Archived

This topic is now archived and is closed to further replies.

Gestalthalcyon

How to tell if polygons overlap?

Recommended Posts

I''m trying to make a quad tree but relized that I don''t know of a good way to tell if two polygons are overlaping. Namely a square in the quad tree and my view frustum. All of these should return that they are infact overlaping, but the only ways that I can think of would require 20+ checks. How do people normaly do this? §LateR§

Share this post


Link to post
Share on other sites
Don''t know how most people do it, but I would cut the polygon by the 4 side planes of the quadtree square. If there is something left of the polygon after the 4 clips, they overlap.

My Site

Share this post


Link to post
Share on other sites
In my previous post I was talking about a plane, but that should be a line in 2D. I'm sorry.

The vertical red line is the line you'll cut the polygon by. In the first picture we have the old polygon, in the second one it's cutted by the line





The parts you just clipped away are outside the rectangle for sure. Now you cut the polygon you have left by the next edge of the rectangle, and for the next one and the next one. If there's still something left of the polygon, they intersect.

if you don't know how to implement it, I can help you with it.

My Site

[edited by - Quasar3D on July 8, 2003 6:45:52 AM]

[edited by - Quasar3D on July 8, 2003 6:46:40 AM]

[edited by - Quasar3D on July 8, 2003 6:52:32 AM]

[edited by - Quasar3D on July 8, 2003 6:52:47 AM]

[edited by - Quasar3D on July 8, 2003 6:56:16 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Pipo DeClown
Ik begrijp je niet, I don''t understand you.


Begreep je mijn ascii art niet, of begrijp mijn hele post niet? Ik kan wel wat beter uitleggen als het niet duidelijk is.

Don''t you understand my asci art, or don''t you understand my entire post? I can try to explain it better if it isn''t clear.

My Site

Share this post


Link to post
Share on other sites
Thanks for the replys. I apoligize about the cross-posting. I''m relitivly new here and didn''t realize that it was a problem. In the future, I''ll keep it in mind. I deleted the other thread. Is it ok to post the same thing on a different board if you delete the first post before?


Anyways, I see what you mean by that cutting method now. This method does seem like it would be precise. The only way that I can see to do this would be to do 4 line intersect tests, add new vertices (or move the old ones) where they intercect, loop through all the old vertices and delete the ones outside the cutting area, leaving a new polygon (or none). Then repeat for the other 3 lines that you are cutting with. This is 4 intersect tests plus 4 point line test per edge. That ends up being a minimum of 32 tests per polygon doesn''t it (if it doesn''t fail). Is that fast enough? Is there a way to do this that I have not thought of? If anyone has an example of how they did it, I would appreciate it.

§LateR§

Share this post


Link to post
Share on other sites
because the edges of the rectangle are axis aligned, the intersection test is very fast (only 2 <''s). I think this method is pretty fast.

My Site

Share this post


Link to post
Share on other sites