Given a set P of (possibly overlapping) polygons and a line segment C determine whether all points of C belong to P

Question

Imagine a set of (continious and enclosed) shapes on a plane and 2 points somewhere there. I need an algorithm to verify that it's possible to traverse from 1 point to another without ever leaving the interior of the set. The shapes can overlap, and in the simplest case, when no two shapes overlap each other, apparently the path exists only if both points belong to a single shape and do not cross it's border. But if some shapes do overlap, it seems tricky to check whether the path between two points crosses any "gaps" between shapes or just traverses from one shape to another.

The scheme to illustrate the condition. Green lines pass the check, red don't

For the sake of simplicity we can approximate shapes as polygons. The crucial part of my problem is that I can't and don't want to merge shapes (reasons are justified by the way they are described/stored), especially given that there are options when the merge produces a "multipolygon" with holes, which also doesn't make the problem easier. So I need an algo which doesn't involve any mutations on the source data and operates directly on cartesian values of polygon bounds.

Answer 1

Finally solved with ChatGPT. After some "discussion" we came up with the algorithm:

1. Define a line segment C with its start and end points.
2. Initialize an empty list to store the intersection points and their original polygons.
3. For each polygon in the set P, do the following:
   1. Check if both ends of C lie within the polygon. If both ends of C lie within the polygon, then C is considered to be within P and the algorithm can stop.
   2. If either end of C does not lie within the polygon, check if C intersects any of the sides of the polygon. If C intersects a side of the polygon, push a tuple containing the intersection point and the current polygon into the list.
   3. If C does not intersect any sides of the polygon and neither end of C lies within the polygon, move on to the next polygon in P.
4. If the list is empty, then C is not considered to be within P.
5. If the list is not empty, do the following:
   1. Sort the intersection points in order along C, removing possible duplicates (which occure when C intersects a polygon at one of its vertices).
   2. Initialize a flag within to true.
   3. While the list is not empty, do the following:
      1. Pop the first intersection point and the polygon from the list.
      2. If there is next intersection point on the list, check if there is at least one polygon in P, that contains both it and the current intersection point. If there is none, then this segment does not lie completely within P, set within to false and stop processing the list.
      3. If there is no next intersection point on the list, than check if there are at least one polygon in P (excluding the one just popped), which contain that point. If there is none, set within to false and stop processing the list.
   4. If within is true, then C is considered to be within P. If within is false, then C is not considered to be within P.

It seems to work perfectly for convex polygons, but I need to do more testing with concave ones. It (the AI) also provided some (pretty obvious) points of improvement with some particular references I found useful:

1. Use an efficient point-in-polygon algorithm: The point-in-polygon algorithm is used to determine whether a point lies within a polygon. There are several algorithms that can be used for this purpose, such as ray casting, winding number, and even-odd rule. You may want to consider using an algorithm that has a low time complexity, such as ray casting, in order to ensure that the algorithm runs efficiently.
2. Use an efficient line-polygon intersection algorithm: The line-polygon intersection algorithm is used to determine whether a line segment intersects any of the sides of a polygon. There are several algorithms that can be used for this purpose, such as the line-line intersection algorithm and the Cohen-Sutherland line clipping algorithm. You may want to consider using an algorithm that has a low time complexity, such as the line-line intersection algorithm, in order to ensure that the algorithm runs efficiently.
3. Use an efficient sorting algorithm: The algorithm involves sorting the intersection points in order along C. There are several sorting algorithms that you could use for this purpose, such as quicksort, merge sort, and heap sort. You may want to consider using an algorithm that has a low time complexity, such as quicksort or merge sort, in order to ensure that the algorithm runs efficiently.
4. Use data structures that are optimized for performance: The algorithm involves storing the intersection points and their original polygons in a list or a stack. You may want to consider using a data structure that is optimized for performance, such as a dynamic array or a linked list, in order to ensure that the algorithm runs efficiently.

The humanity is doomed, it seems, but I finally find my satisfaction.