Fastest horizontal line <-> convex polygon intersection algorithm?

Question

Hi,

I need to solve a relatively simple thing -- I've got n-vertices convex 2D polygon and a horizontal (!) line with some 'y' coordinate. I need only one thing: to check if the polygon is crossed with this line (i.e. have 2 intersections) or not.

The fastest one I can think of is to find min/max y coordinates within a polygon (loop repeated n times with two compares and two stores) and then to compare if the min y <= y < max y.

Somehow I feel this could be solved more "mathematically" but I always end with slower code (for example vector way -- I need to compute differences for n[i] and n[i+1], then multiply them, add etc -- much slower then 2 cmps+stores).

Answer 1

You only need to check if your polygon has a point with y1 < y and one with y2 > y. As soon as you have found such two points, you're done. If you can index your points by the y-coordinate, that should be a fast lookup.

Answer 2

If it's a horizontal 2d line then yes, the method you've described is probably the fastest. You could short circuit it as well, as if you get partway through the check and have a min + max that are > and < your y value then you have an intersection.

Answer 3

If you have to do it on the raw each time, then you're probably not going to find any trick to make it faster than that.

If you can cache the min/max Y value with the polygon, then you can save time by not looping each vertex every time you do the test.

If your polygon has an aligned bounding box associated with it, you can test it against the box extents instead of the polygon and get the same result faster.