Я использовал код, который был отправлен here. Вот код снова:Обнаружение, если два сегмента линии пересекаются, используя Cramer
from __future__ import division
def line(p1, p2):
A = (p1[1] - p2[1])
B = (p2[0] - p1[0])
C = (p1[0]*p2[1] - p2[0]*p1[1])
return A, B, -C
def intersection(L1, L2):
D = L1[0] * L2[1] - L1[1] * L2[0]
Dx = L1[2] * L2[1] - L1[1] * L2[2]
Dy = L1[0] * L2[2] - L1[2] * L2[0]
if D != 0:
x = Dx/D
y = Dy/D
return x,y
else:
return False
# Usage
L1 = line([0,1], [2,3])
L2 = line([2,3], [0,4])
R = intersection(L1, L2)
if R:
print "Intersection detected:", R
else:
print "No single intersection point detected"
Он реализует правило Крамера (приспособленный для линий, если определитель линейного уравнения, построенного для двух заданных строк равно 0, то линии не пересекаются). Однако проблема, с которой я сталкиваюсь, заключается в том, что она также обнаруживает пересечения, которые являются результатом продолжения двух линий. Вот сюжет я сделал с помощью matplotlib, который демонстрирует проблему:
У меня также есть Triangle класса, который содержит 3 Line объектов и демонстрирует проблему еще дальше, так как класс также имеет свой собственный intersect(...) функция, которая принимает другой треугольник и проверяет, какие ребра обоих треугольников пересекаются и где:
Я хочу, чтобы обнаружить пересечение сегмента линии с использованием алгоритма из ссылки. Вышеуказанные сегменты линии не имеют пересечение. Как мне это сделать?
У меня есть два класса - Point и Line - которые используются для работы с этими геометрическими элементами более читабельным способом. Я сохранил выше сценарий и обернутый вокруг него (см Line.intersect(...)):
class Point:
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
# Override __add__, __sub__ etc. to allow arithmetic operations with Point objects
# ...
class Line:
def __init__(self, p1, p2):
self.p1 = p1
self.p2 = p2
# ...
def intersect(self, l):
def line(p1, p2):
A = (p1.y - p2.y)
B = (p2.x - p1.x)
C = (p1.x*p2.y - p2.x*p1.y)
return A, B, -C
L1 = line(self.p1, self.p2)
L2 = line(l.p1, l.p2)
D = L1[0]*L2[1] - L1[1]*L2[0]
Dx = L1[2]*L2[1] - L1[1]*L2[2]
Dy = L1[0]*L2[2] - L1[2]*L2[0]
if D != 0:
x = Dx/D
y = Dy/D
p = Point(x, y)
return True, p
return False, None
#Usage
l1 = Line(Point(0, 0), Point(10, 4))
l2 = Line(Point(-4, -3), Point(-4, 10))
res, p = l1.intersect(l2)
if not res:
print('Lines don\'t intersect')
else:
print('Lines intersect at [%f, %f]' % (p.x, p.y))
Я также ищет оптимального (как в качестве немногих, не дорогостоящие операции с наименьшим количеством памяти след, как это возможно) решения.
Одним из возможных решений является фильтрация полученных точек пересечения (те, которые не являются частью обоих сегментов), используя эвклидовое расстояние, чтобы определить, лежат ли эти точки на обоих сегментах или нет. Если нет, то пересечение является результатом продолжения одной или обеих линий и должно считаться недействительным. Это, однако, дорогостоящая операция, а также включает в себя все точки пересечения (независимо от того, является ли точка частью обоих сегментов или нет).
UPDATE: Я думал, что я решил эту проблему, но увы! следующее имеет проблему. Посмотрев внимательно на комментарии, которые я видел один сделанный @JerryCoffin, который указал на возможный дубликат с this post:
def intersect(self, l, contious=False):
# Before anything else check if lines have a mutual abcisses
interval_1 = [min(self.p1.x, self.p2.x), max(self.p1.x, self.p2.x)]
interval_2 = [min(l.p1.x, l.p2.x), max(l.p1.x, l.p2.x)]
interval = [
min(interval_1[1], interval_2[1]),
max(interval_1[0], interval_2[0])
]
if interval_1[1] < interval_2[0]:
print('No mutual abcisses!')
return False, None
# Try to compute interception
def line(p1, p2):
A = (p1.y - p2.y)
B = (p2.x - p1.x)
C = (p1.x*p2.y - p2.x*p1.y)
return A, B, -C
L1 = line(self.p1, self.p2)
L2 = line(l.p1, l.p2)
D = L1[0]*L2[1] - L1[1]*L2[0]
Dx = L1[2]*L2[1] - L1[1]*L2[2]
Dy = L1[0]*L2[2] - L1[2]*L2[0]
if D != 0:
x = Dx/D
y = Dy/D
p = Point(x, y)
if contiuous: # continuous parameter allows switching between line and line segment interception
return True, p
else:
if p.x < interval[1] or p.x > interval[0]:
print('Intersection out of bound')
return False, None
else:
return True, p
else:
print('Not intersecting')
return False, None
Результат:
, который выглядит красиво и точно, что я хочу иметь. Однако Я добавил строку (координаты были более или менее случайными, но легко для меня проверить график), а именно Line(Point(-4, 12), Point(12, -4)). И представьте себе мое удивление, когда я еще раз один ложный положительный результат получил:
Как вы можете видеть, что пересечение обнаруживается в верхнем левом углу в начале своего сегмента.Он действительно пересекает с продолжением вертикальной линии , но не с фактическим отрезком линии. Похоже, что оба сегмента линии имеют одинаковые x, в то время как один из них является вертикальным. Поэтому я до сих пор не знаю, как решить проблему.