|
I know that I am opening Pandora's box, and I fully expect to be met with an angry hoard of rabid Bats, but I have an idea for constructing a convex hull from a data set. What I was looking for was a "Best" algorithm (here come the Bats) so that I might code it as a baseline to see if my algorithm is any faster. I was actually looking for triangulation, but wanted to start with the convex hull first.
I have already googled convex hull, but there is not too much info about relative performance.
The data will be just 2D (x,y) where there will be 64K-1 unsigned shorts for both x and y, no repeats (randomly select an integer from the set of (1 to (64k-1)), then remove the integer from the set, decrement the set size, and randomly select another entry from the remainder of the set). x and y will be independently randomized. The x y pair will not both be equal (swap the y value with the immediately following or previously defined pair whichever does not violate x!=y for either resultant pair). The set of points will be saved on a file as binary pairs, each algorithm will then be used to read the points and create the convex hull.
I will code my algorithm and the base algorithm in MASM, single threaded (the method should be able to be implemented as multi threaded, but for simplicity and timing, I wanted single threaded). I will use the MASM32 timing macros to set the CPU into Real Time Priority to try to get as accurate a timing as possible.
I'm not looking for code, just a detailed algorithm which would allow me to implement this sought after "Best" algorithm to use as a baseline.
Anyone have a guess how long this 64K-1 set might take to encircle? Should I reduce the size of the set?
Bring on the Bats!
Dave.
|
|
|
|
|
|
Arash,
I am "shocked"! You didn't suggest Wycobi!
Yes, I have read all of the CP articles and Wikis related to "Convex Hull" and read all of their references, but there is not too much reference to relative speeds under the same set of conditions, the touted advantages are mainly about how the algorithm extends to three or more dimensions, etc.
My attempt will be along the lines of "divide and conquer" with several twists I dreamed up (literally - went to bed thinking about the problem and woke up with what I thought was a good solution).
Dave.
|
|
|
|
|
Arash,
Sorry for the double post, but please forgive me. I did not thank you for your reply (I did vote you for a good answer to my question). I actually had expected you to be the first to respond, and my initial reply was a attempt to be humorous (think back to 1941 and "Casablanca").
Dave.
|
|
|
|
|
Hi
I want to write a program that finds LIMIT of a math function in VC++
Would you please help me where to start, or any source code, or any other help
Thanks
www.logicsims.ir
|
|
|
|
|
The limit for a particular class of functions or an arbitrary function?
If you want to enter any given function and return the mathematical limit, then you'll need a parser and some kind of symbolic math engine in order to carry out operations like L'Hopital's rule, etc...
Not exactly a trivial programming project.
|
|
|
|
|
thanks
I know, for sure it needs a parser, I have wrote some for drawing math functions, and matrix and...
but I have no idea about limit!
please help me if you can
Thanks
www.logicsims.ir
|
|
|
|
|
Hadi,
I am wondering what kind of answer you are looking for. Are you looking for a numerical answer such as 3.14159 or a symbolic answer like PI? Also, do you want this function to work any function? For example the limit as x goes to 0 of log(x) is not defined. I believe I could give you a better answer if I had a better idea of the real problem you are solving.
By any chance, are you doing this to get a PhD?
Bob
|
|
|
|
|
If you already have some for drawring, you should be able to adapt that. Lim x->c = slope of a function at point c, right? (change in y over change in x) If you add some boundary checking, you might come close without too much code required.
|
|
|
|
|
I think you need to be more clear about what, exactly, you want. For certain classes of functions calculating the limit is quite involved and requires differentiation. If you want to do this for any input function then you'll need to get into symbolic manipulation. That's a project in itself. Calculating mathematical limits is not an easy task.
|
|
|
|
|
Thank you all
In fact yes, I want to write a program for calculating all limits, for example Lim(sin(2/x)) when x->0, or even x->Infinite
so I must write a parser I think
but maybe I can find something that helps me how to start!
thanks
www.logicsims.ir
|
|
|
|
|
Hi Hadi,
The problem is not just the parser. You will also need both a symbolic manipulation and numeric component. The symbolic package will be needed to calculate derivatives for certain limits that require l'Hopital's rule[^]. Other methods used in computer-based limit calculations are Wynn's epsilon algorithm[^] and generalized Euler transforms.
As you can see, it is a non-trivial project and requires an understanding of some rather advanced mathematics.
|
|
|
|
|
|
|
Yeah, but don't black bodies absorb and then re-emit photons of the same frequency? Melanin absorbs UV and then re-emits about 99.9% of it as infra-red. How does it do THAT? Where does the rest of the energy go?
Richard A. Abbott wrote: Are you querying this because of interest in Anti-Cancer agents or ???
I dunno. Just generalised interest.
|
|
|
|
|
If I can remember back 40 years to my Chemistry/Physics classes, the energentic UV hits the atoms of the Melanin and causes the electrons to jump several states (all jumps are discrete jumps of energy levels), and then the electrons drop back down one level at a time releasing the energy in the form of IR (lower frequency, lower energy). There is no extra energy, but the IR will cause an increase in temperature in the local area.
Dave.
|
|
|
|
|
Ohhh, OK, so the electrons don't have to make the same sized leap all in one go. OK, that makes sense. 
[edit:] Of course, that leaves the question of how it so consistently chooses these smaller quantum-leap pathways...
modified on Sunday, November 9, 2008 2:12 AM
|
|
|
|
|
Hi
thank you very much, it helps me a lot
thank you
www.logicsims.ir
|
|
|
|
|
Hadi Dayvary wrote: for sure it needs a parser
Have you seen these from this CP article search[^]? The one by Hatem is a really good one.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
73Zeppelin wrote: Not exactly a trivial programming project.
I agree. Interesting project idea, nonetheless.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
Paul Conrad wrote: I agree. Interesting project idea, nonetheless.
Yes, looks like he's shooting for a Mathematica-type app. Very interesting, but quite involved - not sure if it's a single programmer project.
|
|
|
|
|
73Zeppelin wrote: looks like he's shooting for a Mathematica-type app
Sounds like it.
73Zeppelin wrote: Very interesting, but quite involved - not sure if it's a single programmer project.
Yep. It would be a pretty ambitious project to do by oneself.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
No, it's a team work, we are working on a new math project,
we need to do this
www.logicsims.ir
|
|
|
|
|
I'm not expecting a wodge of code handed to me on a plate (though I won't say no...), more of a string hint on where to go looking.
I have a set of data points (successive Y values evenly spaced along the X axis). This is crudely a flat line of 0, with a bump part of the way a long, and then some noise added. The bump could well have a flat top to it.
By eye, it's easy to work out where the peak of the underlying curve should be, but a lot less easy to just grab a crude maximum value and expect it to be useful.
From experience, the curve is pretty close to a gaussian that someone has sliced the top off of. I'm trying to find some method of writing / reusing / blatantly stealing a black box function I can give a series of Y values, and get the parameters (centre X, magnitude and 'sharpness') of a gaussian curve.
Can you give me any pointers to useful web pages you've found?
I'm not averse to writing my own, wiggling values and doing fit comparisons, but I'm sure someone made a wonderful algorithm with three names in the 70s that would be vastly superior.
Iain.
|
|
|
|
|
What about least squares?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
