Find intersections between polygon and horizontal line

Question

I have a polygon and a given point. I need to find the points on the polygon with the same Y-coordinate as the given point. See attachment: The given point is the red point and the blue points are the points that I am looking for (points that have the same Y as the given points).

At this point of time, I know to solve it by going over the polygon sections and check if the given point Y value relays within that section. After I find the included sections, I just run a simple equation to find the intersections. However! I am looking to find a better and simpler way to solve it, maybe an existing formula for that?

Thanks!

Answer 1

I assume preprocessing is allowed.

First decompose the polygon in monotone chains: consider all sides in turn and chain all those going in the same direction (up or down). You can ignore the horizontal sides.

There will be at best two chains (always two for convex polygons), and at worst N-1 or N of them (depending on the parity on N) if you are really unlucky. On average, four or so.

Note that the vertices in a chain are ordered by increasing or decreasing Y (sorting "for free").

Now for a given test point, locate it on Y by dichotomy, say between Yi and Yi+1. Then the intersection is given by X = Xi + (Y - Yi).(Xi+1 - Xi) / (Yi+1 - Yi).

This procedure will require O(N) preprocessing time and at worst O(N) storage; the query time will be O(K.LgL), where K is the number of chains and LgL the average logarithm of the chain length.

This is not optimal nor isotropic, but it is pretty simple to program and has little overhead.

Answer 2

Here is a solution which uses O(n log n) time for preprocessing and O((log n)^2 + cnt) per query, where cnt is a number of intersections. It works for any polygon.

1)Preprocessing: Store each segment as a pair(low_y, high_y). Sort them by low_y. Now it is possible to build a two dimensional segment tree where the first dimension is low_y and the second dimension is high_y. It can take O(n log n) space and time if done properly(one can keep a sorted vectorof high_y values for each segment tree node which contains those and only those high_y values which correspond to this particular node).

2)Query: It can rephrased in the following way: find all such segments(that is, pairs) which satisfy low_y <= query_y <= high_y condition. To find all such segments, one can traverse the segment tree and decompose a range [min(low_y), query_y] into a union of at most O(log n) nodes(here only the first dimension is considered). For a fixed node, one can apply a binary search over the sorted high_y vector to extract only those segments which satisfy low_y <= query_y <= high_y condition(the first inequality is true because of the way the tree is traversed, so we need to check high_y only). Here we have O(log n) nodes(due to the properties of a segment tree) and a binary search takes O(log n) time. So this step has O((log n)^2 time complexity. After the smallest high_y is found with binary search, it is clear that the tail of the vector(from this position to the end) contains those and only those segments which do intersect with the query line. So one can simply iterate over them and find the intersection points. This step takes O(cnt) time because a segment is checked if and only if it intersects with the line(cnt - total numner of intersections between the line and the polygon). Thus, the entire query has O((log n)^2 + cnt) time complexity.

3)There are actually at least two corner cases here:
i)a point of intersection is a common point of two adjacent polygon sections and
ii)a horizontal section,
so they should be handled carefully depending on what is the desired output for them(for example, one can ignore horizontal edges completely or assume that a whole edge is an intersection).