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)