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.