4
$\begingroup$

I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane.

  • the polygons are either convex or star-shaped with a non-singular kernel
  • if multiple polygons, they touch each other (have at least a side in common with another polygon of the set)
  • the point moves accoring to a phisical process, so it will not "jump" in the plane, but its movement in the plane will be continuous
  • another system will keep the point within the area defined by the union of said polygons, but this might occasionally fail
  • I need to know which polygon is bounding the point
  • Polygons are given in advance and output of a pre-process that can be expanded

I know these solutions, in particular the "draw a line starting from your point and count the intersections" and the "sum the angles for each subsequent pair of vertices and check if it is 2$\pi$", but:

  • both solutions require a lot of computation if one has complex polygons and several polygons
  • those solutions are for the general case, where there is no dynamics involved, but a static point in a static polygon.

Is there a computationally optimal solution for the scenario I am considering? I think that leveraging the solution of the previous timestep should help in skipping/avoiding some computations in the next cycle, meaning that a "full" solution needs to be computed only at initialization.

Or am I stuck with running a full check at each cycle?

$\endgroup$
4
  • 1
    $\begingroup$ One thing to note is that if the polygons are star shaped (and you know the star-point) you can do a single test in $O(\log n)$ instead of linear, by binary searching through the triangles defined by the star point and each edge. You can also preprocess all polygons to create a point-location data-structure. $\endgroup$
    – Tassle
    Jan 14 at 19:43
  • $\begingroup$ I think I get the main idea of your question, but some details aren't clear to me. Do you only want to know whether the point is inside some of the polygons, or do you also want to know in which polygon it is? Usually, these type of problems are analyzed in terms of preprocessing costs and query costs afterwards, with the idea that preprocessing is only executed once. Are the polygons given in advance, or do they also change frequently? $\endgroup$
    – Discrete lizard
    Jan 16 at 13:10
  • $\begingroup$ Efficient algorithms for points that move continuously is something that is studied in the field of kinetic data structures, but I'm not sure if your problem matches well with the assumptions made in that field. $\endgroup$
    – Discrete lizard
    Jan 16 at 13:10
  • $\begingroup$ Another idea: If you know in advance that your point will always be inside a bounding box, you can triangulate all the faces inside the polygons and outside the polygon but inside the bounding box. Then, you can precompute the value for each triangle and all you have to do for the point is detect when it moves to to another triangle. In the worst case, this takes $O(\log d)$ per step where $d$ is the degree of the vertices in this triangulation, since you need to inspect all triangles incident to a high degree vertex, but can use binary search. $\endgroup$
    – Discrete lizard
    Jan 16 at 13:28
1
$\begingroup$

I can list three candidate approaches. I'm not sure how to choose among them -- you might need to experiment among them to see which will work best in your situation.

Approach #1: sweepline algorithm

This can be solved with a straightforward application of a sweepline algorithm.

Sweep a vertical line from left to right, with increasing $x$-values. At any value of $x$, you'll have a binary search tree that, given $y$, lets you look up which polygon the point $(x,y)$ is contained in. There are two key ideas in sweepline algorithms: you only need one tree for each interval of $x$-values between two adjacent "events" (here each event is an intersection of two line segments from the exteriors of the polygons), so you only need only $O(n)$ binary search trees; and, each binary search tree differs from the previous one by a single insertion or deletion, so you don't need to store all of them separately, but you can store them jointly using a persistent data structure.

Now this makes it easy to solve your problem. At any moment in time, we know the $(x,y)$ position of the point and can look up which polygon it is contained in and a trapezoid inside that polygon it is contained in. As the point moves, once it leaves that trapezoid, we can query the data structure again. Each lookup into the data structure takes $O(\log n)$ time, so will be efficient.

Approach #2: Graph of polygons

As a precomputation, build an undirected graph of polygons, where each polygon is a vertex, and two polygons are joined by an edge if they are adjacent (overlap in a point or line segment). Store this graph in an adjacency list representation. Also, find the polygon that contains the initial position of the point by any algorithm (e.g., linear scan over all polygons).

Note that you can answer point-in-polygon queries (given a point and a polygon, is the point inside that polygon?) in time linear in the number of vertices of the polygon.

Now, the algorithm is simple. Watch the movement of the current point, and as soon as it leaves the current polygon, check which polygon it has moved into by doing a point-in-polygon query on each adjacent polygon. Thus, when it leaves the current polygon, the work is proportional to the number of neighboring polygons, not to the total number of polygons.

There are various optimizations and improvements available:

  • Optimization 1: We can speed up the process of finding when the point leaves the polygon it is currently inside. If we are guaranteed that once the point leaves a polygon, it will never come back to it, then we can use binary search over time to find the first instant when it has left the polygon. Each iteration of binary search requires one point-in-polygon query and we do logarithmically many iterations. If we don't have that guarantee, but we have an upper bound on the speed and/or acceleration and/or turning radius for the movement of the point, we can compute a lower bound on the time to leave the current polygon and return to it (based on the current position of the point and the polygon it is contained within), and use a modified binary search where we avoid jumping further into the future in any one step than given by that bound.

  • Optimization 2: We can sort each adjacency list. Consider the adjacency list for polygon $P$. Suppose the perimeter of $P$ has length $\ell$. If you walk along the perimeter of $P$ starting at some point on the perimeter and returning to it, this maps each point on the perimeter to a number in the range $[0,\ell)$, which gives a total order on points on the perimeter. This yields a total order on the polygons adjacent to $P$: map each neighboring polygon to the points of intersection on the perimeter of $P$, map those to numbers/intervals in $[0,\ell)$, then sort by that. (We can resolve ties as follows: if two neighboring polygons both overlap with $P$ at the same point $p$, where $p$ is on some face of $P$, then imagine extending outward by a tiny bit $\epsilon$ from that face and look at the intersection with those two polygons.) So, sort each adjacency list in this way, as part of the precomputation/setup phase.

    This now speeds up the process of determining which new polygon the point has entered, when it leaves the current one: instead of using a number of point-in-polygon tests that is linear in the number of neighboring polygons, it goes by the log of the number of neighboring polygons.

  • Optimization 3: Compute the bounding box for each polygon. Now, before doing a point-in-polygon test, you can first check whether the point is in the bounding box, which will enable quickly rejecting some polygons.

    You could also use this to speed up finding the polygon the initial position is within. Store all bounding boxes in some appropriate data structure (e.g., a quadtree). Now, given a point, use that data structure to enumerate all bounding boxes it is contained in, then test each with a point-in-polygon test.

Approach #3: Graph of triangles

During a precomputation, triangulate each polygon, i.e., decompose it into a union of triangles. Now combine all these triangles, build a graph of triangles, and proceed as in approach #2, but using triangles instead of objects.

This replaces each point-in-polygon test with a point-in-triangle test, which is much faster; but because the point will traverse many more triangles than polygons, the number of iterations might be much larger. I'm not sure which approach will be faster in the end.

Also, the type of triangulation used might affect performance. I'm not sure whether it is better to choose a triangulation that minimizes the variance of the degrees in the graph or one that maximizes the variance (e.g., a fan decomposition).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.