3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You are saying "Say two polygons one inside another". But - if you have a single self-intersecting polygon, how would you get two polygons one inside another? $\endgroup$
    – HEKTO
    Commented Aug 25, 2014 at 19:24
  • $\begingroup$ Hi HEKTO, imagine circle connected tangentially. You can have them tangent externally or internally. '"two polygons one inside another"' will be similar to circle with internal tangent. So if you have tessellated circle and created a polygon, it will still be single polygon but with intersection. $\endgroup$
    – user3406792
    Commented Aug 26, 2014 at 7:40
  • $\begingroup$ So, your internal and external "polygons" will have common vertex, or edge, or intersection point, right? $\endgroup$
    – HEKTO
    Commented Aug 26, 2014 at 23:31
  • $\begingroup$ Yes, the internal/external polygons will have common vertex or intersection point (common edge will not be there). $\endgroup$
    – user3406792
    Commented Aug 27, 2014 at 8:14

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the reply HEKTO! But this does not solve my question. My basic question is : Once I encounter an edge with an intersection how should I choose the next edge for the face? Currently we select next edge which makes the smallest angle with the preceding edge. Is it safe to choose next edge which makes the largest angle with the preceding edge? $\endgroup$
    – user3406792
    Commented Aug 28, 2014 at 12:40
  • $\begingroup$ All edges, adjacent to a vertex, are ordered by angle. This order is cyclical, so the first edge follows the last one. When an edge enters a vertex you need to find a position of this edge in the edges list. The edge in the next position will be your next edge. A picture in wiki shows that as next(e) $\endgroup$
    – HEKTO
    Commented Aug 28, 2014 at 14:56
  • $\begingroup$ I forgot to mention - edges in each edge list should be clockwise-ordered $\endgroup$
    – HEKTO
    Commented Aug 28, 2014 at 20:12
  • $\begingroup$ @HEKTO Am I right that the DCEL presented in de Berg's book (mentioned in the link to wikipedia in your answer) does not store all edges adjacent to a vertex. Each vertex only has one "incidentEdge" field. So to get this list of edges sorted by angle you'd have to do some kind of pre-processing and create an extra data structure? $\endgroup$
    – Rob N
    Commented Oct 24, 2022 at 1:02
  • $\begingroup$ @RobN - yes, you're right, a version of the DCEL in this book is slightly different. However, this version still allows us to list all edges, incident to a vertex - for that we need to use pointers $Next(e)$ and $Twin(e)$ for each half-edge $e$. No extra data structure is needed. If we store a list of incident edges in each vertex (as I described in my answer), this process will be faster, but dealing with variable-length lists of half-edges might be an additional headache. $\endgroup$
    – HEKTO
    Commented Oct 24, 2022 at 22:08
0
$\begingroup$

Suppose you've gone counterclockwise along some edges on the exterior of the polygon and now you've come to a vertex and/or intersection point (I'll just refer to them all as vertices from now on) V from vertex U. Then if you begin opening an angle from the V, going counterclockwise, you'll sweep through the exterior of the polygon. So the edge at V creating the smallest angle with V -> U going counterclockwise is also an edge on the exterior.

To put it another way, if you are going clockwise, the edge that creates the largest angle (where largest means the largest going counterclockwise) is also an edge on the exterior.

To be clear, suppose you're building the outer loop in clockwise order. Then you DON'T want the largest angle as measured by dot products, since that gives you the angle when you're allowed to go either clockwise or counter-clockwise direction.

Here's a suggestion based on the same observation. 1) Find an exterior edge U -> V oriented clockwise around the polygon. 2) Take the SMALLEST angle as measured going counter-clockwise V. This edge is guaranteed to be an edge of the minimal interior polygon of which U->V is a part. Continuing in this manner, you'll get the minimal polygon of which U -> V is a part. You cut this off and repeat.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.