How do i check if two polygons hit each other?
like polygon1.contains(polygon2)
I cant find any Method in the api that does that
How do i check if two polygons hit each other?
like polygon1.contains(polygon2)
I cant find any Method in the api that does that
The easiest way is to check all the vertices of one polygon to see if they lie inside the other polygon using the contains( x, y ) method.
However, this method is slow O( n * m ), where poly1 has n vertices and poly2 has m vertices, and can give an incorrect result ( think about two triangles in a star of David type formation ).
The more complex way is use a sweep-line strategy to check if any of the polygon edges intersect. This method will find all cases of polygon intersection and runs in O( p * log p ) , where p = n + m.
If you google for “line intersection” and “sweep line” something may turn up. It is also detailed in “Introduction to Algorithms” by three guys whos names i can’t remember???, but their initials were C, L and R
If you don’t find anything, come back here and I’ll put up an explanation about how it works when i have more time.