Triangular decomposition

摘要

The paper examines the recursive subdivision of a two-dimensional picture. Six decompositions are presented and assessed in terms of the similarity of the regions and the number of different neighbours of each region. Of the six decompositions described here, two are based on the equilateral triangle, one on the isosceles right-angled triangle, two on the scalene triangle, and one on squares inscribed inside squares to form isosceles right-angled triangles. The data structure representing each decomposition is a labelled tree; each label is a key incorporating the path from the root to the corresponding node. This particular way of labelling enables a tree to be represented as a set of sorted integers on which operations such a union, intersection, difference and test for membership are easy to carry out. A unified approach is given for finding the neighbours of each region. An example application of the triangulations presented here could be in cartography, where the overlaying of pictorial information often occurs.