• Advertisement
Sign in to follow this  

Logic for polygonizing lines where the polygon with multiple holes

This topic is 1048 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to make a 2D map editor, and while I can easily triangulating convex/concave polygons from articles I've read... I'm unsure how to make the jump to handling one with holes in it in practice. So far, I've read a paper that provides a method if connecting two visible vertices to slice it into a monotome polygon, but I get quite lost in practice when I have to polygonize the orangey-yellow area:

2eZRndK.png

The only data I have (as you see above) is:
- The lines and their vertices
- Which side of the line is the 'front' which determines if a sector is being enclosed, or if they're all facing out and it makes a hole

There is no sector information at all, my goal is to use to construct the bounds for a sector.


1) How do I polygonize the colored area with all these holes? Just looking for the logic here, code isn't needed.
Flood filling is not an option since I'm dealing with floating point vertices.


2) How can I use the facing sides to determine if it's an enclosed sector or not?
Basically, how can I tell all the lines I'm tracing are facing inside.
An idea I had was adding up the angles of all the lines, and if the average is >180 degrees, it's facing outward. Is this thinking correct? Is there a better way?

Share this post


Link to post
Share on other sites
Advertisement
You can use a library such as CGAL or use GLU's tessellators. The general approach seems to be to construct a Delaunay triangulation with all of the edges and then punch out the holes. As for determining what's in and what's out, use the winding order of the contour to determine whether or not it's adding or subtracting from the geometry.

Share this post


Link to post
Share on other sites
I probably should have specified that I won't be using a library. I have to learn to code this fully on my own, I appreciate the links however.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement