A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons
复制标题
DOI：
10.1007/3-540-45749-6_19
复制
发表时间：
2002-09
期刊：
影响因子：
--
通讯作者：
Eric Berberich;Arno Eigenwillig;M. Hemmer;Susan Hert;K. Mehlhorn;E. Schömer
中科院分区：
文献类型：
--
作者：
Eric Berberich;Arno Eigenwillig;M. Hemmer;Susan Hert;K. Mehlhorn;E. Schömer
我们给出了圆锥弧的精确几何核，低次代数数的精确计算算法，以及一种计算圆锥弧排列的算法，该算法可立即导致在圆锥多边形上实现正则化布尔运算。圆锥多边形，或简称多边形，是任何可以从线性或圆锥半空间（=线性或二次函数非负的点的集合）通过正则化布尔运算得到的东西。该算法及其实现是完整的（它们可以处理所有情况）、精确的（它们给出数学上正确的结果）和高效的（它们可以处理带有数百个原语的输入）。
We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately leads to a realization of regularized boolean operations on conic polygons. A conic polygon, or polygon for short, is anything that can be obtained from linear or conic halfspaces (= the set of points where a linear or quadratic function is non-negative) by regularized boolean operations. The algorithm and its implementation are complete (they can handle all cases), exact (they give the mathematically correct result), and efficient (they can handle inputs with several hundred primitives).