On discrete triangles characterization

摘要

For a given real triangle T its discretization on a discrete point set S consists of points from S which fall into T. If the number of such points is finite the obtained discretization of T will be called discrete triangle. In this paper we show that all discrete triangles from a fixed discretizing set are determined uniquely by their 10 discrete moments which have the order up to 3. Of a particular interest is the case when S is the integer grid, i.e., S=Z2. The discretization of a real triangle on Z2 is called digital triangle. It turns out that the proposed characterization preserves a coding of digital triangles from an integer grid of a given size, say m×m, within an O(logm) amount of memory space per coded digital triangle. That is the theoretical minimum. A possible extension of the proposed coding scheme for digital triangles to the coding digital convex k-gons and arbitrary digital convex shapes is discussed, as well.