Ich sehe, es gibt bereits eine gute Frage für allgemeine Polygone here. Gibt es einfachere oder effizientere Algorithmen für Vierecke?Was ist ein guter Algorithmus für die Berechnung der Fläche eines Vierecks?
Antwort
Für ein (konvexes) Viereck ist es oft schneller, das Quad in zwei Dreiecke aufzuteilen und die Fläche der zwei Dreiecke zu berechnen.
Wenn die Quadralaterale konvex nicht garantiert ist, ist die closed polygon approach immer noch meine Präferenz, da es in der Regel schneller als die Überprüfungen ist, um herauszufinden, wie Sie das Quad korrekt aufteilen.
Bearbeiten Kommentare:
Wie Walt W weist darauf hin, die beiden Ansätze sind theoretisch identisch in Bezug auf Leistung. Die zweite ist flexibler, da keine konvexen Quads benötigt werden, aber die erste (spaltende Dreiecke) ist leichter zu implementieren und zu verstehen, also potenziell aufrechterhaltbar.
Nein. Ich würde die Formel in der von Ihnen erwähnten Post verwenden.
Edits:
Um näher auf, dass eine Menge, wobei das Verfahren in der Post präsentiert Sie (die so genannte Closed Polygon-Ansatz in Reed Copsey Antwort) erwähnen die Liste der Punkte in Dreiecke brechen endet und Berechnung ihrer Bereiche Verwendung von Cross-Produkten. Es geht darum, nichts zu triangulieren, indem man sowohl die positiven als auch die negativen Bereiche ausnutzt, entsprechend der Reihenfolge (Wicklung) der Punkte, die das Polygon beschreiben. Da dieser Ansatz sowohl positive als auch negative Bereiche ausnutzt, erfordert dieser Ansatz keine Berechnungen für die Linien, die jedes Dreieck im Viereck bilden, und es spielt keine Rolle, ob das Viereck konvex ist oder nicht.
Das heißt, es ist einfacher, konzeptionell das Aufbrechen des Vierecks in zwei nicht überlappende Dreiecke zu verstehen und unabhängig die Fläche jedes Dreiecks zu berechnen. Dieser Ansatz wird immer auch das richtige Ergebnis liefern. Die Komplikation für diesen Ansatz besteht darin, zu entscheiden, welches Paar von gegenüberliegenden Ecken den Bruch zwischen den zwei Dreiecken spezifizieren soll. Wenn Sie ein nicht konvexes Viereck haben und die falsche Triangulation wählen, entstehen überlappende Dreiecke, die (sofern nicht berücksichtigt) das Flächenergebnis verzerren. Wenn Sie die Flächen dieser Dreiecke sorgfältig berechnen, werden Sie feststellen, dass (im Falle eines Vierecks) ein Dreieck immer in dem anderen enthalten sein wird. Mit einiger Schlauheit können Sie erreichen, dass die Fläche des enthaltenen Dreiecks das umgekehrte Vorzeichen der Fläche des umschließenden Dreiecks hat, die dann wiederum das korrekte Ergebnis liefert.
Im Wesentlichen sind diese beiden Algorithmen identisch. Es gibt keinen Leistungsunterschied; Angenommen, der Quadrupel ist durch x0, y0, x1, y1, x2, y2, x3 und y3 spezifiziert. Dann wird der geschlossene Polygon Ansatz hat die folgenden Operationen:
area = 0.5 * abs(x0 * y1 - x1 * y0 + x1 * y2 - x2 * y1 +
x2 * y3 - x3 * y2 + x3 * y0 - x0 * y3)
Welche vereinfacht werden kann als:
area = 0.5 * abs(x0 * (y1 - y3) + x1 * (y2 - y0) + x2 * (y3 + y1) +
x3 * (y0 - y2))
die zu ausarbeitet (der * zählen 's und +' s) 12 Operationen insgesamt. Der andere Ansatz, jedes einzelne Dreieck zu finden und das Kreuzprodukt unter funktioniert wie folgt:
x2_line = x2 - x0
y2_line = y2 - y0
area = 0.5 * abs((x1 - x0) * y2_line + (y1 - y0) * x2_line +
x2_line * (y3 - y0) + y2_line * (x3 - x0))
die wiederum vereinfacht werden kann:
x2_line = x2 - x0
y2_line = y2 - y0
area = 0.5 * abs(y2_line * (x1 - x0 + x3 - x0) + x2_line * (y1 - y0 + y3 - y0))
die auch 12 Operationen ausarbeitet. Die genau gleiche Anzahl von Operationen. Der größte Unterschied besteht also darin, dass die Triangulation gefolgt von der produktübergreifenden Berechnung einfacher zu verstehen ist, während der Closed-Polygon-Ansatz eigentlich nur der gleiche Algorithmus ist, aber optimiert und somit präsentiert wird auf andere Weise.
Zusammenfassend, ja, die Formel in der Post, die Sie erwähnen, ist die effizienteste, die Sie haben, und ist zur gleichen Zeit der einfachste Algorithmus, wenn anders dargestellt.
Warum der Downvote. . . Die allgemeine Formel erfordert 3 Operationen pro Vertexpaar + 1 multipliziert mit 0,5, was 3 * 4 + 1 = 13 Operationen für ein Quad entspricht. . . –
Plus, der geschlossene Polygon-Ansatz erwähnt in der oberen Post ist die ursprüngliche Formel in der Frage erwähnt ... –
Ursprünglich schien es wie eine rotzig Antwort, die ich allzu oft sehe. Aber Ihre Bearbeitung und Kommentare haben es verdient. Erwäge, diese Kommentare in eine andere Bearbeitung zu übernehmen. – geowa4
Die Seite mathworld listet mehrere Formeln auf.
Brechen Sie das Quadrialateral in zwei Dreiecke und berechnen Sie die Fläche von beiden.
Sobald Sie zwei Dreiecke haben, funktioniert Heron's Formula gut innerhalb eines Computerprogramms.
für ein Dreieck mit den Seiten A, B und C ist der Bereich
double area = Math.Sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)/16);
Dieses Verfahren arbeitet mit einer beliebigen Vierecks, ob es sich um ein Rechteck, Quadrat, Rhombus, Trapez oder ist.
Es gibt Vierecke, die keine Rechtecke, Quadrate, Rhomben oder Trapeze sind! Wenn sie konvex sind, ist "brechen in zwei Dreiecke" eine nichttriviale Aufgabe, wie Reed bemerkte. – Ken
@Ken: That sollte "Wenn sie NICHT konvex sind" ... konvexe Quads sind trivial, da jeder Bruch gültig ist. Nicht-konvexe Quads können eine starke Überberechnung des Bereichs verursachen. –
Ist die einfachste Lösung, dann die Fläche beider Mengen zu berechnen von Dreiecken und wählen Sie den Mindestwert? –
Welche Formel würden Sie für die Berechnung der Fläche jedes Dreiecks verwenden? –
Sie können jeden Ansatz verwenden. Normalerweise verwende ich 1/2 des Kreuzprodukts der beiden Vektoren, aber das liegt daran, dass ich fast immer im 3D-Raum arbeite, und das für nicht-planare Quads funktioniert (obwohl man in diesem Fall technisch eine Regelfläche verwenden sollte, was nicht schnell ist). –
Nun, meine Frage ist, wie viele Operationen beteiligt sind? Warum ist das schneller als die Verwendung des geschlossenen Polygonzuges (wie Sie ihn nennen, der mit der Formel identisch ist, zu der das OP eine Verbindung herstellt)? –