A fast and elementary algorithm for digital plane recognition

✍ Scribed by Y. Gérard

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 126 KB
• Volume: 12
• Category: Article
• ISSN: 1571-0653
• DOI: 10.1016/s1571-0653(04)00481-0

✦ Synopsis

A digital naive plane is a subset of points (x, y, z) ∈ Z 3 verifying a double inequality h ≤ ax + by + cz < h + max{|a|, |b|, |c|} where (a, b, c) ∈ R/ {(0,0,0)} and h ∈ R. Given a finite subset of Z 3 , a problem is to determine whether or not there exists a digital naive 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 2-simplexes called triangles and an original strategy of optimization. The code is short and elementary (less than 300 lines). Its theoritical complexity is bounded by O(n 7 ) but its behaviour is quasi-linear in practice.