Überlappende Liniensegmente im 2D-Raum

8

Ich muss herausfinden, ob zwei Linien einander überlappen. Ich habe den Schnittpunktcode, der 0 zurückgibt, wenn zwei Linien parallel sind. Aber dann muss ich wissen, ob diese zwei parallelen Linien überlappen.

Bearbeiten:

%Vor%

Zeile 1: A-B

Zeile 2: C-D

Ich muss herausfinden, ob Zeile 1 Zeile 2 überlappt, aber beide Zeilen können eine Steigung & gt; 0.

    
user2483744 17.06.2013, 13:35
quelle

7 Antworten

9

Sie können vergleichen, um festzustellen, ob es eine Überlappung gibt. Sie werden auf diese Weise weniger Vergleiche haben, also sehr effizient. Führen Sie folgende Vergleiche durch

D & lt; A

B & lt; C

Wenn einer der beiden Fälle wahr ist, überschneiden sich die Linien nicht. Ansonsten muss eine Überschneidung erfolgen. Sie werden die wenigsten Vergleiche durchführen, um festzustellen, ob sie sich nicht überschneiden. Andernfalls werden weitere Vergleiche angestellt.

    
Kishore 16.01.2014 17:19
quelle
1

Da Sie wissen, dass sie beide parallel sind, prüfen Sie einfach, ob die CD des Liniensegments einen der Endpunkte der ersten Zeile enthält (Punkt A und Punkt B).

    
Harrison Paine 17.06.2013 15:11
quelle
1

Für zwei kollineare Liniensegmente, die nicht unbedingt achsversetzt sind:

  1. Sortieren Sie die Scheitelpunkte in der Reihenfolge im Uhrzeigersinn um den Ursprung.
  2. Die Linien überlappen, wenn die geordneten Scheitelpunkte zwischen den zwei Segmenten wechseln, z. Line1.Point1, Line2.Point1, Line1.Point2, Line2.Point2.
mbeckish 17.06.2013 15:23
quelle
1

Es ist ausreichend, die Flächen der Dreiecke ACB und CBD zu berechnen. Wenn der Bereich 0 ist, sind die Punkte kollinear, und wenn beide Bereiche Null sind, überlappen sich die Linien.

Sie können die Fläche eines Dreiecks ABC nach folgender Formel berechnen:

2 * Fläche (ABC) = (bx - ax) (cy - ay) - (cx - ax) (by - ay);

    
user3412621 21.05.2014 12:04
quelle
1

Die Liniengleichung ist die Richtung der Linie in unendlicher Richtung. Wenn Sie eine Steigung oder einen Schnittpunkt finden, können Sie mit ihnen nichts anfangen (obwohl die horizontale Linie keine Steigung hat), ich empfehle den Punkt auf der Linie. Also ist AB deine Linie [(x, y), (x, y)] und C ist auf dem Punkt (x, y) und dann musst du prüfen, ob ein Punkt auf der Linie ist.
Kontrollpunkt in einer Zeile

    
Bear 06.04.2016 03:23
quelle
0

Wir haben zwei Liniensegmente

  

AB = Liniensegment von (A x, A y) bis (B x, B y) )   CD = Liniensegment von (CX, CY) bis (DX, DY)

























p>

mit der gleichen Steigung.

  • Ordne die Endpunkte E 1 & lt; E 2 <& lt; E & lt; 3 & lt; & lt; E 4, so dass E, x ≤ E i + 1, x und E i, y ≤ E i + 1, y, wenn E , x i + 1, x
  • Wenn E 1 und E <2> aus verschiedenen Segmenten stammen, ist die Überlappung das Segment von E2 bis E3 .

Es gibt einige degenerierte Fälle:

  • A & lt; B = C & lt; D
  • A & lt; C = D & lt; B
  • A & lt; B = C = D
  • A = B = C = D

Diese ergeben einen einzigen Schnittpunkt. Ich bin mir nicht sicher, ob einige davon in Ihrem System auftreten können, aber wenn dies der Fall ist, müssen Sie entscheiden, ob Sie dies als "Überlappung" betrachten und spezielle Fallüberprüfungen hinzufügen.

    
jerry 17.06.2013 16:20
quelle
0

Die Eigenschaft von zwei Segmenten, in denselben Linien zu sein, wird Kollinearität genannt und kann getestet werden, indem die Fläche der zwei Dreiecke berechnet wird, die durch die einen Segmentendpunkte bzw. die Endpunkte des anderen Segments gebildet werden. Wenn der Bereich unter einem Schwellenwert Null oder nahe Null ist, sind die Segmente kollinear.

%Vor%     
ceztko 27.02.2014 22:42
quelle