3

Given a set of polygons P and a rectangular area A, I need to verify if A is completely covered by P.

The number and complexity of the polygons and the total area A are significantly large and so, a polygon union-based approach might not work in time. To make things a bit simpler, I defined A' as the size of the smallest area inside A whose coverage I care about. I thought of building up a 2D segment-tree like structure dividing the area in 2D repeatedly(each area square breaks into 4 child squares until the child square size is A') but since we are dealing with polygons here, I am not sure if this would be efficient enough.

user1089464
  • 273
  • 2
  • 10
  • What is limitations? count of polygons, min max coordinates(target polygon and all other)). – Толя Feb 27 '13 at 08:46
  • I think this could help : http://stackoverflow.com/questions/2272179/a-simple-algorithm-for-polygon-intersection – Tony Morris Feb 27 '13 at 15:55
  • [1] I have more than 50K polygons and the size of A is pretty large. To add more context, I had to divide A upto 14 times to reach the size of A' (ie) A = 4^14 * A'. @TonyMorris The polygons I am dealing with are quite complex with inner holes etc... I used a 3rd party libraries to find the union(as mentioned in the post) but it was of no use. On the other hand, finding whether a rectangle fell inside these polygons ran much faster and that was the reason I tried the 2D segment tree approach – user1089464 Feb 27 '13 at 18:11

1 Answers1

0

You can use polygon intersection or difference instead of union:

Consider A itself as a polygon and each time pick a polygon P' and refine A as A - P', and check to see if A is empty. After checking all polygons you can say for sure whether A is covered by P or not.

Ehsan Shoja
  • 443
  • 3
  • 6
  • On a side note, how do we actually implement a 2D-segment tree? The issue I see here as compared to a 1D tree is that in a 1D tree, we know that a queried range splits only twice while traversing the depth and returning the result. But in 2D, that does not seem to be the case – user1089464 Feb 28 '13 at 03:10
  • I think for 2D-segment trees you should first consider x-projections of the segments resulting in a 1D-segment tree then each node of the tree is also a 1D-segment tree over the y-projection of the segments inside the nodes x-range. – Ehsan Shoja Feb 28 '13 at 13:54
  • also my answer above that needs computing A-P' seems to be tricky if polygon P' contains holes. – Ehsan Shoja Feb 28 '13 at 13:55
  • Yes, I was about to say the same. I took off with that solution in a hurry but the problems with creating the union with complex polygons comes back while running it via the A-P' solution. – user1089464 Mar 01 '13 at 12:12