Rectangle 27 0

algorithm Find intersections between polygon and horizontal line?


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).

Each segment has two dimensional nature. It is not possible to unify low_y and high_y. Or, at least I do not see a way to unify them correctly.

For one dimensional segment tree, it is necessary to maintain a list or a vector of edges for each node(because there can be more than one edge covering concrete y). It is O(n^2) space in the worst case(if all edges are long and cover almost the entire range).

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.

I'm confused... All you need is a plain ol' segment tree. (1) Construct it in O(nlog n) time. (2) Query it in O(log n + k) time per query, where k is the number of intervals that contain the query y co-ord.

No, every segment (here, every vertical extent of a polygon edge) will appear at exactly 1 node in the segment tree. (I had an explanation here of where that is, but it was wrong -- I trust the Wikipedia article though :) ) Here, its x co-ords can be stored in the same place (and treated as a black box by the segment tree functions).

We don't care about x co-ords at all though -- for each edge in the polygon, we can just store its y extent (pair of y co-ords) as a segment in the segment tree, with the x co-ords stored in 2 extra fields (i.e. fields that the segment tree doesn't care about).

Note