Spatial Geometric Constraint Solving Using Constructive Geometry and Homotopy Continuation

该项目开发了一个实用的空间几何约束求解器的理论和实现， 从构造几何的符号方法与从 同伦延拓理论 几何约束求解器是 现代机械计算机辅助设计系统，并提供了一个关键的 提高生产率、快速响应制造和敏捷性的技术 制造业 平面约束存在有效的求解器，但空间问题 超过了许多研究求解器的能力。 的 正在开发的解决方案将涵盖由以下内容指定的广泛类别的问题： 点、线和平面之间的距离、角度和入射约束。 它 将以交互方式解决小问题， 几秒 使用约束图，其节点表示元素， 边表示约束，约束分析将分解 约束问题转化为一系列可以解决的小构造问题 有效地使用预处理。 将进行基本建设 代数上，更复杂的建设步骤同伦延续。 该混合算法结合了符号方法的鲁棒性和完备性 数值方法的一致性和效率。

The project develops the theory and implementation of a practical spatial geometric constraint solver that integrates symbolic methods from constructive geometry with numerical methods from homotopy continuation theory. Geometric constraint solvers are a key component in modern Mechanical Computer-Aided Design systems, and offer a critical technology for increased productivity, rapid response manufacturing, and agile manufacturing. Effective solvers exist for planar constraints, but spatial problems of moderate size exceed the capabilities of many research solvers. The solver being developed will cover the broad class of problems specified by distance, angle, and incidence constraints among points, lines, and planes. It will solve small problems interactively and problems of moderate size in a few seconds. Using a constraint graph whose nodes represent elements and whose edges represent constraints, a constraint analysis will decompose the constraint problem into a series of small construction problems that can be solved efficiently using preprocessing. Elementary constructions will be carried out algebraically, more complex construction steps by homotopy continuation. The hybrid algorithm combines the robustness and completeness of symbolic methods with the uniformity and efficiency of numerical methods.