Clever Geek Handbook

Algorithm for determining a set of paired visible edges between two concave polygons

Let's say we have two concave 2d polygons (A, B) that do not intersect. The problem is to find a set of pairs of edges (each pair consists of one edge from polygon A and an edge from polygon B) that have the following property: each element in the pair must be visible to each other. One edge is visible to the other, if there are no obstacles (in Fig. 3), there are three cases between them, marked with a red cross, when this rule is violated).

enter image description here

I know how to solve this problem in O (n ^ 2) using rays and edge vertices. But this is too slow.

+3


source to share


1 answer


I don't think it can be done faster than O (n ^ 2).

See the picture below. There is a hyperbola and two polygons. The vertices of each polygon are on the branch of the hyperbola.



Two polygons. One on each branch of a hyperbola.

In this case, the edges of the two polygons appear to be visible (except for the two edges behind). Then the result set will contain pairs of O (n ^ 2) edges.

+6


source






More articles:


All Articles