DCEL data structure edge refinement algorithm (edge cases)
I'm trying to connect two polygons that are described as DCEL data structure and find it hard to do so at some edge cases where, for example, edges intersect with each other at their interior or overlap each other.
Here's the definition of the problem:
- The polygons are of rectangular shape with straight edges (edges at vertices make straight angles)
- There are no more than 8 edges that meet at the vertex. The only case where it's possible is that all 4 polygons meet at single vertex (aka 4 rectangles)
- It's impossible to have more than 2 edges intersecting in their interior
- It's impossible that polygons intersect not on segments. All intersections are done on edges and all of them are mix of overlapping cases or interior intersections
- There are no holes in polygons
- Dissolving internal faces is not allowed here. Edge in between still must be present
If this helps the polygons are representing imaginary regions enclosed under the imaginary country that's why they meet at edges only.
Here are some examples of polygons:
Case 1:
Case 2:
PS: Right now I'm reading Bergs 'Computational Geometry' and trying to practice in DCEL implementation
PSS: In addition I've read a lot of info across the Internet regarding handling subdivision overlapping, but haven't seen the explanation about how to handle such cases. What I think here is that I need to handle edge removal while Berg does not tell this in his book.
Also extra source: same Berg, but with more fancy images
https://cw.fel.cvut.cz/b201/_media/courses/cg/lectures/09-intersect-split.pdf (p. 26/96)
So after tons of trials and errors I found the solution to my problem. It's not ideal because I still don't know the 'correct' answer on how to split edges when they are neighboring to each other for arbitrary polygon, but have a solution to my problem that I was trying to solve.
According to the algorithm that Berg described in his book edges must be refined using sweep line algorithm. Previous and next edge must be selected in the CCW or CW order (CCW = counter clockwise, CW = clockwise) depending in what direction edge is pointing, but it's hard to do so when you have overlapping edges. Additional complexity here will be that the edge consists of two half edges and it's a nightmare to refine both of them according to simplified algorithm described above. Instead, what we can do here is to forget about two half edges and use only one. It will always have incident face but no twin. In this case overlapping is detected perfectly using sweep line algorithm and polygon stitching becomes straightforward: the overlapping edges become twins to each other when edge refinement is done (splitting edge at the event point in case if edge contains it in the interior). When edge is split the other edge that belongs to another polygon becomes its twin
It looks a bit messy without thorough explanation, but I'll attach image that will show what I mean by that
On the image you can see edges like a2 that gets split into two new edges - a2' and a2'' plus old shrunk a2. Refinement of a2 was done at two points - v5 and v8. Each point is a beginning of the new half edge and the end of previous one. When we have two edges that are ending at a point (it's impossible to have more than 2 edges in my problem) we mark them as twins (b4 and a2'). Resolving next and previous here is really easy.
To bypass the contour of stitched polygon (black lines) you can use info about the twin of next edge. If it has a twin then switch to the twins next edge at next step (next_edge = a2'.twin.next is the same as next_edge = b4.next)
PS: it will not work for case when you have multiple polygons overlapping at the same edge. It's hard to make twins in such case, but it's a question whether the correct solution exists or not?