Programming Help - Trigonometry / Geometry / Mathematicians

sama · 09-10-2007, 04:00 PM

Consider that I have a vector of points, that are NOT in sequence, but when they're all drawn they form a contiguous line as shown below in black.

how can I pragmatically extract the peaks and dips, as shown by the red crosses?

I can order the points to be in sequence, but this will eats up valuable CPU clocks.

I have an idea to track the direction of travel and monitor the change in cardinal directions, waiting until a loop of directions has been passed (like N > NE > E > SE) but this is a tricky algorithm to implement, and can get expensive with having to first order the points, then do the scanning.

I'm looking for a more elegant solution before I attempt the above.

any ideas?

2k1Toaster · 09-10-2007, 04:14 PM

well if they are sorted, or can be sorted, then they should be. It shouldnt eat that much CPU. If they are all doubles, then comparator functions should be cheap.

Well if they are sorted, the easiest way I see, is to just take point n, point n + 1 and n - 1. You can also check points n +/- m with weighted averages.

When the average of points n and those first, switches in greater/less than, you have a slope change.

So if n and m points slope before give a value greater than 0, then the slope is up/positive. if n and m points after give a negative slope, then somewhere between n-m and n+m there is a slope change like /`\. Same visa versa, except that would be \./ so it would be low point.

It is clear in my head, but I am known for not explaining things very well.

2k1Toaster · 09-10-2007, 04:18 PM

I should add, that this only works if there is a "function" that could be described from these vector points such that it is 1 to 1. Meaning it passes the "vertical line test" meaning there is a unique x value for any given y value with y being vertical and x being horizontal in the picture. So no circles, or waves vertically.

2k1Toaster · 09-10-2007, 04:35 PM

Case #4 is the cool/hard one.

You see, you pick m to be rather large (smaller however than the minimum distance between peaks can ever be though as to avoid losing accuracy). Then when you test and get a case like 4, where the difference is there, but the slope of the line from (n - m) to n does not equal the negative of n to (n + m). So if the slope from (n-m) to n is X then the apex is where the slope of n to (n+m) is -X.

So when you get to case #4, you halve your "m" value, and try again but only over the region from n-m to n+m. This way it saves CPU cycles. For easiest programming this factoring down could be ommitted by just making m a really small value to begin with. However this will destroy your CPU cycles.

sama · 09-11-2007, 02:10 AM

thanks for the answer dude.

this is a tracking approach effectively, where anything that's out of the straight vector is considered a change in direction, and it is the change in direction that's monitored.

I'm sure this can work, but it it's worth adding at this point that:

- the line may not always be that smooth, so false positives are possible. I guess some smoothing is in order, perhaps at the sorting stage.

- the peaks and dips do not always increase on the x axis, things can switch

- "shallow" peaks/dips need to be ignored

Here's some more info showing more about the problem

PS the reason the list isn't sorted, is because I'm detecting an edge, and I'm doing so with a single scan over an image, rather than travelling along each edge found as this gives predictable performance.

2k1Toaster · 09-11-2007, 02:13 AM

Is this for readings from an optical sensor of somekind? I am just having difficulty picturing it...

But for the last picture you showed, my first approach wont work at all.

Ill have to sleep on this...

sama · 09-11-2007, 02:14 AM

yep (I've just updated the post + pic)

galvitron · 10-03-2007, 10:40 PM

Is there a coordinate system you are imposing on this, for example North = Y-axis, etc? Do you know where North is when given the batch of points?

Assuming you had a coordinate system, you can't create a function because of what 2k1 mentioned...not 1 to 1. But you can divide the points into sections (using a grid maybe) and try to extract max/min values in each section. You would have to have the points in order and you would probably want to drop sections that confused or complicated the algorithm too much...

Damn, I hate using my brain :P

sama · 10-09-2007, 03:52 PM

thanks for the response. I've now figured a new method of doing this, and it's doing well, but I'm still working on getting it perfect:

1. sort the points (easily done through proximity and reordering)
2. start at a point P1 and draw a line to the P3, at the same time as drawing a perpendicular line from the middle of the drawn line to P2.
3. the length of this line measures the height of the curve between P1 and P3.
4. go to P5 and try a perpendicular line with P3... and so forth
5. until the length of that line starts to shrink*, indicating it passed the peak
6. start at the new point (end of last peak) and do it all over again.

*false positives can be ignored by smoothing the line whilst sorting it

galvitron · 10-12-2007, 11:55 PM

Nice.