# Trying to find a minimal set of polygons that intersect a rectangle.

This topic is 2414 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have an ordered set of polygons and I am intersecting them with a rectangle, how do I tell when the rectangle is filled so I can stop checking? This is in 2D.

I am trying to get the minimal set of polygons with cover the rectangle. The order of the set is the priority of use and the polygons are simple (don't have holes or self intersecting). So if my set is {A,B,C,D} and A B D intersect the rectangle but A contains B than I want a the set that contains just {A, D}.

Tried googling but wasn't sure what to google really, I was thinking it would fall under polygon coverage but that didn't seem to produce results of what I was looking for.

Thanks

##### Share on other sites

I have an ordered set of polygons and I am intersecting them with a rectangle, how do I tell when the rectangle is filled so I can stop checking? This is in 2D.

I am trying to get the minimal set of polygons with cover the rectangle. The order of the set is the priority of use and the polygons are simple (don't have holes or self intersecting). So if my set is {A,B,C,D} and A B D intersect the rectangle but A contains B than I want a the set that contains just {A, D}.

Tried googling but wasn't sure what to google really, I was thinking it would fall under polygon coverage but that didn't seem to produce results of what I was looking for.

Thanks

I think this is a hard problem theoretically. For a practical solution, have you thought about rasterizing the rectangle and polygons to a high-resolution grid? Rasterize the rectangle first. Rasterizer your polygons one at a time, keeping track of which rectangle pixels are written to (sort of like a stencil buffer) and which polygons have been rasterized to previously unwritten pixels. Once you have rasterized to all pixels, the process terminates. (You have to deal with not writing all rectangle pixels after all polygons have been processed.)

##### Share on other sites
If you have fixed polygons and an order in which to use them, you can simply maintain the uncovered portion of the target figure, initially a rectangle and generally a set of non-overlapping polygons (possibly concave and with holes: splitting them into a set of convex polygons might be wise).
You can clip each uncovered piece against the successive covering polygons: if the covering polygon overlaps any uncovered piece, remove the overlap from the set (removing parts of some pieces or whole pieces) and continue until all uncovered pieces are gone or you have tried all covering polygons.
In the example, piece B would be excluded because, after A cuts out a part of the figure, B doesn't cut anything more. Correctness depends on the ordering of covering polygons: B must come after A to be rejected.

Where does the covering polygons sequence come from? Are they convex? Can you guarantee that they cover the target shape? Can you guarantee good performance, without pathological splitting? Can you guarantee that the sequence doesn't contain polygons that are contained into other polygons?

1. 1
Rutin
48
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633409
• Total Posts
3011717
• ### Who's Online (See full list)

There are no registered users currently online

×