Поиск пересечений Траектории на основе областей и линейные траектории

У меня есть две траектории (т.е. два списка точек), и я пытаюсь найти точки пересечения для обеих этих траекторий. Однако, если я представлю эти траектории в виде линий, я могу пропустить пересечения в реальном мире (просто промахнусь).

Что я хотел бы сделать, так это представить линию как многоугольник с определенной шириной вокруг точек, а затем найти, где два многоугольника пересекаются друг с другом.

Я использую пространственную библиотеку python, но мне было интересно, делал ли кто-нибудь это раньше. Вот изображение сегментов линии, которые не пересекаются, потому что они просто не пересекаются друг с другом. Ниже приведен пример кода данных, который представляет траекторию двух объектов.

введите здесь описание изображения

введите здесь описание изображения

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')

python geospatial polygon spatial
person SriK    schedule 25.09.2017    source источник
comment
Что вы подразумеваете под представлением линии в виде многоугольника? Многоугольник состоит из линий. Вы имеете в виду, что хотите найти, где точки или линии между точками находятся в пределах определенного порога другой траектории?   -  person Jeremy McGibbon    schedule 25.09.2017
comment
Спасибо за разъяснение @JeremyMcGibbon. В основном я хочу конверт вокруг каждой строки. Конверт будет представлен в виде многоугольника. И тогда я могу определить, где две конверты пересекаются друг с другом, а затем провести дополнительный анализ этих точек пересечения. Рассмотрим сюжетное изображение. В этой ситуации ни одна из линий не пересекает друг друга, но в практической ситуации это происходит, потому что это не линия, а ширина. Это помогает?   -  person SriK    schedule 25.09.2017
comment
Насколько хорошо выбраны точки? Достаточно ли проверять наличие перекрытий только в непосредственной близости от точек или нужно также смотреть на траекторию между этими точками? А сколько у вас точек траекторий, как по порядку?   -  person Jeremy McGibbon    schedule 25.09.2017
comment
Я имею в виду, что если у нас есть две линии, в которых мы проверяем пересечения, необходимо ли вам проверять каждое возможное место на этой линии, или будет достаточно проверить только то, где у вас есть точка? Другой способ задать этот вопрос: как вы думаете, будет ли по крайней мере 1-2 точки от каждой из линий на каждом пересечении?   -  person Jeremy McGibbon    schedule 25.09.2017
comment
Давайте продолжим обсуждение в чате.   -  person SriK    schedule 25.09.2017
comment
Похоже, вы хотите буферизировать линии, а затем вычислить пересечение. Вероятно, можно использовать shapely: toblerity.org/shapely/manual.html   -  person Spacedman    schedule 25.09.2017
comment
Спасибо @Spacedman. Звучит интересно. Раньше я не замечал функцию буфера. Итак, в основном, я бы создал кучу буферизованных точек (повернутых вокруг угла траектории), а затем посмотрел, какие из другого набора точек пересекаются с буферизованными полигонами? Если у вас есть пример, хотелось бы его увидеть, иначе я тоже попробую.   -  person SriK    schedule 26.09.2017
comment
Вроде того, вы создаете буфер многоугольник (как сосиска) вокруг своей линии, при этом ширина буфера является вашим допуском. Если вы сможете отредактировать свой вопрос, включив в него некоторый код для создания образцов данных, я мог бы получить возможность поработать над ним.   -  person Spacedman    schedule 26.09.2017

Ответы (2)


arrow_upward
1
arrow_downward

Допустим, у вас есть две строки, определенные массивами numpy x1, y1, x2 и y2.

import numpy as np

Вы можете создать массив distances[i, j], содержащий расстояния между i точкой первой строки и j точкой второй строки.

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

Затем вы можете найти индексы, где distances меньше некоторого порога, который вы хотите определить для пересечения. Если вы считаете, что линии имеют некоторую толщину, порог будет равен половине этой толщины.

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

intersections теперь представляет собой массив N на 2, содержащий все пары точек, которые считаются «пересекающимися» ([i, 0] — это индекс из первой строки, а [i, 1] — это индекс из второй строки). Если вы хотите получить набор всех индексов из каждой пересекающейся строки, вы можете использовать что-то вроде

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

Отсюда вы также можете определить количество пересечений, взяв только центральное значение для любых последовательных значений в каждом списке.

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))

Вы можете использовать их для печати координат каждого перекрестка.

for i in L1:
    print(x1[i], y1[i])
person Jeremy McGibbon    schedule 25.09.2017
comment
Спасибо! Отличный альтернативный подход к поиску близких точек как приближенных к точкам пересечения двух полигонов. Одна проблема - если выборка точек несколько неудачна (поскольку интерполяция между точками не учитывается), этот подход может не найти пересечений, когда в действительности пересечения были бы. Это точно? - person SriK; 25.09.2017

arrow_upward
0
arrow_downward

Оказывается, в красивом пакете уже есть масса удобных функций, которые помогают мне в этом.

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]
person SriK    schedule 27.09.2017