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.