Überlappende Liniensegmente im 2D-Raum

Question

Ü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.

language-agnostic line geometry

user2483744 17.06.2013, 13:35

quelle

7 Antworten

Tags und Links language-agnostic line geometry

Django: Verwenden von Annotate, Count und Distinct in einem Queryset jQueryValidate - Pflichtfeld - hängt nicht ab

score 9 · Answer 1

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.

score 1 · Answer 2

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

score 1 · Answer 3

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

Sortieren Sie die Scheitelpunkte in der Reihenfolge im Uhrzeigersinn um den Ursprung.
Die Linien überlappen, wenn die geordneten Scheitelpunkte zwischen den zwei Segmenten wechseln, z. Line1.Point1, Line2.Point1, Line1.Point2, Line2.Point2.

score 1 · Answer 4

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);

score 1 · Answer 5

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

score 0 · Answer 6

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 ₁ & 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 ₁ 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.

score 0 · Answer 7

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%