We present the first exact, complete and efficient implementation that computes for a given set P=p1,...,pn of quadric surfaces the planar map induced by all intersection curves p1∩ pi, 2 ≤ i ≤ n, running on the surface of p1. The vertices in this graph are the singular and x-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in [20] and [9].Our implementation is complete in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pairs of curves intersect with high multiplicity. It is exact in that it always computes the mathematical correct result. It is efficient measured in running times.
展开▼
机译:我们介绍了对给定集合P = P 1 INF>,...,P N INF>的第一个精确,完整和有效的实现,所有全部诱导的平面图交叉点曲线P 1 INF>∩P I INF>,2≤i≤N,在P 1 INF>的表面上运行。该图中的顶点是曲线的奇异和X-极端点以及所有交叉点的曲线。如果基础点由其中一个曲线的分支连接,则两个顶点通过边缘连接。我们的工作基于并扩展了[20]和[9]中开发的想法。我们的实施是完成 i>,它可以处理所有类型的输入,包括所有退化曲线都有奇点或者成对曲线与高多数相交。它是精确的 i>,它始终计算数学正确结果。它是高效的 i>在运行时间测量。
展开▼