A fast and elementary algorithm for digital plane recognition - Archive ouverte HAL Access content directly
Reports Year : 2003

A fast and elementary algorithm for digital plane recognition

(1) , (2) , (3)
1
2
3
Yan Gérard
Isabelle Debled-Rennesson
• Function : Author
Paul Zimmermann

Abstract

A naive digital plane with integer coefficients is a subset of points (x,y,z) in Z^3 verifying a double inequality h <= ax+by+cz < h + max{ | a|,|b|, |c| } where a,b,c and h are integer numbers. Given a finite subset of Z^3, a problem is to determine whether or not there exists a naive digital plane containing it. This question is rather classical in the field of digital geometry (also called discrete geometry). We suggest in this paper a new algorithm for solving it. It uses an original strategy of optimization in a set of triangular facets (called triangles). The code is short and elementary (less than 300 lines) and available on http://www.loria.fr/~debled/plane. Its theoretical complexity is bounded by $O( n^7)$ but its behavior is quasi-linear in practice.

Dates and versions

inria-00099772 , version 1 (26-09-2006)

Identifiers

• HAL Id : inria-00099772 , version 1

Cite

Yan Gérard, Isabelle Debled-Rennesson, Paul Zimmermann. A fast and elementary algorithm for digital plane recognition. [Intern report] A03-R-332 || gerard03a, 2003, 16 p. ⟨inria-00099772⟩

102 View