确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想，根据输入多边形A，B之间边的拓扑关系，划分A，B边为内边、外边、重叠边3种，揭示A，B与它们的交、并、差之间边的本质联系，进而描述了确定任意两个简单多边形交、并、差算法．算法的时间复杂度为O((n m k)log(n m k))，其中n，m分别是A，B的顶点数，k是两多边形的交点数．算法建立在数学理论基础之上，很好地处理了布尔运算的奇异情形，比如重叠边，边与边相交于边的顶点等情形．本算法易于编程实现。     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。     

基于网格与R-树空间索引的矢量线图任意简单多边形窗口裁剪算法

针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法。算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数。在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍。本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度;其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～ O(n~(1/2)),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向;最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件。     

Maximal intersection of spherical polygons by an arc with applications to 4-axis machining

Many geometric optimization problems in CAD/CAM can be reduced to a maximal intersection problem on the sphere: given a set of N simple spherical polygons on the unit sphere and a real number constant L≤2π, find an arc of length L on the unit sphere that intersects as many spherical polygons as possible. Past results can only solve this maximization problem for two very restricted special cases: the arc must be either a great circle or a semi-great circle. In this paper, a simple and deterministic algorithm based on domain partitioning is presented for solving this maximal arc intersection problem in the general case when the number L is arbitrary. The algorithm is made possible by reducing the domain of the arcs to a continuous sub-space in R² and then establishing a quotient space partitioning in this sub-space based on a congruence relation. The number of the constituting congruent sub-regions in this quotient space partitioning is shown to have an upper-bound O(E³), where E is the total number of edges on the polygons. The proposed algorithm has a worst-case upper bound O(ME) on its running time, where M is an output-sensitive number and is bounded by O(E³). Examples including two realistic tests for 4-axis NC machining are presented.     

一种含有圆弧的曲线快速求交方法

二维曲线的求交是CAD&CG中的一个基本问题,论文提出了一种由圆弧和直线段组成的二维曲线快速求交方法。首先选择一个最优方向,根据最优方向把封闭曲线分割为一系列单调链,然后通过拓展Bentley-Ottman的扫描线算法对单调链进行求交。算法时间复杂度为O((n+k)logm),其中n为顶点个数,k为交点的个数,m为划分的单调链的个数。     

Finding the intersection of two convex polyhedra

Given two convex polyhedra in three-dimensional space, we develop an algorithm to (i) test whether their intersection is empty, and (ii) if so to find a separating plane, while (iii) if not to find a point in the intersection and explicitly construct their intersection polyhedron. The algorithm runs in timeO (nlogn), where n is the sum of the numbers of vertices of the two polyhedra. The part of the algorithm concerned with (iii) (constructing the intersection) is based upon the fact that if a point in the intersection is known, then the entire intersection is obtained from the convex hull of suitable geometric duals of the two polyhedra taken with respect to this point.     

Visibility problems for orthogonal objects in two-or three-dimensions

LetP be a set ofl points in 3-space, and letF be a set ofm opaque rectangular faces in 3-space with sides parallel tox- ory-axis. We present anO(n logn) time andO(n) space algorithm for determining all points inP which are visible from a viewpoint at (0,0,), wheren=l+m. We also present anO(n logn+k) time andO(n) space algorithm for the hidden-line elimination problem for the orthogonal polyhedra together with a viewpoint at (0,0,), wheren is the number of vertices of the polyhedra andk is the number of edge intersections in the projection plane.     

Intersecting polyhedra with successive planes

An algorithm that computes the intersections of a set of non-overlapping arbitrary polyhedra with a series of planes is described. Each succeeding plane intersection is computed using information from the preceding intersection. Only changes to the preceding intersection are considered, making testing of the polyhedra minimal. Successions of intersecting planes that are translations of one another and those that are rotations of one another are considered.     

Fast dynamic intersection searching in a set of isothetic line segments

We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log² n) space requirements and O(log³ n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(logN + t) query time, O(n log² N) space and O(log² N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique.     

Probing a scene of nonconvex polyhedra

We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that probes are sufficient to compute the exact shapes of the polyhedra.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM).     

An optimal online algorithm for halfplane intersection

The intersection of N halfplanes is a basic problem in computational geometry and computer graphics,The optimal offline algorithm for this problem runs in time O(N log N).In this paper,an optimal online algorithm which runs also in time O(N log N) for this problem is presented.The main idea of the algorithm is to give a new definition for the left side of a given line,to assign the order for the opoints of a convex polygon.and then to use binary search method in an ordered vertex set.The data structure used in the algorithm is no more complex than array.     

折线链节点标注技术

针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用"线段端点与线段"和"线段端点与邻折线"的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效;然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注;通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.     

Quasiconvolutional smoothing of polyhedra

This paper describes a method for rounding edges and corners of arbitrary polyhedra that uses a fast approximation to convolutional filtering. The approximation defines an implicit surface, which is rendered with a specialised ray-tracing algorithm. By varying the radius of the smoothing filter, a wide range of effects can be obtained, from perfect polyhedra to blobby models. Small rounding radii give polyhedra a softer, more natural look, with edges well delineated by shadows and highlights. The rounded surfaces are much easier to specify and compute than those obtained by traditional filleting and surface-blending techniques, and are far more economical in storage.     

多面体环分解算法原理

本文着重阐述了环分解算法的三个主要步骤:(1)A体至从体的一致性映射过程。(2)交线边的计算及分类过程。(3)简单环分解和复杂环分解的计算过程。最后总结了该算法在FSMTS中的应用情况和实验结论。     

Detection of rotational and involutional symmetries and congruity of polyhedra

We propose a simple and efficient general algorithm for determining both rotational and involutional symmetries of polyhedra. It requiresO(m ²) time and usesO(m) space, wherem is the number of edges of the polyhedron. As this is the lower bound of the symmetry detection problem for the considered output form, our algorithm is optimal. We show that a slight modification of our symmetry detection algorithm can be used to solve the related conguity problem of polyhedra.     

Finding Starting Points for Tracing Surface Intersections

To find starting points for all the intersection curves, one of the surfaces is subdivided into some small surface patches. Based on a correlative algorithm of computing the minimum distance of two surfaces, the intersections of every patch with another surface are detected, and starting points are calculated by dichotomy. This algorithm shows superior efficiency in the computational complexity and number of iterations needed. It can be used to determine exact starting points on all possible solution curves between any kinds of parametric sculptured surfaces.     

Finding Starting Points for Tracing Surface Intersections

1 Introduction Finding out proper starting points for all the intersection curves between two surfaces is a key process in numerical tracing methods for surface-surface intersection (SSI) problems. A number of methods [1] are introduced to calculate the starting points. Cugini et al. [2] introduced the concept of shrinking bounding boxes to calculate starting points. This method is simple and in some cases effective, but it may miss some intersection components. Muellenheim [3] presented an…     

Fast detection of polyhedral intersection

Methods are given for unifying and extending previous work on detecting intersections of suitably preprocessed polyhedra. New upper bounds of O(log n) and O(log²n) are given on plane-polyhedron and polyhedron-polyhedron intersection problems.     

A localized method for intersecting plane algebraic curve segments

We present a local method for the computation of the intersections of plane algebraic curve segments. The conventional method of intersection is global, because it must first find all of the intersections between two curves before it can restrict the segments in question; hence, it cannot take advantage of situations dealing with the intersection of short-curve segments on complex curves. Our local method, on the other hand, will directly find only those intersections that lie on the segments, as it is based upon an extension of methods for tracing along a curve.This author's research was supported by the National Science Foundation under Grant IRI-8910366This author's research was supported by the National Science Foundation under Grant CCR-8810568