使用Cramer检测两个线段是否相交 [英] Detect if two line segments intersect using Cramer
问题描述
我使用了
我也有一个 Triangle 类，其中包含3个 Line 对象，它进一步说明了这个问题，因为该类还具有自己的 intersect（...）函数，该函数采用另一个三角形并检查三角形的哪些边两个三角形都相交，并且在其中：
I想要使用链接中的算法检测线段交点。上面的线段不没有交点。我该怎么做？
我有两个类- Point 和 Line -用于以更易读的方式处理这些几何元素。我维护了上面的脚本并将其包裹起来（请参见 Line.intersect（...））：
类点：$ b $ b def __init __（self，x，y，z）：
self.x = x
self.y = y
self.z = z
＃覆盖__add __，__ sub__等，以允许使用Point对象
＃...
类行进行算术运算：
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 =行（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]
如果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 =直线（Point（-4，-3），Point（-4，10））
res，p = l1.intersect （l2）
如果不是res：
print（'线不相交'）
else：
print（'线在[％f，％f]相交'％（px，py））
我也在寻找最优值（如解决方案。
一种可能的解决方案是过滤掉结果相交点（不是两个部分的一部分）通过使用欧几里得距离来确定这些点是否同时位于两个线段上。如果不是，则相交是一条线或两条线连续的结果，应视为无效。但是，这是一项成本很高的操作，并且还需要考虑所有相交点（无论该点是否为两个线段的一部分）。
更新：我以为我已经解决了问题，可惜！以下有问题。在仔细查看评论之后，我看到了@JerryCoffin发表的评论，他指出可能与
这看起来不错，而且正是我想要的。 但是我添加了一条线（坐标或多或少是随机的，但对我来说很容易检查），即 Line（Point（-4，12），Point（12 ，-4））。想象一下当我再次得到一个误报时，我会感到惊讶：
如您所见，在我的线段开始处的左上角检测到一个相交。实际上，它确实与垂直线的延续相交，但与实际线段不相交。似乎两个线段都具有相同的 x ，而垂直线段却是一个问题。因此，我仍然不知道如何解决该问题。
嗯，一个人需要学习如何阅读...解决方案实际上是在@JerryCoffin提出的重复建议中的评论中，即
I have used the code that has been posted here. Here is the code again:
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"
It implements the Cramer rule (adapted for lines; if determinant of the linear equation built for two given lines is 0 then the lines are not intersecting). However the problem I'm having with it is that it also detects intersections that are a result of the continuation of the two lines at hand. Here is a plot I've made using matplotlib which demonstrates the issue:
I also have a Triangle class which contains 3 Line objects and it demonstrates the issue even further since the class also has its own intersect(...) function which takes another triangle and checks which edges of both triangles are intersecting and where:
I want to detect line segment intersection using the algorithm from the link. The above line segments do not have an intersection. How do I do that?
I have two classes - Point and Line - that are used to work with these geometric elements in a more readable way. I have maintained the above script and wrapped around it (see 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))
I'm also looking for an optimal (as in as few non-costly operations with as few memory footprint as possible) solution.
One possible solution is filtering out the resulted intersection points (the ones that are not part of both segments) by using Euclidean distance to determine if these points are lying on both segments or not. If not, then the intersection is a result of the continuation of one or both lines and should be considered invalid. This is however a costly operation and also involves taking all intersection points (no matter if point is part of both segments or not) into consideration.
UPDATE: I thought I have solved the problem but alas! the following has a problem. After looking closely to the comments I saw one made by @JerryCoffin who pointed out a possible duplicate with 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
The result:
which looks nice and exactly what I want to have. However I added a line (the coordinates were more or less random but easy for me to check on the plot) namely Line(Point(-4, 12), Point(12, -4)). And imagine my surprise when I got yet again a single false positive:
As you can see there is an intersection detected at the top left corner at beginning of my line segment. It does indeed intersect with the continuation of the vertical line but not with the actual line segment. It seems that the fact that both line segments have the same x while the one being vertical poses an issue. So I'm still clueless how to solve the issue.
Well, one needs to learn how to read...The solution was actually in the comments in a duplicate suggestion made by @JerryCoffin namely here:
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
The result:
这篇关于使用Cramer检测两个线段是否相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
