Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: Polygon Creation -- Request for Algorithm Suggestions

by Anonymous Monk
on Nov 22, 2017 at 20:21 UTC ( [id://1204067]=note: print w/replies, xml ) Need Help??


in reply to Polygon Creation -- Request for Algorithm Suggestions

You say enclosing polygon, by which I'd assume you need a bounding convex polyhedron; the embedded example however shows a non-convex shape. I don't think this makes much of a sense unless the points were ordered (lines) to begin with. In the example, you could reduce the volume by cutting wedges into the shape, thereby making some of the pruned "internal" points appear in the final shape.

  • 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 22, 2017 at 20:33 UTC
    I'm not sure what you mean by polyhedron. It's not a 3-dimensional shape, which a polyhedron is by definition.

    And no, the points were not ordered to begin with -- they were taken from an image which had no extra information other than (X,Y) pairs of points, and an associated color for each point.

    I did look at the module Math::ConvexHull, but determined it didn't do what I needed because if I go with the convex polygon defined for the set of points, it adds more to the shape than necessary, and eats into neighboring shapes to which the algorithm will also eventually be applied.

    say  substr+lc crypt(qw $i3 SI$),4,5

      Aye, a polygon, I stand corrected. It looks to me you have a set of pixels (small squares), or a sprite, and you want vector graphics out of it? The shapes are all solid, with no holes?

      If you have pixels, they should fall on a grid. You could just walk the outline on the grid and be done with it.

        Yes you're correct, it's a set of pixels originally. The shapes are all solid (no holes) and as I mentioned, my pruning algorithm seems to be a plausible first step to narrowing it down to the outline.

        But the "walk the outline" step, as you say, is exactly where I'm stuck. I'm searching for an algorithm that will give me the correct order of points that define that outline/perimeter. If there are any points out of order, they will either cut lines across the shape, or (worse) create regions which are outside of the shape.

        say  substr+lc crypt(qw $i3 SI$),4,5

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1204067]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (5)
As of 2024-04-24 21:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found