Geometric constraint solving with conics and linkages

Most geometric construction methods of geometric constraint solving systems use line and circle (rule and compass) as basic drawing tools. In this paper, by introducing conics and linkages, we provide a set of complete drawing tools for the construction approach of geometric constraint solving. Using these tools, we may enlarge the drawing scope of the construction approach and still keep the elegant style of geometric solutions to geometric constraint solving. As applications, we obtain pure geometric solutions to three sets of well-known constraint problems: the 10 Apollonian drawing problems, the 13 cases of a smallest tri-connected constraint graph, and constraint problems with distance constraints only.     

基于几何约束求解的完备方法

针对参数化CAD在约束求解中的应用,提出了基于智能连杆的算法,该算法在扩充几何作图范围、改善算法复杂度方面都有明显的优势.将其同LIMO算法、几何变换方法、C-Tree算法、数值求解方法等方法相互融合,能够组成一套非常完备的几何约束求解框架,来完成对平面和空间几何约束问题的自动求解与图像生成.将该算法应用于智能动态几何软件的设计中,实验显示可以取得令人满意的结果.     

Dealing with redundancy and inconsistency in constructive geometric constraint solving

General constructive geometric constraint solvers are pre-processed by a degree-of-freedom analysis, which enables efficient graph decomposition and recombination. However, all these methods are based on the assumption that structural rigidity automatically assures solvability. In this paper, we show that this assumption fails in numerous, even the most basic, configurations. We introduce several simple but efficient rules aimed to additionally analyse solvability in such cases. Another novelty addresses conditional constraints between three or more geometric parts, rules for their simplification and a redundancy check. All these functionalities are built into our original 2D geometric constraint solver, based on concepts of rigid clusters and constrained-angle (CA) sets.     

Solving spatial basic geometric constraint configurations with locus intersection

A basic idea of geometric constraint solving (GCS) is to decompose the constraint problem into smaller ones according to some basic configurations. In this paper, we find all spatial basic configurations involving points, lines, and planes containing up to six geometric primitives in an automated way. Many of these basic configurations still resist effective analytical solutions. We propose the locus intersection method (LIM) for GCS, a hybrid method based on geometric computation and numerical search that can be used to find all the solutions for a geometric constraint problem. We show that the LIM can be used to solve all the above basic configurations.     

A C-tree decomposition algorithm for 2D and 3D geometric constraint solving

In this paper, we propose a method which can be used to decompose a 2D or 3D constraint problem into a C-tree. With this decomposition, a geometric constraint problem can be reduced into basic merge patterns, which are the smallest problems we need to solve in order to solve the original problem in certain sense. Based on the C-tree decomposition algorithm, we implemented a software package MMP/Geometer. Experimental results show that MMP/Geometer finds the smallest decomposition for all the testing examples efficiently.     

快速判定几何约束奇异性的切面扰动法

针对冗余奇异和分支奇异的判定问题,提出一种新的切面扰动的判定方法.该方法将奇异的雅可比矩阵分为独立构型空间和奇异空间,变量沿独立构型空间的切面扰动,计算更新的雅克比矩阵的秩,依据秩亏的变化可以快速、稳定地判定约束奇异性.该算法克服了残量扰动法的数值迭代、计算量大和不稳定的缺点,并且在参数化特征造型系统InteSolid中得到验证.     

三维服装CAD中几何约束表达及其求解技术研究

从人体及服装的特点出发,提出三维服装几何元素的概念．采用样条曲线作为基本几何元素,归纳出服装的三种约束关系,即共点、对称和自对称关系;成为约束关系形成的基础．以三种约束关系为基础,建立了面向服装的几何约束图,有效地表达了三维服装几何元素及其相互关系;实现了一种基于约束图的约束求解方法。从而完成了构造服装及对服装的交互参数化修改,文中给出了应用实例,并将参数化方法向高层次图素如样条曲线、曲面作了推广,成功地应用于以样条曲线为几何元素的参数化服装CAD系统中,运行效果良好。     

Revisiting decomposition analysis of geometric constraint graphs

Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solving.In this paper we first introduce the concept of deficit of a constraint graph. Then we give a new formalization of the decomposition algorithm due to Owen. This new formalization is based on preserving the deficit rather than on computing triconnected components of the graph and is simpler. Finally we apply tree decompositions to prove that the class of problems solved by the formalizations studied here and other formalizations reported in the literature is the same.     

几何约束求解研究综述

综述了几何约束求解的历史发展、研究现状和应用．对常见的4类求解方法：数值计算的方法、符号计算的方法、基于规则的方法、基于图论的方法做了详细的介绍．同时还列举了几何约束求解在计算机视觉、连杆设计、机器人、分子结构设计和计算机辅助教学等方面的应用实例．     

A Constructive Approach to Solving Geometric Constraint Systems

This paper proposes a constructive approach to solving geometric constraint systems.The approach incorporates graph-based and rule-based approaches, and achieves interactive speed.The paper presents a graph representation of geometric conStraint syStems, and discusses in detailthe algorithm of geometric reasoning based on poinl-cluster reduction. An example is made forillustration.     

Geometric constraint solving: The witness configuration method

Geometric constraint solving is a key issue in CAD, CAM and PLM. The systems of geometric constraints are today studied and decomposed with graph-based methods, before their numerical resolution. However, graph-based methods can detect only the simplest (called structural) dependences between constraints; they cannot detect subtle dependences due to theorems. To overcome these limitations, this paper proposes a new method: the system is studied (with linear algebra tools) at a witness configuration, which is intuitively similar to the unknown one, and easy to compute.     

用圆锥曲面求解几何约束问题

通常大多数三维参数化CAD系统都只用平面和球面作为最基本的作图工具,这在某种程度上限制了三维参数化CAD系统的作图范围.通过引进一类新的作图工具,使得三维参数化CAD系统的作图范围得到扩大. 同时证明了一个三维几何图形可以用平面、球面和圆锥曲面构造出来的充分必要条件是这个三维几何图形可以用一个三角化的次数小于9的代数方程组来描述.通过引进圆锥曲面作为新的作图工具,著名的三维Appolonius作图问题可以被完全求解.     

几何约束求解的简化迭代算法

针对几何约束系统图分解中复合顶点的求解问题,提出复合顶点的图分解算法和等价自由变量的简化迭代求解算法.通过去除复合顶点部分边界约束对复合顶点进行图分解,对求解序列中的欠约束顶点添加等价自由变量、以等价自由变量的部分迭代求解、替代系统的整体数值求解,以提高求解效率和稳定性.该算法具有很强的通用性,并在实际应用中得到验证.     

面向集成变量化设计的三维几何约束求解方法

针对集成变量化设计中三维几何约束和装配几何约束的混合建模与求解问题,提出改进的有向图方法.该方法采用几何约束的基本约束表达和几何实体的抽象对偶实体表达,引入定向弧表达实体之间的内在依赖关系建立混合几何约束有向图模型;结合约束有向图的优化处理,实现了几何约束系统的细粒度分解和高效并行求解.最后用实例验证了文中方法的正确性和有效性.     

Using invariance under the similarity group to solve geometric constraint systems

In the area of Computer Aided Design (CAD), the main feature of geometric constraint systems lies in their invariance under the direct isometry group. Several researchers have developed methods, which take advantage of this fact to decompose such systems into smaller sub-systems. In this paper, we show that considering the invariance under the direct similarity group leads to a new constructive method to solve geometric constraint systems encountered in CAD.     

Geometric constraints within feature hierarchies

We study the problem of enabling general 2D and 3D variational constraint representation to be used in conjunction with a feature hierarchy representation, where some of the features may use procedural or other non-constraint based representations. We trace the challenge to a requirement on constraint decomposition algorithms or decomposition-recombination (DR) planners used by most variational constraint solvers, formalize the feature hierarchy incorporation problem for DR-planners, clarify its relationship to other problems, and provide an efficient algorithmic solution. The new algorithms have been implemented in the general, 2D and 3D opensource geometric constraint solver FRONTIER developed at the University of Florida.     

动态种群划分量子遗传算法求解几何约束

几何约束问题的约束方程组可转化为优化模型,因此约束求解问题可以转化为优化问题。针对传统量子遗传算法个体间信息交换不足,易使算法陷入局部最优的缺点,提出了动态种群划分量子遗传算法（dynamic population divided quantum genetic algorithm,DPDQGA）,并将其应用于几何约束求解中。该算法种群中的个体按照一定规则自发地进行信息交换。在每一代进化的开始阶段,分别对两个初始种群中的个体计算个体适应度。将两个种群合并,使用联赛选择的方法为种群中的个体打分,并按照得分对种群进行排序。最后将合并的种群重新划分为两个子种群。实验表明,基于动态种群划分的量子遗传算法求解几何约束问题具有更好的求解精度和求解速率。     

Searching the Solution Space in Constructive Geometric Constraint Solving with Genetic Algorithms

Geometric problems defined by constraints have an exponential number of solution instances in the number of geometric elements involved. Generally, the user is only interested in one instance such that besides fulfilling the geometric constraints, exhibits some additional properties. Selecting a solution instance amounts to selecting a given root every time the geometric constraint solver needs to compute the zeros of a multi valuated function. The problem of selecting a given root is known as the Root Identification Problem.In this paper we present a new technique to solve the root identification problem. The technique is based on an automatic search in the space of solutions performed by a genetic algorithm. The user specifies the solution of interest by defining a set of additional constraints on the geometric elements which drive the search of the genetic algorithm. The method is extended with a sequential niche technique to compute multiple solutions. A number of case studies illustrate the performance of the method.     

部分变量迭代法求解几何循环约束

在对几何约束进行求解时,一般先要进行适当分解,然后再根据分解得到的求解次序进行依次求解。当同时进行求解的约束数量较多时,必须采用数值解法。如果这样的循环约束中变量的数量较多,则采用全部变量迭代的方法会导致计算不稳定,且计算时间较长。本文提出了部分变量进行迭代的方法,大大降低了迭代变量的个数,增加了计算的的稳定性,缩短了计算时间。     

用连杆机构几何约束求解

在这篇文章里,我们引入连杆机构作为新的工具,且证明这是完备的,也就是说,所有能构造性描述的图形能被连杆机构作出,这一类包括了所有只含距离约束的约束问题.作为一个应用,我们说明了超出Owen和Hoffmann的三角分解方法之外的最简单的约束图能被转化为纯几何构造形式.为了求解起源于连杆构造的方程,我们提出了一种基于动态轨迹生成的几何方法.