Точная геометрия в Java

Question

Я кодирую приложение на Java, которое требует довольно большой геометрии. Я сильно использовал существующие классы, и мои вычисления до сих пор были в двойной точности (поэтому я использую, например, Point2D.Double, Line2D.Double и кодировал выпуклый многоугольник с использованием последнего ...).

Я столкнулся с несколькими проблемами, связанными с вычислениями с двойной точностью, которые делают мое приложение неустойчивым, и я решил переключиться на BigDecimal, но это подразумевает создание собственных классов Point2D, Line2D с помощью BigDecimals и т. Д. И переписывание нескольких функций. Другим решением было бы принять неточности и справиться с ними; т. е. точка на самом деле представляет собой небольшой квадрат, линия - бесконечная полоса, точка лежит на прямой, если квадрат и полоса пересекаются и т. д. Хотя это решение может быть быстро реализовано, мой код был бы обезображен такими операциями, как (точность Math.abs (x) <) (чтобы обозначить, что x == 0) разбросаны здесь и там.

Кто-нибудь знает о хорошем чистом способе делать точную геометрию на Java?

Answer 1

_{Я попытался сжать (части) этого в комментарий, но это не поместилось. Вы должны не считать это ответом «THE», но есть некоторые моменты, которые я хотел бы перечислить здесь.}

Рекомендация использовать BigDecimal раздражающе общий всякий раз, когда кто-то упоминает точность проблему с float или double - и тем не менее столь же неуместно в таких случаях, как этот. Во всех, кроме наименьших случаях, ограниченная точность double просто не актуальна.

^{Если вы, возможно, не пишете программное обеспечение, которое должно вычислить траекторию пилотируемого космического корабля, который должен быть отправлен на Марс, или делать другие высоконаучные вычисления.}

Кроме того, замена double на BigDecimal имеет тенденцию заменять только одну небольшую проблему несколькими более крупными. Например, вам нужно будет подумать о RoundingMode и «шкале», что может быть сложно. И в итоге вы заметите, что простое значение, например 1.0/3.0, не может быть представлено BigDecimal.

Для вашего конкретного случая применения, есть больше предостережений:

Даже с BigDecimal -А реализацией Point2D, данные будут по-прежнему подвергаются в double, с помощью методов в getX()/getY(). Например, способ, подобный Line2D#ptLineDistSq, по-прежнему будет использовать значения double. Этого можно было бы избежать, если бы вы написали все, что связано с вашими вычислениями, с нуля, используя BigDecimal действительно всюду.

Но даже если вы это сделали: вы не можете вычислить наклон линии от точки (-1,0) до точки (2,1), и вы не можете сказать, где эта линия пересекает ось y. Здесь вы можете попробовать некоторое рациональное числовое представление, но по-прежнему существует проблема с длиной диагонали единичного квадрата, что является иррациональным числом.

Неточность double вызывает раздражение. Вы можете вычислить, является ли точка слева линии или правая линии.И из-за проблем точности, вполне возможно, что это и. Выполнение вычислений с точками, которые должны «математически» быть равным, но отличаются некоторой небольшой ошибкой с плавающей запятой, могут привести к фиктивным результатам (я также наткнулся на это в one of my libraries).

Как вы уже упоминали в вопросе: некоторые концепции, которые работают в чистой математике, должны быть переосмыслены, когда их следует применять с ограниченной точностью. Любое сравнение == - это не-go, и другие сравнения должны быть тщательно проверены с учетом возможных ошибок округления.

Но использование некоторых сравнений «epsilon» - это обычный способ справиться с этим. Конечно, они делают код немного более неуклюжим. Но сравните это с какой-то "произвольной точности" код с 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; 
} 

Кроме того, сравнения на основе эпсилона по-прежнему подвержены ошибкам и поднимают некоторые вопросы. Самое главное: насколько велика эта «эпсилон»? Где должно проводиться сравнение на основе эпсилона? Однако существующие реализации, такие как геометрические алгоритмы в http://www.geometrictools.com/, могут дать некоторые идеи о том, как это можно сделать (даже если они реализованы на C++ и стали менее читаемыми в последних версиях). Они проверены временем и уже показывают, как справляться со многими проблемами, связанными с точностью.