Find intersections between polygon and horizontal line
algorithm, computational-geometry, math, polygon
Solution
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 `vector`of `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).
Problem
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!