Results 1 to 10 of 10

Thread: Programming Help - Trigonometry / Geometry / Mathematicians

  1. #1
    FLAC sama's Avatar
    Join Date
    Feb 2006
    Location
    London, UK
    Posts
    1,375

    Programming Help - Trigonometry / Geometry / Mathematicians

    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?

  2. #2
    Fusion Brain Creator 2k1Toaster's Avatar
    Join Date
    Mar 2006
    Location
    Colorado, but Canadian!
    Posts
    10,045
    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.
    Fusion Brain Version 6 Released!
    1.9in x 2.9in -- 47mm x 73mm
    30 Digital Outputs -- Directly drive a relay
    15 Analogue Inputs -- Read sensors like temperature, light, distance, acceleration, and more
    Buy now in the MP3Car.com Store

  3. #3
    Fusion Brain Creator 2k1Toaster's Avatar
    Join Date
    Mar 2006
    Location
    Colorado, but Canadian!
    Posts
    10,045
    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.
    Fusion Brain Version 6 Released!
    1.9in x 2.9in -- 47mm x 73mm
    30 Digital Outputs -- Directly drive a relay
    15 Analogue Inputs -- Read sensors like temperature, light, distance, acceleration, and more
    Buy now in the MP3Car.com Store

  4. #4
    Fusion Brain Creator 2k1Toaster's Avatar
    Join Date
    Mar 2006
    Location
    Colorado, but Canadian!
    Posts
    10,045


    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.
    Fusion Brain Version 6 Released!
    1.9in x 2.9in -- 47mm x 73mm
    30 Digital Outputs -- Directly drive a relay
    15 Analogue Inputs -- Read sensors like temperature, light, distance, acceleration, and more
    Buy now in the MP3Car.com Store

  5. #5
    FLAC sama's Avatar
    Join Date
    Feb 2006
    Location
    London, UK
    Posts
    1,375
    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.

  6. #6
    Fusion Brain Creator 2k1Toaster's Avatar
    Join Date
    Mar 2006
    Location
    Colorado, but Canadian!
    Posts
    10,045
    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...
    Fusion Brain Version 6 Released!
    1.9in x 2.9in -- 47mm x 73mm
    30 Digital Outputs -- Directly drive a relay
    15 Analogue Inputs -- Read sensors like temperature, light, distance, acceleration, and more
    Buy now in the MP3Car.com Store

  7. #7
    FLAC sama's Avatar
    Join Date
    Feb 2006
    Location
    London, UK
    Posts
    1,375
    yep (I've just updated the post + pic)

  8. #8
    Maximum Bitrate galvitron's Avatar
    Join Date
    Mar 2007
    Location
    Socal
    Posts
    719
    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
    2006 Lancer Evolution IX MR In-Dash PC Project - WIP

    Planning:
    [----------] 100%
    Purchasing:
    [----------] 90%
    Installation/Fab/Assembly (Revised v2):
    [----------] 90%


  9. #9
    FLAC sama's Avatar
    Join Date
    Feb 2006
    Location
    London, UK
    Posts
    1,375
    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

  10. #10
    Maximum Bitrate galvitron's Avatar
    Join Date
    Mar 2007
    Location
    Socal
    Posts
    719
    Nice.
    2006 Lancer Evolution IX MR In-Dash PC Project - WIP

    Planning:
    [----------] 100%
    Purchasing:
    [----------] 90%
    Installation/Fab/Assembly (Revised v2):
    [----------] 90%


Similar Threads

  1. Replies: 0
    Last Post: 07-03-2007, 01:04 PM
  2. EMS programming questions
    By 94legend in forum Engine Management, OBD-II, Engine Diagnostics, etc.
    Replies: 0
    Last Post: 05-27-2007, 12:13 PM
  3. Wanting to learn some programming, help me pick a language!
    By RS3RS in forum Software & Software Development
    Replies: 32
    Last Post: 10-15-2004, 04:38 PM
  4. C++: GUI Programming with >NET Framework
    By [iG] in forum Software & Software Development
    Replies: 3
    Last Post: 05-24-2004, 06:57 PM
  5. Need to start somewhere with Hardware programming
    By 168db in forum Software & Software Development
    Replies: 7
    Last Post: 01-11-2002, 08:35 AM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •