http://qs321.pair.com?node_id=1204095


in reply to Re: Polygon Creation -- Request for Algorithm Suggestions
in thread Polygon Creation -- Request for Algorithm Suggestions

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

Replies are listed 'Best First'.
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

      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

      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

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