Re: Polygon Creation -- Request for Algorithm Suggestions

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. :)

Cheers Rolf
_{(addicted to the Perl Programming Language and ☆☆☆☆ :)

Wikisyntax for the Monastery}

Comment on Re: Polygon Creation -- Request for Algorithm Suggestions

Replies are listed 'Best First'.
Re^2: Polygon Creation -- Request for Algorithm Suggestions by golux (Chaplain) on Nov 23, 2017 at 00:43 UTC
Thanks, LanX, I agree with you that what I want is a "smallest convex hull". I'll see if I can get my head around the math involved. say substr+lc crypt(qw $i3 SI$),4,5	[reply]
Re^3: Polygon Creation -- Request for Algorithm Suggestions (updated) by LanX (Saint) on Nov 23, 2017 at 14:43 UTC
> I agree with you that what I want is a "smallest convex hull". Looking at the other answers I'm not sure anymore. A convex hull means a banana shape would be represented as a semicircle. You seem to want a tight (not necessarily convex) vector graphic enclosing a sprite. I think you could achieve this by improving the convex hull (by replacing long edges with concave triangles until all edges are sufficiently "short" or "tight") Another problem I see are non-connected segments/territories . The shape of the USA would look very different if Alaska and Hawaii were included into just one hull ... update Found this http://stackoverflow.com/questions/7408470/given-a-vector-of-points-possibly-out-of-order-find-polygon-not-convex-hull Pointing to the next problem There is no unique solution for a concave polygon So starting from a convex hull and improving it till criteria are met is sensible. Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Wikisyntax for the Monastery}	[reply]
Re^4: Polygon Creation -- Request for Algorithm Suggestions by LanX (Saint) on Nov 23, 2017 at 18:47 UTC
One more idea > could achieve this by improving the convex hull take this "banana", the asterisks * are corners of the convex hull but the dots are not approached. `* a * . . . * . . * . . * * b` [download] Now starting from the edge a-b you could construct a "convex" streak from a to b which keeps all other points "outside", just using the same algorithm like before and inverting the orientation. Saying so I'm pretty sure there are already ready to use algorithms which do this in a time efficient way... Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Wikisyntax for the Monastery}	[reply] [d/l]
Re^3: Polygon Creation -- Request for Algorithm Suggestions by LanX (Saint) on Nov 23, 2017 at 09:33 UTC
I can't post images here but I came around this wikipedia article which should be of help understanding how the do product helps identifying distance and orientation of a point in respect to an edge Scalar_projection Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Wikisyntax for the Monastery} update added clarification	[reply]


go ahead... be a heretic
	PerlMonks

Re: Polygon Creation -- Request for Algorithm Suggestions

update

update