The method copes fine with 360 degrees of rotation or any ammount x-y translation (there is an even an example of that). This is simple a function of mapping from 2D to 1D space. In one dimensional space the concepts or rotation and x-y tranlation simply have no meaning.

However the method shown relies on having *all* the points, no extra points and no missing points. This is because it is using the centriod to create the vector. A single missing or additional point will result in a different centroid, and vastly different vector.

It is not clear what the real problem you are dealing with is. Curious? It seems now that missing and additional points are an issue. If so you can modify the method as follows.

Without an accurate centroid we must choose one (or more) arbitrary points to use for our 2D->1D mapping. You could choose x_min, or y_min or any other arbitrary point but given templates with ~ 10 points I would just choose all of them in sequence, ie arbitratily declare each point the 'centroid' in turn and calculate the 1D distance mapping vector as before. Insert this data into some sort of easy lookup hash structure. You probably won't need the sort anymore which is O(logn) anyway. You now have all 10 possible 1D mappings of your template object from every possible point, thus rotation, translation, and added/missing points are not an issue. For any given point set you can rapidly check that sets correlation against all the templates in O(n) time.

I will be interested to hear how you get on.

cheers

tachyon

In reply to Re^3: Interesting problem fitting points to a template (algorithm?) by tachyon
in thread Interesting problem fitting points to a template (algorithm?) by doowah2004

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.