Jump to content
  • Advertisement
Sign in to follow this  
fredysays

Looking for complex polygon decomposition code

This topic is 4160 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'm looking for code that will decompose a non-simple (intersecting edges) polygon into simple polygons. I know there are several implementations that will triangulate a complex polygon, but that doesn't fit my needs. The following link mentions how to do this: http://geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm (Towars the middle of the page is what I am after). However this looks to be reasonably complex code to implement and I don't want to reinvent the wheel if this already exists somewhere. Any help appreciated.

Share this post


Link to post
Share on other sites
Advertisement
I didn't read it that carefully, but it says on that page that they've implemented that method, and that there is C++ code at the bottom of the page (which there is). I don't know if this is a complete implementation of what you want, but I guess it'd provide some of the framework for what you require.

Dan

Share this post


Link to post
Share on other sites
Compute all edge-edge intersections. If a point of intersection of two edges is interior to one (or both) of the edges, split that edge into two edges (split both edges). You can do this step efficiently using a sweep algorithm. The sample application MeshEnvelope uses such a method (although with exact rational arithmetic).

What you have now is a vertex-edge graph for which you need to compute the minimal cycle basis.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!