Check connection between two points on 2D plane

Question

SO,

The problem

I have a question about algorithm of determining if two points are connected on 2D-plane. I have:

• Array of 2D-lines. Each line is limited with its start end end 2D-point. Each point is simple array of two elements [x,y] - i.e. each line looks like ['start'=>[X0, Y0], 'end'=>[X1, Y1]] Let this lines set be named as L. Lines can belongs one to another (i.e. one could be part of another), they can be intersected by only one point e.t.c. - i.e. there are no restrictions for them on 2D plane. But line can not be a point - i.e. start of line can not be equal to end of line.
• Two points S and E, i.e. arrays [Xs, Ys] and [Xe, Ye]

Now, all lines from L are drawn on the plane. Then, S and E are also drawn and I need to answer the question - can E be reached from S without intersection of any lines in L? And, to be more specific - which algorithm will be optimal? By 'could be reached' I mean that there is a way on the plane from S to E without intersection any line from L - and, of cause, this way could be anything, not just line.

Sample

-as you see, in sample S and E are not connected. Also in the sample there is a case when one line fully belongs to another (gray and purple lines) - and a case when one line has a start/end on another line (green and rose lines).

My approach

Currently, I have non-deterministic polynomial (NP) algorithm to do that. It's steps are:

• Find all intersections for each pairs of lines.
• Create new set of lines from points of first step. If two lines has one intersection, then there will be 4 new lines with intersection point at the start of each new line - or it can be 3 new lines if first line has it's start/end on second line - or it can be 2 new lines if first line has it's start/end exactly match with second's line start/end. I.e:

so 1-st case will result in 4 new lines, 2-4 cases in 3 new lines and 5 case in 2 new lines. (lines are [A, B] and [C, D])

• Next, in lines step from 2-nd step I'm searching all polygons. Polygon is a closed line set (i.e. it holds closed part of area)
• I'm determining for S subset of such polygons that contain S. To do this, I'm using simple algorithm - counting number of intersections with polygon's edges and some line from S to outer plane (if it's odd, then S is inside polygon and if it's even - then outside). This is a ray-casting algorithm. Then I do that for E
• Now, when I have polygons set for both S and E I'm simply comparing both sets. If they are equal, then E could be reached from S and could not be - otherwise.

Why is this NP?

The answer is simple: on 3-rd step I'm performing search of all loops in 2D-graph. Since a problem of finding maximum/minimum loop length if NP, then mine is too (because I can get maximum/minimum loop length simply with sorting resulted loops set). Good information about this is located here.

The question

Since my current solution is NP, I want to know - may be my solution for the problem is an overkill? I.e. may be there are simpler solution which will result in polynomial time?

Answer 1

You can construct a so-called "Visibility graph" that connects two obstacle vertices iif they are directly visible. Shortest path in this graph (with S and E added) will be the shortest obstacle-free path between S and E in your configuration space. Algorithms and optimisations concerning Visibility Graph are well-known and widely described.

The main difficulty you'll have is handling corner cases so you can't "leak" in some improper intersection to the other side of the segment (shared segments, endpoint as intersection, etc). Handling such corner cases is not algorithmically difficult but requires patience.

EDIT:

So let me be more formal: build a graph G(Ver, Edg) where Ver contains all segment's endpoints, S and E; and Edg contains all pairs of vertices which are directly visible (including following the segment).

Answer 2

1. find all intersection between line segments
2. remove all points which have rank = 1; i.e. it's an end point, only one line-segment is connected to this point
3. find line-segment closest to point S
4. find polygon whose one side is previously found line segment, using following approach:
   1. starting line segment is given
   2. mark both ends of starting segment, starting = lsS, ending = lsE
   3. find all line segments connected to lsE, excluding starting segment
   4. from found segments choose that segment that is closest to point S closest line is the one, whose center is possible to connect with point S without intersecting any of examined lines
   5. remove all other examined line segments from problem space
   6. repeat until you have complete polygon
5. if complete polygon contains both points E and S, those are connected

It's a bit similar to depth first search.

In each step you only work with immediate neighbors of last point you successfully solved.

Answer 3

Compute the planar straight-line graph formed by the line segments and locate the faces to which S and E belong. There is a path if and only if S and E belong to the same face. The first two steps are standard, polynomial-time algorithms from computational geometry, with many descriptions and implementations available.

Answer 4

There are two steps to the algorithm.

1. Find out the maximum polyogn encompassing S and E 
    (which could possibly be an open polygon, so convex hull algorithm needs 
    to be modified)
2. E can be reached from S if
    (Case 1) The polygons are the same
    (Case 2) Both are open polygons.

Explanation:

Step 1: Find the maximum encompassing polygon of a point P

Form a set of points by adding the end-points and all possible 
    intersections. (O(n^2))
Eliminate points that can only be reached from P by crossing another line. 
    This can be done by finding the intersection of the line joining P to each 
    point with all other lines (O (n^3)).
Form a convex hull of the remaining points. 
    Here it should be noted that the resulting polygon may not be closed. 
    So, the convex hull algorithm needs to be modified to get rid of 
    those possible edges which don't have a direct connection. 
    This can be efficiently done by an appropriate data structure 
    like a graph (O(n^2) in worst case)

Step 2: Comparison would need some kind of sorting of the polygon vertices. This would be maximum O(n long n)

So the resulting algorithm complexity would be O (n^3)

Answer 5

Basically the problem boils down to:
1) Determine all of the polygons enclosing some space which don't contain any other polygon. In your above example, you have 3 shapes/cycles/polygons that do not contain any others: the quadrilateral containing S, the quadrilateral containing E, and the triangle below the 2 of them.
2) Determine if S and E are on opposite inside/outside of any of these polygons.

For part 1, you have to build a graph:

Create an array of intersection points of your given line, this is N^2. Remember which 2 lines each intersection point came from. These intersection points are the vertexes of your graph.

Two vertexes are "connected" if they are from the same line and there is no other intersection point between them. Don't rely on the accuracy of floating point to determine this, obviously.

Now you wish to find the polygons in your layout. A graph may in general contain an exponential number of cycles. However, each edge may only border 2 "inner" polygons, so we are only interested in a polynomial subset of the cycles. So pick an edge, then find the next edge in the polygon, and keep repeating until you get back to where you started or determine that the first edge wasn't part of a polygon.

So suppose you are coming from edge E = (U, V), and want to find the next edge in the polygon (sharing the same vertex V).
1) Create a vector T as U - V.
2) Create the set of edges A that are adjacent to vertex V. Remove E from that set.
3) If the set is empty, then the edge isn't part of a polygon.
4) For each edge (Q, V) in A, construct a vector R as Q - V. (Remember Q and V represent points in the 2D plane).
5) Normalize R : divide it by it's length to create a vector of length 1.
6) Determine CrossProductValue(T, R).
7) The edge in A with the least CrossProductValue is the next edge in one the adjacent polygons. The edge in A with the largest CrossProductValue is the next edge in the other polygon.

CrossProductChecker(2D T, 2D R) {
  return (T.x*R.y - T.y*R.x); // cross product for 2 dimensions
}

So use this to find your polygons. Lookup the relation between cross products and sinusoids to get an idea how this works.

============

Now that you have all of your polygons, all there is to do is check if there is one that S is inside of and E is outside of, or the other way around.

The easy way to do this is to draw a line from S to E. If it intersects any polygon (cycle from above) an even number of times, they are both inside or both outside the polygon so keep checking.

If the line intersects a cycle an odd number of times, then one is inside the polygon and one is outside, so you can say that there is no path.