# 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.

## 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 on other sites
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 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.

1. 1
2. 2
Rutin
17
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633735
• Total Posts
3013596
×