2

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.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
Aleem Uddin
  • 41
  • 7
  • Is preprocessing of the polygons allowed ? –  May 21 '15 at 12:26
  • Note that your approach is wrong. You can very well have a polygon intersecting the box with no box vertex inside the polygon. –  May 21 '15 at 12:30

1 Answers1

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.

Anders Schou
  • 184
  • 1
  • 13
  • 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 May 19 '15 at 14:41
  • 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. – Aleem Uddin May 19 '15 at 15:20
  • Do you need to actual intersection point? Or do you just need to know where if they intersect. – Anders Schou May 19 '15 at 18:18
  • i just want to if they intersect or not (true or false) – Aleem Uddin May 19 '15 at 18:30
  • assuming you're in 2D, look at http://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. – Anders Schou May 19 '15 at 19:43
  • According to that logic i need to take each side of my polygon and check whether it is intersecting with my bounding box edges, if it intersects return true right ? – Aleem Uddin May 19 '15 at 20:06
  • Yes. As you're just interested in a true/false result, remember to break after the first intersection. – Anders Schou May 20 '15 at 06:35
  • of course i am doing that only ...see i have polygons(cities) and i have some areal bounding box and i want to know how many cities(polygons) my box is touching ..see i have to return true, even if my whole box is inside polygon (here no intersection is happening b/w polygon and box). – Aleem Uddin May 20 '15 at 06:47
  • "If the two bounding volumes intersect, you will naturally have an intersection": not always. –  May 21 '15 at 12:31