Jump to content
  • Advertisement
Sign in to follow this  
HPSC

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

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!