Блог

Я работаю над задачей (с python3), которая должна проверить, перекрываются ли 2 отрезка линии, и может ли вернуть 2 конечные точки. Отрезок прямой имеет координаты в форме (x1, y1, x2, y2), которые (x1,y1) и (x2,y2) являются координатами его конечных точек. 2 линии расположены довольно близко друг к другу, но могут быть не параллельными. Вы можете посмотреть картинку, чтобы понять, какой случай называется перекрытием. Я думаю, что определение перекрытия можно сказать «если проекция одной точки лежит между 2 конечными точками другой линии» Пример:

 overlap1 = numpy.array([[1,4,5,5], [7,7,3,5]])
overlap2 = numpy.array([[8,1,12,2], [9,2,11,3]])

non_overlap = numpy.array([[1,2,5,3], [6,3,9,4]])
 

Моя цель-найти 2 самые дальние точки из 4 точек, если они перекрываются, как показано красным кружком на изображении. В настоящее время моя идея заключается в следующем:

1. вычислите расстояние от всех точек (AB, AC, AD, BC, BD, CD) и проверьте, чтобы найти максимальное расстояние, называемое max_len
2. Вычислить: тест = len_AB len_CD — max_len
3. Если тест > 0, они перекрываются, в противном случае это не так

Этот алгоритм довольно хорошо работает для проверки условия перекрытия, но трудно вернуть 2 самые конечные точки.

Что вы думаете об этой проблеме? Спасибо.

Рассмотрим следующий код для вычисления относительного положения проекции точки (xp, yp) на (x1y1-x2y2) отрезок прямой. Он использует точечное (скалярное) произведение.

Возвращает None , когда сегмент действительно является точкой

Возвращает параметр 0..1 , когда проекция лежит внутри сегмента

Возвращает значения за пределами этого интервала, если проекция лежит на линии за пределами сегмента. Поэтому отрицательные значения и > 1 предназначены для ваших точек, обведенных красным кружком.

(картинка с названиями других точек)

 def proj(x1, y1, x2, y2, xp, yp):
    x12 = x2 - x1
    y12 = y2 - y1
    dotp = x12 * (xp - x1)   y12 * (yp - y1)
    dot12 = x12 * x12   y12 * y12
    if dot12:
        return dotp / dot12
    else:
        return None
 

Спасибо, что прочитали мой вопрос. Я думаю, что это больше проблема математики, чем программирования, но через некоторое время я нашел хороший простой алгоритм для ее решения. Мое решение в значительной степени основано на массиве numpy в python для эффективного расчета. Я не уверен, что есть лучший способ с более математическим подходом, но, надеюсь, это решение все еще будет полезно в будущем.

Идея состоит в том, чтобы найти расстояние от всей комбинации точек (есть 6 расстояний от 4 точек). Я создаю массив numpy из этой комбинации, нахожу евклидово расстояние, нахожу максимальное расстояние от него и проверяю перекрытие по условию: len_AB len_CD — max(расстояние).

 import numpy as np
def check_overlap(line1, line2):
    combination = np.array([line1,
                         line2,
                         [line1[0], line1[1], line2[0], line2[1]],
                         [line1[0], line1[1], line2[2], line2[3]],
                         [line1[2], line1[3], line2[0], line2[1]],
                         [line1[2], line1[3], line2[2], line2[3]]])
    distance = np.sqrt((combination[:,0] - combination[:,2])**2   (combination[:,1] - combination[:,3])**2)
    max = np.amax(distance)
    overlap = distance[0]   distance[1] - max
    endpoint = combination[np.argmax(distance)]
    return (overlap >= 0), endpoint
 

Похоже, вы просто используете координаты x, поэтому, если A<C<B<D или A<C<D<B ик перекрывается, в противном случае это не так (например, A<B<C