论文标题
实施对几何变性的简单性模拟
Implementing Simulation of Simplicity for geometric degeneracies
论文作者
论文摘要
我们描述了如何实施简单性（SOS）的模拟。 SOS通过确定在坐标中添加不同阶的非架构Infitianimimals的效果，从而消除了点 - 多面体查询，多面体相交，MAP覆盖以及其他2D和3D几何和空间算法中的几何脱生。然后，它修改了几何谓词，以模拟该谓词并在通常的算术中对其进行评估。 几何变性是一个巧合，例如一个多边形在另一个多边形边缘的一个多边形的顶点，如果对象分布i.i.d.统一。但是，在实际数据中，它们可能经常发生。尤其是在3D中，有太多类型的退化性可靠地列举。但是，如果不处理它们，则谓词会评估错误，并且输出拓扑可能是错误的。 我们描述了SOS的理论，以及如何成功修改了几种算法和程序，包括许多立方体的结合，3D网格中的点位置以及相交的3D网格。
We describe how to implement Simulation of Simplicity (SoS). SoS removes geometric degeneracies in point-in-polygon queries, polyhedron intersection, map overlay, and other 2D and 3D geometric and spatial algorithms by determining the effect of adding non-Archimedian infinitesimals of different orders to the coordinates. Then it modifies the geometric predicates to emulate that, and evaluates them in the usual arithmetic. A geometric degeneracy is a coincidence, such as a vertex of one polygon on an edge of another polygon, that would have probability approaching zero if the objects were distributed i.i.d. uniformly. However, in real data, they can occur often. Especially in 3D, there are too many types of degeneracies to reliably enumerate. But, if they are not handled, then predicates evaluate wrong, and the output topology may be wrong. We describe the theory of SoS, and how several algorithms and programs were successfully modified, including volume of the union of many cubes, point location in a 3D mesh, and intersecting 3D meshes.
