Genaue Geometrie in Java

Question

Ich kodiere eine Anwendung in Java, die ziemlich viel Geometrie benötigt. Ich habe die vorhandenen Klassen stark genutzt, und meine Berechnungen waren bisher in doppelter Genauigkeit (also verwende ich zum Beispiel Point2D.Double, Line2D.Double und codierte eine konvexe Polygonklasse mit letzterer ...).

Ich stieß auf einige Probleme in Bezug auf Berechnungen mit doppelter Genauigkeit, die meine Anwendung manchmal instabil machten, und ich erwog, zu BigDecimal zu wechseln, aber das würde die Erstellung eigener Point2D-, Line2D-Klassen mit BigDecimals usw. erfordern und mehrere Funktionen umschreiben. Eine andere Lösung wäre, die Ungenauigkeiten zu akzeptieren und damit umzugehen; ein Punkt ist tatsächlich ein kleines Quadrat, eine Linie ist ein unendliches Band, ein Punkt liegt auf einer Linie, wenn sich das Quadrat und das Band schneiden und so weiter. Obwohl diese Lösung schnell implementiert werden kann, würde mein Code durch (hier und da verstreute) Aussagen wie (Math.abs (x) < Präzision) entstellt werden (um anzuzeigen, dass x == 0).

Kennt jemand eine nette, saubere Methode, um genaue Geometrie in Java zu erstellen?

Answer 1

_{Ich versuchte (Teile) diese in einen Kommentar zu drücken, aber es passte nicht. Sie sollten nicht betrachten dies als "die" Antwort, aber es gibt einige Punkte, die ich hier auflisten möchte.}

Die Empfehlung BigDecimal zu verwenden ist ärgerlicherweise gemeinsam, wenn jemand Präzision Probleme mit float oder double erwähnt - und doch ist in solchen Fällen wie diese ebenso ungeeignet. In den wenigsten Fällen ist die begrenzte Genauigkeit von double einfach nicht relevant.

^{Es sei denn, Sie schreiben Software, die die Flugbahn eines bemannten Raumfahrzeugs, das gerade zum Mars gesendet wird, oder andere hochwissenschaftliche Berechnungen berechnen soll.}

Außerdem ersetzt das Ersetzen von double durch BigDecimal nur ein kleines Problem durch mehrere größere. Zum Beispiel müssen Sie über die RoundingMode und "Skalierung" nachdenken, was schwierig sein kann. Und schließlich werden Sie feststellen, dass ein einfacher Wert wie 1.0/3.0 nicht mit BigDecimal entweder dargestellt werden kann.

für Ihren speziellen Anwendungsfall gibt es mehr Einschränkungen:

Selbst bei einer BigDecimal -basierte Implementierung von Point2D, würden die Daten immer noch als double, über die getX()/getY() Verfahren ausgesetzt werden. Zum Beispiel wird eine Methode wie Line2D#ptLineDistSq immer noch die double Werte verwenden. Dies könnte nur vermieden werden, wenn man alles schrieb, die auf Ihre Berechnungen verwandt ist, von Grund auf, mit BigDecimal wirklich überall.

Aber selbst wenn Sie dies getan haben: Sie können nicht die Steigung einer Linie vom Punkt (-1,0) zum Punkt (2,1) berechnen, und Sie können nicht sagen, wo diese Linie die Y-Achse schneidet. Sie könnten hier eine rationale Zahlendarstellung versuchen, aber es gibt immer noch dieses Problem mit der Länge der Diagonalen eines Einheitsquadrats - was eine irrationale Zahl ist.

Die Ungenauigkeiten von double sind nervig. Sie können berechnen, ob ein Punkt links einer Linie oder rechts einer Linie ist.Und aufgrund der Genauigkeitsprobleme kann es gut sein, dass es sowohl ist. Berechnungen mit Punkten auszuführen, die "mathematisch" gleich sein sollten, aber sich durch einen kleinen Gleitkommafehler unterscheiden, kann zu falschen Ergebnissen führen (ich bin auch darüber in one of my libraries gestolpert).

Wie Sie bereits in der Frage erwähnt haben: Einige Konzepte, die in der reinen Mathematik funktionieren, müssen überdacht werden, wenn sie mit begrenzter Genauigkeit implementiert werden sollen. Jeder == Vergleich ist ein No-Go, und andere Vergleiche sollten unter Berücksichtigung der möglichen Rundungsfehler sorgfältig validiert werden.

Aber mit einigen "epsilon" -basierten Vergleiche ist der übliche Weg, damit umzugehen. Natürlich machen sie den Code etwas ungeschickter. Aber vergleichen Sie diese mit einem gewissen "beliebiger Genauigkeit" Code mit BigDecimal:

BigDecimal computeArea(BigDecimal radius) { 
    // Let's be very precise here.... 
    BigDecimal pi = new BigDecimal("3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198938095257201065485863278865936153381827968230301952035301852968995773622599413891249721775283479131515574857242454150695950829533116861727855889075098381754637464939319"); 
    BigDecimal radiusSquared = radius.multiply(radius); 
    BigDecimal area = radiusSquared.multiply(pi); 
    return area; 
} 

Vs.

double computeArea(double radius) { 
    return Math.PI * radius * radius; 
} 

Auch die Epsilon-basierte Vergleiche sind immer noch fehleranfällig und einige Fragen aufwerfen. Am prominentesten: Wie groß sollte dieses "Epsilon" sein? Wo sollte der Epsilon-basierte Vergleich stattfinden? Bestehende Implementierungen, wie die geometrischen Algorithmen in http://www.geometrictools.com/, könnten jedoch einige Ideen geben, wie dies möglich ist (obwohl sie in C++ implementiert sind und in den neuesten Versionen etwas weniger lesbar wurden). Sie sind praxiserprobt und zeigen bereits, wie man mit vielen der Präzisionsprobleme fertig wird.