Study on Representations and Processing of Geometric Objects in Terms of Mutual Constraints

从工程角度考虑了表示几何对象的可能性和用途，不是用坐标系，而是用对象的点、线和面等元素之间的相互约束来表示几何对象，并获得了以下结果。阐明了顶点之间的长度、面间夹角等相互约束之间的依赖关系的数学结构；对于几何元素位于一般位置的情况，依赖结构由几何对象的某些组合性质来刻画；对于几何元素位于特定位置从而发生退化的情况，依赖结构由代数性质来刻画。2.将上述结果应用于几何结构定义不一致问题、单摄像机移动机器人定位问题和距离图像目标识别问题。3.构造了一种避免几何退化的新方法。几何退化是当几何元素到达特定位置时发生的，这使得几何算法变得复杂。在Voronoi图的构造和消隐中，使用了一种称为“符号摄动”的技术来避免这种退化。4.提出了一种使几何算法对数值误差保持稳定的新方法。该方法基于这样的原则，即如果数值结果与拓扑结构相矛盾，则优先考虑拓扑结构的一致性。将该方法应用到Voronoi图的构造中，实验结果表明了该方法的有效性，该项目中建立的新概念和新方法将在未来应用于工程各个领域的许多其他几何问题。

The possibility and the use of representing geometric objects, not in terms of coordinate systems, but in terms of mutual constraints among elements such as points, lines and faces of the objects was considered from an engineering point of view, and the following results have been obtained.1. The mathematical structure of dependence among mutual constraints such as lenghts between vertices and angles between faces was :clarified; the dependence structure was characterized by some combinatorial properties of the geometric objects for the case where geometric elements were in general positions, whereas the dependence structure was characterized by algebraic properties for the case where geometric elements were in some special position so that degeneracy took place. 2. The above result was applied to the problem of finding inconsistency in the definition of geometric structures, to that of locating a mobile robot with a single camera, and to that of recognizing objects extracted from range pictures. 3. A new method was constructed for avoiding geometric degeneracy. Geometric degeneracy takes place when geometric elements come to some special position, and it causes to make geometric algorithms complicated. A technique called "symbolic perturbation" was applied to avoidance of such degeneracy in Voronoi diagram construction and in hidden line elimination. 4. A new method was proposed for making geometric algorithms stable against numerical errors. The method is based on the principle that the highest priority is placed on the consistency of the topological structures if numerical results contradict topological structures. This method was applied to the construction of Voronoi diagrams, and experimental results showed the validity of the method.The new concepts and methods established in this projects will be applied to many other geometric problems in various fields of engineering in future.