2010-05-11 11 views
5

Ich weiß, es gibt viele Algorithmen, um zu überprüfen, ob zwei Liniensegmente geschnitten werden.Zwei parallele Liniensegmente Kreuzung

Die Liniensegmente, von denen ich spreche, sind eine Länge, die aus 2 Endpunkten besteht.

Aber sobald sie parallelen Zustand angetroffen haben, sagen sie nur dem Benutzer ein großes "Nein" und
so tun, als ob es keine Überlappung, gemeinsame Endpunkt oder Endpunkt Kollusion gibt.

Ich weiß, dass ich den Abstand zwischen 2 Linien Segmenten berechnen kann.
Wenn der Abstand 0 ist, überprüfen Sie die Endpunkte in den anderen Liniensegmenten oder nicht.
Und das bedeutet, ich muss eine Menge von wenn sonst und & & || verwenden Bedingungen.

Dies ist nicht schwierig, aber meine Frage ist

„Gibt es einen Trick (oder Mathematik) Methode, um diesen speziellen Parallelfall zu berechnen?“

Ich hoffe, das Bild meiner Frage http://judark.myweb.hinet.net/parallel.JPG

+0

Was genau suchen Sie? Per Definition schneiden sich parallele Linien niemals. – Tyler

+0

Parallele Linien kreuzen sich nie, es sei denn, der Abstand ist 0. Aber da ihre Entfernung 0 ist, werden sie überlagert. Meine Frage betrifft jedoch die Liniensegmente. Die gestreckten Linien überlappen sich, aber die Liniensegmente bleiben unbekannt. Also versuche ich eine Lösung zu suchen, um das Unbekannte zu enthüllen. – Judarkness

+0

Judarkness Sie müssen wahrscheinlich Ihre Frage ein wenig verfeinern. Was ist wichtig, wenn es Liniensegmente sind oder nicht, wenn wir nach Parallelität suchen? – WhirlWind

Antwort

4

Ja, für beide der Linien die Formeln
zu klären, zu testen, ob ihre Steigungen gleich sind. Wenn dies der Fall ist, sind die Linien parallel und schneiden sich niemals.

Wenn Sie Punkte auf jeder Linie haben, können Sie die slope formula verwenden.

Wenn beide senkrecht zur x-Achse sind, haben beide unendliche Steigungen, aber sie sind parallel. Alle Punkte auf jeder Linie haben gleiche x-Koordinaten.

Um mit Liniensegmenten umzugehen, berechnen Sie den Schnittpunkt und bestimmen dann, ob dieser Schnittpunkt für beide Segmente existiert.

+0

Oh mein. Ich denke, ich sollte besser die Charakteranforderung erfüllen. Ich lag falsch. = P –

+0

Haha ... * shuffles Füße * =) –

+0

@Chris ahh, nun, ich habe es auch getan;) – WhirlWind

0

Ich nehme an, der Fall, der Sie interessiert, ist, wo die beiden Liniensegmente parallel sind (wie durch Überprüfung der Steigung bestimmt, wie Whirlwind sagt), und Sie versuchen zu bestimmen, ob die beiden Segmente überlappen.

vielmehr über den Abstand zwischen den Zeilen als besorgniserregend, würde ich denken, der einfachste Weg, das zu tun, um, wenn entweder Endpunkt eines Segments innerhalb des anderen liegt:

if (segment_contains_point(segment_A, segment_B.start) || 
    segment_contains_point(segment_A, segment_B.end)) { 
     // lines overlap 
} 
+1

Dies ist genau das, was ich will, ich habe meine eigenen segment_contains_points() (in anderen Namen) Aber es ist viel zu ineffizient. Und ich muss es dreimal aufrufen, weil Segment B größer sein könnte und das gesamte Segment A enthält. Und ich möchte wissen, ob es eine bessere Lösung gibt? – Judarkness

0

Nehmen wir an, dass Sie zwei Linien beschrieben durch die Formeln a.x + b.y + c = 0 und d.x + e.y + f = 0. Die zwei Linien sind parallel, wenn a = 0 and d = 0 oder b/a = e/d. Vielleicht, anstatt die Division zu machen, stellen Sie einfach sicher, dass b.d = a.e.

0

fand ich dies (ein wenig von mir geändert entsprechen) es wird die intercetion x, y sonst zurückgeben, wenn kein intercetion es -1 kehrt gefunden, -1

Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point 
    '// Determines the intersection point of the line segment defined by points A and B 
    '// with the line segment defined by points C and D. 
    '// 
    '// Returns YES if the intersection point was found, and stores that point in X,Y. 
    '// Returns NO if there is no determinable intersection point, in which case X,Y will 
    '// be unmodified. 

    Dim distAB, theCos, theSin, newX, ABpos As Double 

    '// Fail if either line segment is zero-length. 
    If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1) 

    '// Fail if the segments share an end-point. 
    If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1) 

    '// (1) Translate the system so that point A is on the origin. 
    bx -= ax 
    by -= ay 
    cx -= ax 
    cy -= ay 
    dx -= ax 
    dy -= ay 

    '// Discover the length of segment A-B. 
    distAB = Math.Sqrt(bx * bx + by * by) 

    '// (2) Rotate the system so that point B is on the positive X axis. 
    theCos = bx/distAB 
    theSin = by/distAB 
    newX = cx * theCos + cy * theSin 
    cy = cy * theCos - cx * theSin 
    cx = newX 
    newX = dx * theCos + dy * theSin 
    dy = dy * theCos - dx * theSin 
    dx = newX 

    '// Fail if segment C-D doesn't cross line A-B. 
    If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1) 

    '// (3) Discover the position of the intersection point along line A-B. 
    ABpos = dx + (cx - dx) * dy/(dy - cy) 

    '// Fail if segment C-D crosses line A-B outside of segment A-B. 
    If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1) 

    '// (4) Apply the discovered position to line A-B in the original coordinate system. 
    '*X=Ax+ABpos*theCos 
    '*Y=Ay+ABpos*theSin 

    '// Success. 
    Return New Point(ax + ABpos * theCos, ay + ABpos * theSin) 
End Function 

Origin

+0

Dies löst nicht die Frage, ob sich kolineare Liniensegmente überlappen - tatsächlich sagt es in den Kommentaren zu diesem Code, dass es für kollineare (und parallele) Linien fehlschlägt: // Fail, wenn die Segment-CD keine Linie kreuzt AB –

0

Ich habe gerade das gleiche Problem: Der einfachste Weg, den ich habe, nur um zu überprüfen, ob die Linien überlappen: Angenommen die Segmente sind kolinear (parallel und haben den gleichen Schnittpunkt mit der x-Achse). Nehmen Sie einen Punkt A vom längeren Segment (A, B) als Startpunkt. Finden Sie nun den Punkt unter den anderen drei Punkten, der den minimalen Abstand zum Punkt A hat (quadrierter Abstand ist besser, sogar Manhattan-Länge könnte auch funktionieren). Messen Sie den Abstand in Richtung B. Wenn der nächste Punkt zu A B ist, dann Linien kreuzen sich nicht. Wenn es zu dem anderen Segment gehört, tun sie es. Vielleicht müssen Sie für spezielle Fälle wie Null-Zeilen oder identische Linien überprüfen, aber das sollte einfach sein.

Verwandte Themen