Effizienter Algorithmus für den kürzesten Abstand zwischen zwei Liniensegmenten in 1D

Question

Ich kann viele Formeln finden, um den Abstand zwischen zwei schrägen Linien zu bestimmen. Ich möchte den Abstand zwischen zwei Liniensegmenten berechnen in eine Dimension .

Das ist mit einer Reihe von IF-Anweisungen leicht zu bewerkstelligen. Aber ich habe mich gefragt, ob es eine effizientere mathematische Formel gibt.

Z.B. 1:

----L1x1-------L2x1-------L1x2------L2x2----------------------------

L1 = Linienabschnitt 1, L2 = Linienabschnitt 2; der Abstand ist hier 0, weil sich die Linien schneiden

Z.B. 2:

----L1x1-------L1x2-------L2x1------L2x2----------------------------

der Abstand ist hier L2x1 - L1x2

EDIT :

Die einzige Annahme ist, dass die Liniensegmente geordnet sind, d. h. x2 ist immer > x1.

Linienabschnitt 1 kann links, rechts, gleich usw. von Linienabschnitt 2 liegen. Der Algorithmus muss dies berücksichtigen.

EDIT 2:

Ich muss dies in T-SQL (SQL Server 2008) implementieren. Ich brauche nur die Logik... Ich kann die T-SQL schreiben.

EDIT 3:

Wenn ein Liniensegment ein Liniensegment der anderen Linie ist, ist der Abstand 0.

----L1x1-------L2x1-------L2x2------L1x2----------------------------

Der Linienabschnitt 2 ist ein Abschnitt des Linienabschnitts 1, so dass der Abstand 0 beträgt.

Wenn sie sich kreuzen oder berühren, ist der Abstand 0.

Answer 1

Diese Frage ist die gleiche wie die Frage "Schneiden sich zwei Bereiche, und wenn nicht, wie groß ist der Abstand zwischen ihnen?" Die Antwort hängt ein wenig davon ab, ob Sie bereits wissen, welcher Bereich der kleinste ist, und ob die Punkte in den Bereichen richtig angeordnet sind (d. h. ob die Linien die gleiche Richtung haben).

if (a.start < b.start) {
  first = a;
  second = b;
} else {
  first = b;
  second = a;
}

Dann:

distance = max(0, second.start - first.end);

Je nachdem, wo Sie das Programm ausführen, sollte Ihr Compiler es gut optimieren können. In jedem Fall sollten Sie wahrscheinlich ein Profil erstellen, um sicherzustellen, dass Ihr Code ein Engpass ist, bevor Sie ihn für eine theoretische Leistungssteigerung weniger lesbar machen.

Answer 2

Dies funktioniert in allen Fällen:

d = (s1 max s2 - e1 min e2) max 0

Als Bonus bedeutet das Entfernen von max 0, dass ein negatives Ergebnis genau angibt, wie viel der beiden Segmente sich überschneiden.

Proof

Beachten Sie, dass der Algorithmus symmetrisch ist, so dass asymmetrische Fälle nur einmal behandelt werden müssen. Ich werde also behaupten, dass s2 >= s1 ist. Beachten Sie auch, dass e1 >= s1 und e2 >= s2 ist.

Die Fälle:

• L2 beginnt nach dem Ende von L1 (s2 >= e1): s1 max s2 = s2, e1 min e2 = e1. Das Ergebnis ist s2 - e1, was nicht negativ ist und eindeutig der gewünschte Wert ist (der Abstand).
• L2 innerhalb von L1 (s2 <= e1, e2 <= e1): s1 max s2 = s2, e1 min e2 = e2. s2 - e2 ist durch s2 <= e2 nicht positiv, so dass das Ergebnis wie bei der Überschneidung erwartet 0 ist.
• L2 beginnt innerhalb von L1, endet aber nach (s2 <= e1, e2 >= e1): s1 max s2 = s2, e1 min e2 = e1. s2 - e1 ist bei s2 <= e1 nicht positiv, so dass das Ergebnis bei Überschneidung wie erwartet 0 ist.

Answer 3

Ich glaube nicht, dass es einen Weg gibt, die Bedingungen zu umgehen. Aber das ist kurz und bündig:

var diff1 = L2x1 - L1x2;
var diff2 = L2x2 - L1x1;

return diff1 > 0 ? max(0, diff1) : -min(0,diff2);

Dies setzt voraus, dass LNx1 < LNx2.

Answer 4

Ich denke, da alle Liniensegmente in der 1D eine der Formen (X,0) oder (0,Y) haben

so speichern Sie alle diese x-Werte in einem Array und sortieren Sie das Array und minimalen Abstand wird der Unterschied zwischen 1. 2 elemenst des Arrays.

Hier müssen Sie beim Speichern von Elementen im Array vorsichtig sein, damit keine doppelten Elemente gespeichert werden

Answer 5

Diese Formel scheint in allen Fällen zu funktionieren, außer in dem, in dem eine Linie vollständig auf der anderen Linie liegt.

return -min(a2-b1,b2-a1)