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.
翻译：我们描述如何执行简单化模拟( SoS) 。 因此, SS 通过确定在坐标上添加不同顺序的非亚西中度无限动物的效果, 从而在微粒点查询、 多元面交叉点、 地图重叠点、 以及其它 2D 和 3D 几何算法和空间算法中去除几何变异。 然后, 它会修改几何假设, 并用通常的算术来加以效仿, 并且用通常的算术来评价它们。 几何变异性是一个巧合, 例如, 在另一个多边形边缘的一个多边形的顶点, 如果对象分布在 i. i. d. 时, 概率就会接近于零 。 然而, 在真实数据中, 它们会经常发生。 特别是在 3D 中, 有太多种非亚西中度的梯度无法可靠地进行计算 。 但是, 如果它们没有被处理, 则会评估前端错误, 产出表可能是错误的 。 我们描述了 SoS 的理论, 以及一些算法和程序是如何成功地被修改的, 包括许多立方体的组合、 位置 3D 和中间 3D 。
相关内容
微信扫码咨询专知VIP会员