CODEWITHSUNDEEP
pythonpolygongeospatialspatial
SriK
SriK

Reputation: 1121

Finding Intersections Region Based Trajectories vs. Line Trajectories

I have two trajectories (i.e. two lists of points) and I am trying to find the intersection points for both these trajectories. However, if I represent these trajectories as lines, I might miss real world intersections (just misses).

What I would like to do is to represent the line as a polygon with certain width around the points and then find where the two polygons intersect with each other.

I am using the python spatial library but I was wondering if anyone has done this before. Here is a picture of the line segments which don't intersect because they just miss each other. Below is the sample data code that represents the trajectory of two objects.

enter image description here

enter image description here

object_trajectory=np.array([[-3370.00427248,  3701.46800775],
   [-3363.69164715,  3702.21408203],
   [-3356.31277271,  3703.06477984],
   [-3347.25951787,  3704.10740164],
   [-3336.739511  ,  3705.3958357 ],
   [-3326.29355823,  3706.78035903],
   [-3313.4987339 ,  3708.2076586 ],
   [-3299.53433345,  3709.72507366],
   [-3283.15486406,  3711.47077376],
   [-3269.23487255,  3713.05635557]])
target_trajectory=np.array([[-3384.99966703,  3696.41922372],
   [-3382.43687562,  3696.6739521 ],
   [-3378.22995178,  3697.08802862],
   [-3371.98983789,  3697.71490469],
   [-3363.5900481 ,  3698.62666805],
   [-3354.28520354,  3699.67613798],
   [-3342.18581931,  3701.04853915],
   [-3328.51519511,  3702.57528111],
   [-3312.09691577,  3704.41961271],
   [-3297.85543763,  3706.00878621]])
plt.plot(object_trajectory[:,0],object_trajectory[:,1],'b',color='b')
plt.plot(vehicle_trajectory[:,0],vehicle_trajectory[:,1],'b',color='r')

Upvotes: 2

Views: 1542

Answers (2)

SriK
SriK

Reputation: 1121

Turns out that the shapely package already has a ton of convinience functions that get me very far with this. 

from shapely.geometry import Point, LineString, MultiPoint
# I assume that self.line is of type LineString (i.e. a line trajectory)
region_polygon = self.line.buffer(self.lane_width)
# line.buffer essentially generates a nice interpolated bounding polygon around the trajectory.
# Now we can identify all the other points in the other trajectory that intersects with the region_polygon that we just generated. You can also use .intersection if you want to simply generate two polygon trajectories and find the intersecting polygon as well.
is_in_region = [region_polygon.intersects(point) for point in points]

Upvotes: 0

Jeremy McGibbon
Jeremy McGibbon

Reputation: 3775

Let's say you have two lines defined by numpy arrays x1, y1, x2, and y2.

import numpy as np

You can create an array distances[i, j] containing the distances between the ith point in the first line and the jth point in the second line.

distances = ((x1[:, None] - x2[None, :])**2 + (y1[:, None] - y2[None, :])**2)**0.5

Then you can find indices where distances is less than some threshold you want to define for intersection. If you're thinking of the lines as having some thickness, the threshold would be half of that thickness.

threshold = 0.1
intersections = np.argwhere(distances < threshold)

intersections is now a N by 2 array containing all point pairs that are considered to be "intersecting" (the [i, 0] is the index from the first line, and [i, 1] is the index from the second line). If you want to get the set of all the indices from each line that are intersecting, you can use something like

first_intersection_indices = np.asarray(sorted(set(intersections[:, 0])))
second_intersection_indices = np.asarray(sorted(set(intersections[:, 1])))

From here, you can also determine how many intersections there are by taking only the center value for any consecutive values in each list.

L1 = []
current_intersection = []
for i in range(first_intersection_indices.shape[0]):
    if len(current_intersection) == 0:
        current_intersection.append(first_intersection_indices[i])
    elif first_intersection_indices[i] == current_intersection[-1]:
        current_intersection.append(first_intersection_indices[i])
    else:
        L1.append(int(np.median(current_intersection)))
        current_intersection = [first_intersection_indices[i]]
print(len(L1))

You can use these to print the coordinates of each intersection.

for i in L1:
    print(x1[i], y1[i])

Upvotes: 1

Related Questions