Systems for solving spatial reasoning problems via topological inference

摘要

New methods of manipulating topological regions and properties have been discovered. These novel methods simplify complex spatial design problems. In some cases, the methods provide solutions or outputs where prior techniques fail entirely. Prior methods of reasoning about relations in two- dimensional space require computation with exact geometry even when only topological answers are required. For example, computing which sets of two- dimensional regions have simultaneous intersections would require explicitly constructing these intersections. These techniques become unnecessarily complex when regions have complex shapes. The present invention includes methods where topological properties of a set of regions in two-dimensional space can be manipulated by applications of topological computations. Two classes of these methods select and determine maximal and minimal simultaneous region intersections. A third method class produces sets of geometrical minimal paths satisfying a particular rule base through predetermined topological regions. The newly devised methods are much simpler and more robust than geometric methods as they do not require the exact shapes of regions to be completely known. In addition, the newly devised methods do not incur a penalty for complex curved shapes such as may occur in nature.