Eine weitere kollineare Frage. Dieser Twist ist, ich verwende Integer-Arithmetik, und ich suche nach genau Collinearity, kein Fuzzy Epsilon-basierter Test.
Bei Inline-Assemblierung kann ich eine genaue Antwort erhalten: Die x86-Multiplikationsanweisung ermöglicht den Zugriff auf die beiden Teile des Produkts, die beide für die Berechnung des Kreuzprodukts wichtig sind ( X - A ) x ( B - A ); Ich kann einfach die beiden Hälften zusammenstellen und auf Null testen. Aber ich hoffe, dass es einen Weg gibt, es in C zu machen, nämlich:
ungefähr in dieser Reihenfolge. Und zur gleichen Zeit, ein Weg, es zu tun, ist / nicht:
double
Ich mache mir keine Gedanken darüber, ob X über das Segment AB hinausgeht. das sind nur vier uninteressante Vergleiche.
Mein Albtraum-Szenario ist, dass ich jede Koordinatenkomponente in zwei Hälften zerlegen und eine lange Multiplikation explizit ausführen muss, nur damit ich alle hohen Hälften in den Teilprodukten verfolgen kann. (Und dann explizit mit add-with-carry zu tun.)
Nach einigen Vergleichen und einfachen Überprüfungen können Sie zwei Paare positiver Zahlen (x1,y1) , (x2,y2) erhalten, die Sie überprüfen möchten, ob x1*y2==x2*y1 .
Sie können den euklidischen Algorithmus verwenden, um die GCD von x1 und y1 zu finden und sie beide durch GCM zu teilen. Tun Sie dasselbe für (x2,y2) . Wenn Sie in beiden Fällen das gleiche Paar haben, haben beide Vektoren die gleiche Richtung.
Wenn drei Punkte (a, b, c) genau kolinear sind, gilt die folgende Identität:
%Vor%d. h .:
%Vor% Also nimm die erste Komponente von (c-a) , dividiere sie durch die erste Komponente von (a-b) und speichere diesen Wert. Wiederholen Sie dann für jede nachfolgende Komponente, und wenn sich einige von ihnen unterscheiden, sind die Punkte nicht kolinear.
Wenn Sie vermeiden möchten, die Gleitkomma-Division vollständig zu verwenden (was der einfachste Weg wäre), dann müssen Sie das Verhältnis speichern und stattdessen vergleichen.
Tags und Links c