Efficient way of determining polygon intersection with bounding box

Question

I have a set of polygons, and I need to check whether they are intersecting with a given bounding box(rectangle). What I am doing is, I am taking every vertex of polygon and checking whether it's inside bounding box or not.

If yes   
return true   
else   
Now I am taking every vertex(i.e 4 vertices) of my bounding box and checking  whether it is inside polygon or not, 
using  the algorithm from http://assemblysys.com/php-point-in-polygon-algorithm/
if yes   
return true  
else
return false(box and polygon are not intersecting)

This way of approaching is taking too much time. I want another algorithm which is faster than this. I tried to search for an answer on Google but was not able to find anything. I tried for finding code of mysql st_intersects() function on github but again I was unable to find that function code.

I know there are many algorithms but, because I am new to this field I was unable to find algorithms,So I used the above approach.

Note that your approach is wrong. You can very well have a polygon intersecting the box with no box vertex inside the polygon. — user1196549
– user1196549, Commented May 21, 2015 at 12:30

Anders Schou · Accepted Answer · 2015-05-19 14:02:48Z

0

You could create the boundingbox of the polygon, and compare test that against the volume. If the boundingbox of the polygon is inside your test volume, you have no intersection. If the two bounding volumes intersect, you will naturally have an intersection. If the boundingbox of the polygon is outside the test volume, you would have to test each edge, to see if they intersect. You could probably do this test while creating the bounding box.

answered May 19, 2015 at 14:02

Anders Schou

1841 silver badge13 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Aleem Uddin Over a year ago

yes i already do that, but for some polygons if two bounding box are intersecting then also i don't have intersect between my polygon and test volume(bounding box rectangle)

Aleem Uddin Over a year ago

if you can give me mysql st_intersects() code link then it will help me a lot , i have searched in mysql git hub repo but i was unable to find it.

Anders Schou Over a year ago

Do you need to actual intersection point? Or do you just need to know where if they intersect.

Aleem Uddin Over a year ago

i just want to if they intersect or not (true or false)

Anders Schou Over a year ago

assuming you're in 2D, look at stackoverflow.com/a/1968345/1725027 It has a c-implementation of the line segment intersection. Not just loop over all your edges and return true when you get an intersection.

|

Collectives™ on Stack Overflow

Efficient way of determining polygon intersection with bounding box

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related