Poly / Line intersection

There are easy algorithms for intersecting a line with a convex poly. If you have concave (forgive spelling) polies, you can try dividing those in convex polies and intersecting with the convex polies.


If most of the time the line and the poly dont intersect, you can speed up the algorithms a lot by precalculating for each poly the center and the radius of a circle that encompasses all of the polies points. Then, you calculate the distance from the circle center (a 2d point) to your line (very fast). If this distance is greater than the circle radius, the poly doesnt intersect the line and you can skip to the next poly.