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§
How to tell if polygons overlap?
Author
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§
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§
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
My Site
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]
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]
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
Author
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§
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§
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
