From the bottom of my mind:
The simplest algorithm I'm aware of is to successively
- construct the smallest polygon enclosing n-1 points
- check if point n is inside the polygon
- if YES then it's already the smallest polygon enclosing n points
- if NO then include it as a new corner
You have to start with a triangle and finish with the smallest convex hull.
The check is crucial, you need a scalar product of the point vector with orthogonal vectors on all edges pointing inside.
If the product is positiv it means the point is "inside" the edge.
Iff the point is inside all edges, it's inside the polygon.
Otherwise you extend the polygon by replacing all "outside" edges.
(Most probably you'll also need to move the points before doing the product, such that the edge goes thru (0,0) )
HTH and you get the idea.
I'm pretty tired, lacking the right vocabulary and typing into my mobile without possibility to scetch it on paper. :)
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: |
| & | | & |
| < | | < |
| > | | > |
| [ | | [ |
| ] | | ] |
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
