Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximation of Digital Surfaces by a Hierarchical Set of Planar Patches

  • Conference paper
  • First Online:
Discrete Geometry and Mathematical Morphology (DGMM 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13493))

Abstract

We show that the plane-probing algorithms introduced in Lachaud et al. (J. Math. Imaging Vis., 59, 1, 23–39, 2017), which compute the normal vector of a digital plane from a starting point and a set-membership predicate, are closely related to a three-dimensional generalization of the Euclidean algorithm. In addition, we show how to associate with the steps of these algorithms generalized substitutions, i.e., rules that replace square faces by unions of square faces, to build finite sets of elements that periodically generate digital planes. This work is a first step towards the incremental computation of a hierarchy of pieces of digital plane that locally fit a digital surface.

This work has been funded by PARADIS ANR-18-CE23-0007-01 research grant.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Arnoux, P., Furukado, M., Harriss, E., Ito, S.: Algebraic numbers, free group automorphisms and substitutions on the plane. Trans. Amer. Math. Soc. 363, 4651–4699 (2011)

    Article  MathSciNet  Google Scholar 

  2. Arnoux, P., Ito, S.: Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8(2), 181–208 (2001)

    Article  MathSciNet  Google Scholar 

  3. Berthé, V., Domenjoud, É., Jamet, D., Provençal, X.: Fully Subtractive algorithm, tribonacci numeration and connectedness of discrete planes. Res. Inst. Math. Sci. Lecture Note Kokyuroku Bessatu B 46, 159–174 (2014)

    Google Scholar 

  4. Berthé, V., Fernique, T.: Brun expansions of stepped surfaces. Discret. Math. 311(7), 521–543 (2011)

    Article  MathSciNet  Google Scholar 

  5. Berthé, V., Jamet, D., Jolivet, T., Provençal, X.: Critical connectedness of thin arithmetical discrete planes. In: Proceedings of DGCI, pp. 107–118 (2013)

    Google Scholar 

  6. Berthé, V., Lacasse, A., Paquin, G., Provençal, X.: A study of Jacobi-Perron boundary words for the generation of discrete planes. Theor. Comput. Sci. 502, 118–142 (2013)

    Article  MathSciNet  Google Scholar 

  7. Brimkov, V., Coeurjolly, D., Klette, R.: Digital planarity - a review. Discret. Appl. Math. 155(4), 468–495 (2007)

    Article  MathSciNet  Google Scholar 

  8. Domenjoud, E., Laboureix, B., Vuillon, L.: Facet connectedness of arithmetic discrete hyperplanes with non-zero shift. In: Proceedings of DGCI (2019)

    Google Scholar 

  9. Domenjoud, E., Provençal, X., Vuillon, L.: Facet connectedness of discrete hyperplanes with zero intercept: the general case. In: Proceedings of DGCI, pp. 1–12 (2014)

    Google Scholar 

  10. Domenjoud, E., Vuillon, L.: Geometric palindromic closure. Unif. Distrib. Theory 7(2), 109–140 (2012)

    MathSciNet  MATH  Google Scholar 

  11. Fernique, T.: Multidimensional Sturmian sequences and generalized substitutions. Int. J. Found. Comput. Sci. 17, 575–600 (2006)

    Article  MathSciNet  Google Scholar 

  12. Fernique, T.: Generation and recognition of digital planes using multi-dimensional continued fractions. Pattern Recogn. 42(10), 2229–2238 (2009)

    Article  Google Scholar 

  13. Jamet, D., Lafrenière, N., Provençal, X.: Generation of digital planes using generalized continued-fractions algorithms. In: Proceedings of DGCI, pp. 45–56 (2016)

    Google Scholar 

  14. Jolivet, T.: Combinatorics of Pisot substitutions. Ph.d. thesis, Université Paris Diderot, University of Turku (2013)

    Google Scholar 

  15. Klette, R., Rosenfeld, A.: Digital straightness - a review. Discret. Appl. Math. 139(1–3), 197–230 (2004)

    Article  MathSciNet  Google Scholar 

  16. Labbé, S., Reutenauer, C.: A d-dimensional extension of christoffel words. Discret. Comput. Geom. 54(1), 152–181 (2015)

    Article  MathSciNet  Google Scholar 

  17. Lachaud, J.O., Meyron, J., Roussillon, T.: An optimized framework for plane-probing algorithms. J. Math. Imaging Vis. 62, 718–736 (2020)

    Article  MathSciNet  Google Scholar 

  18. Lachaud, J.O., Provençal, X., Roussillon, T.: Two plane-probing algorithms for the computation of the normal vector to a digital plane. J. Math. Imaging Vis. 59, 23–39 (2017)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Univ Lyon, INSA Lyon, CNRS, UCBL, LIRIS, UMR 5205, 69622, Villeurbanne, France

    Jocelyn Meyron & Tristan Roussillon

Authors
  1. Jocelyn Meyron
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tristan Roussillon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tristan Roussillon .

Editor information

Editors and Affiliations

  1. University of Strasbourg, Strasbourg, France

    Étienne Baudrier

  2. University of Strasbourg, Strasbourg, France

    Benoît Naegel

  3. University of Strasbourg, Strasbourg, France

    Adrien Krähenbühl

  4. University of Strasbourg, Strasbourg, France

    Mohamed Tajine

Proofs

Proofs

Proof

(of Theorem 2).

$$\begin{aligned} E^*_1(\sigma _{n \cdots 0})(\textbf{0},i^*)&= E^*_1(\sigma _{n-1 \cdots 0})\big ( E^*_1(\sigma _n)(\textbf{0},i^*) \big ) \\&= E^*_1(\sigma _{n-1 \cdots 0}) \Bigg ( \underset{(s, j) \in \mathcal {S}^i_{\sigma _n}}{\bigcup } (\textbf{M}_{\sigma _n}^{-1} l(s), j^*) \Bigg ) \\&= \underset{(s, j) \in \mathcal {S}^i_{\sigma _n}}{\bigcup } E^*_1(\sigma _{n-1 \cdots 0}) \big (\textbf{M}_{\sigma _n}^{-1} l(s), j^*) \big ) \\&= \underset{(s, j) \in \mathcal {S}^i_{\sigma _n}}{\bigcup } \big ( (\textbf{M}_{\sigma _{n-1}} \cdots \textbf{M}_{\sigma _0})^{-1} (\textbf{M}_{\sigma _n})^{-1} l(s) + E^*_1(\sigma _{n-1 \cdots 0})(\textbf{0},j^*) \big ) \\&= \underset{(s, j) \in \mathcal {S}^i_{\sigma _n}}{\bigcup } \big ( (\textbf{M}_{\sigma _n} \cdots \textbf{M}_{\sigma _0})^{-1} l(s) + E^*_1(\sigma _{n-1 \cdots 0})(\textbf{0},j^*) \big ). \end{aligned}$$

The second to last line comes from

$$\begin{aligned} E^*_1(\sigma _{n-1 \cdots 0})(\textbf{x},i^*) = (\textbf{M}_{\sigma _{n-1}} \cdots \textbf{M}_{\sigma _0})^{-1} \textbf{x}+ E^*_1(\sigma _{n-1 \cdots 0})(\textbf{0},i^*), \end{aligned}$$

since \((\textbf{M}_{\sigma _{n-1}} \cdots \textbf{M}_{\sigma _0})^{-1}\) does not depend on the union in the definition of \(E^*_1\), Eq. (3) (see also [14, Proposition 1.2.4, item (2)]).    \(\square \)

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Meyron, J., Roussillon, T. (2022). Approximation of Digital Surfaces by a Hierarchical Set of Planar Patches. In: Baudrier, É., Naegel, B., Krähenbühl, A., Tajine, M. (eds) Discrete Geometry and Mathematical Morphology. DGMM 2022. Lecture Notes in Computer Science, vol 13493. Springer, Cham. https://doi.org/10.1007/978-3-031-19897-7_32

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-19897-7_32

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-19896-0

  • Online ISBN: 978-3-031-19897-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation