Identify the source edge of the merged polygon

Question

I have many polygons, and after combining all these polygons, I get a new large polygon. The combined algorithm is a black box and uses a third-party library process that I could not control, and I also can not extract any information from a kind of progress.

Is there an effective way to find out for each edge of this large giant union polygon which one belongs to that edge of the smaller polygon?

Most likely, to solve this problem, you need to compare each edge of the combined polygon with each of the smaller polygons, but this will be very inefficient. Any other more efficient methods?

My hunch is telling me that a line-sweep algorithm can help here, although I have absolutely no idea how to do this.

Edit: small npolygons may overlap, so an allied polygon may contain points located on the edges of small polygons, but these points may not be the vertices of the original polygons.

Screenshot shown below:

Answer 1

Here is one solution.

Take each original edge. They can be (exceeded) set by three things:

• Vector direction indication
• starting point
• End point

(, , x y 1). , , . ( , .)

, , , , , , .

, , , , . , .

Answer 2

- , (. ), .

, , . "contains" , . , , , .

: , , . :

INPUT: , E1, V1 V2 .

OUTPUT: , V1 V2 .

• , V1, V2 (, , , V1, V2)
• , V1, V2.

. , . A K-D ( ) , . , , R-. stackoverflow . , , .

---

:

, - . , . , - : , (), . : , , . O (log n) .

, , , . , , . , , .

- : , . , , .

Answer 3

BSP quadtree, . , .

node (s).

n m . O(n log n) O(m log n). O((m+n)*log n).

: 2 , . quadtree. .

You can do it differently. Create quadrants of the output edges of the polygon and find each edge of the original polygons. Runtime O((m+n)*log m), which is faster. But with the top approach, you can extract more information from input polygons if you need it in the future.