J'ai utilisé le code qui a été affiché here. Voici le code à nouveau:Détecter si deux segments de ligne se croisent en utilisant 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"
Il met en œuvre la règle Cramer (adapté pour les lignes, si déterminant de l'équation linéaire construite pour deux lignes données est 0, les lignes ne sont pas sécantes). Cependant, le problème que j'ai avec lui est qu'il détecte également les intersections qui résultent de la continuation des deux lignes en cours. Voici un terrain que je l'ai fait à l'aide matplotlib qui démontre la question:
J'ai aussi une classe Triangle qui contient 3 Line objets et il démontre la question encore plus loin puisque la classe a également son propre intersect(...) fonction qui prend un autre triangle et vérifie que les bords des deux triangles se croisent et où:
je souhaite détecter intersection de segment de ligne en utilisant l'algorithme du lien. Les segments de ligne et ont une intersection. Comment je fais ça?
J'ai deux classes - Point et Line - qui sont utilisées pour travailler avec ces éléments géométriques d'une manière plus lisible. Je l'ai maintenu le script ci-dessus et enroulé autour de lui (voir 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))
Je cherche aussi une optimale (comme aussi peu coûteuses opérations non avec aussi peu empreinte mémoire possible) solution.
Une solution possible consiste à filtrer les points d'intersection résultants (ceux qui ne font pas partie des deux segments) en utilisant la distance euclidienne pour déterminer si ces points se trouvent sur les deux segments ou non. Si ce n'est pas le cas, l'intersection est le résultat de la continuation d'une ou des deux lignes et doit être considérée comme invalide. Ceci est cependant une opération coûteuse et implique également de prendre en compte tous les points d'intersection (peu importe si le point fait partie ou non des deux segments).
MISE À JOUR: Je pensais que je l'ai résolu le problème, mais hélas! ce qui suit a un problème. Après avoir examiné attentivement les observations que j'ai vu celle faite par @JerryCoffin qui a un double possible avec 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
Le résultat:
qui a l'air agréable et exactement ce que je veux avoir. Cependant J'ai ajouté une ligne (les coordonnées étaient plus ou moins aléatoire mais facile pour moi de vérifier sur l'intrigue) à savoir Line(Point(-4, 12), Point(12, -4)). Et imaginez ma surprise quand je suis arrivé encore une fois un faux positif:
Comme vous pouvez le voir il y a une intersection détectée dans le coin supérieur gauche au début de mon segment de ligne.Il croise en effet avec la suite de la ligne verticale mais pas avec le segment de ligne réel. Il semble que le fait que les deux segments de ligne aient le même x alors que celui qui est vertical pose problème. Donc je ne sais toujours pas comment résoudre le problème.