My question is similar to question here Divide self-intersecting polygon I have

Question

My question is similar to question here Divide self-intersecting polygon

I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects.

I have to divide it into simple polygons and tessellate them later.

I have an issue how we currently select the edge after the intersection point is encountered. Right now we select an intersecting-edge which makes the smallest angle with the preceding edge. This approach simplifies some intersecting loops (e.g. horizontal '8' is divided into two 'o' loops).

But this approach has some issue. Say two polygons one inside another. Such polygons are not divided into two loops.

I plan to select an intersecting-edge which makes the largest angle with the preceding edge. This way I can get the outermost loop first and than I will form the internal loops with remaining edges. This will solve the problem for 'two polygons one inside another'. (This will fail for cases such as 'horizontal '8''. But this is OK as such case is handles while tessellating polygon)

Are there any known/unforeseen problems with this approach?

Explanation / Answer

A self-intersecting polygon induces a plane partition, which should be represented by some data structure. This structure should include at least three types of objects - vertices, edges and faces. The faces are what you are trying to construct.

This data structure is called DCEL and it usually represents both planar graphs - the original graph with vertices and edges (where intersection points are added as new vertices, and some edges are split), and a dual graph with polygonal faces as vertices. Each vertex in the original graph should refer to a list of adjacent edges (sorted by angle, yes) and each vertex in the dual graph should refer to a list of adjacent edges, forming its boundary. Edges are usually represented by two arcs with orientations, opposite to one another. In this case each arc is adjacent to exactly one face (including the exterior face), which normally lies "to the left" of it.

Having this data structure implemented you'll be able to calculate all the faces by finding proper cycles in the set of all arcs.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.