Abstract
In this paper we use symmetric coordinate systems for the hexagonal and the triangular grids (that are dual of each other). We present new coordinate systems by extending the symmetric coordinate systems that are appropriate to address elements (cells) of cell complexes. Coordinate triplets are used to address the hexagon/triangle pixels, their sides (the edges between the border of neighbour pixels) and the points at the corners of the hexagon/triangle pixels. Properties of the coordinate systems are detailed, lines (zig-zag lines) and lanes (hexagonal stepping lanes) are defined on the triangular (resp. hexagonal) grid by fixing a coordinate value. The bounding relation of the cells can easily be captured by the coordinate values. To illustrate the utility of these coordinate systems some topological algorithms, namely collapses and cuts are presented.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Brimkov, V.E., Barneva, R.: “Honeycomb” vs square and cubic models. In: Electronic Notes in Theoretical Computer Science, p. 46 (2001)
Cousty, J., Bertrand, G., Couprie, M., Najman, L.: Collapses and watersheds in pseudomanifolds. In: Wiederhold, P., Barneva, R.P. (eds.) Proceedings of IWCIA 2009, LNCS, vol. 5852, pp. 397–410 (2009)
Cousty, J., Bertrand, G., Najman, L., Couprie, M.: Watershed cuts: thinnings, shortest path forests, and topological watersheds. IEEE Trans. Pattern. Anal. Mach. Intell. 32(5), 925–939 (2010)
Coxeter, H.S.M.: Introduction to Geometry, 2nd edn. Wiley, New York (1969)
Deutsch, E.S.: Thinning algorithms on rectangular, hexagonal and triangular arrays. Commun. ACM 15, 827–837 (1972)
Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)
Her, I.: Geometric transformations on the hexagonal grid. IEEE Trans. Image Process. 4(9), 1213–1222 (1995)
Ito, K. (ed.): Encyclopedic Dictionary of Mathematics, vol. 2, (original Japanese edition, 1954). MIT Press (1993, 2000)
Luczak, E., Rosenfeld, A.: Distance on a hexagonal grid. IEEE Trans. Comput. C-25(5), 532–533 (1976)
Klette, R., Rosenfeld, A.: Digital geometry. Geometric Methods for Digital Picture Analysis. Morgan Kaufmann Publishers, San Francisco, Elsevier Science, Amsterdam (2004)
Kong, T., Rosenfeld, A.: Digital topology: introduction and survey. Comput. Vis. Graph. Image Process. 48(3), 357–393 (1989)
Kovalevsky, V.A.: Finite topology as applied to image analysis, Vol. 45 (1989)
Kovalevsky, V.A.: Algorithms in digital geometry based on cellular topology. In: Proceedings of IWCIA 2004, LNCS, vol. 3322, pp. 366–393 (2004)
Kovalevsky, V.A.: Geometry of Locally Finite Spaces (Computer Agreeable Topology and Algorithms for Computer Imagery), editing house Dr. Bärbel Kovalevski, Berlin (2008)
Middleton, L., Sivaswamy, J.: Hexagonal Image Processing – A Practical Approach. Springer, London (2005)
Nagy, B.: Shortest path in triangular grids with neighbourhood sequences. J. Comput. Inf. Technol. 11, 111–122 (2003)
Nagy, B.: A family of triangular grids in digital geometry. In: Proceedings of ISPA03, 3rd International Symposium on Image and Signal Processing and Analysis (IEEE), pp. 101–106. Rome (2003)
Nagy, B.: Generalized triangular grids in digital geometry. Acta Mathematica Academiae Paedagogicae Nyíregyháziensis 20, 63–78 (2004)
Nagy, B.: A symmetric coordinate frame for hexagonal networks. In: Proceedings of Theoretical Computer Science - Information Society’04 (ACM Slovenia), pp. 193–196. Ljubljana (2004)
Nagy, B.: Characterization of digital circles in triangular grid. Pattern Recogn. Lett. 25(11), 1231–1242 (2004)
Nagy, B.: Calculating distance with neighborhood sequences in the hexagonal grid. In: Proceedings of IWCIA 2004: Tenth International Workshop on Combinatorial Image Analysis, Lecture Notes in Computer Science LNCS, vol. 3322, pp. 98–109. Auckland (2004)
Nagy, B.: Isometric transformations of the dual of the hexagonal lattice. In: Proceedings of ISPA 2009, 6th International Symposium on Image and Signal Processing and Analysis (IEEE), pp. 432–437. Salzburg (2009)
Nagy, B.: Cellular topology on the triangular grid. In: Proceedings of IWCIA 2012, Lecture Notes in Computer Science - LNCS, vol. 7655, pp. 143–153 (2012)
Nagy, B., Strand, R.: Non-traditional grids embedded in ℤn. Int. J. Shape Model. IJSM (World Scientific) 14(2), 209–228 (2008)
Nagy, B., Strand, R.: Non-traditional grids embedded in ℤn. Int. J. Shape Model. IJSM (World Scientific) 14(2), 209–228 (2008)
Stojmenovic, I.: Honeycomb networks: topological properties and communication algorithms. IEEE Trans. Parallel Distrib. Syst. 8(10), 1036–1042 (1997)
Strand, R., Nagy, B., Borgefors, G.: Digital distance functions on three-dimensional grids. Theor. Comput. Sci. 412, 1350–1363 (2011)
Yong-Kui, L.: The generation of straight lines on hexagonal grids. Comput. Graph. Forum. 12(1), 21–25 (1993)
Wiederhold, P., Morales, S.: Thinning on quadratic, triangular, and hexagonal cell complexes. In: Proceedings of IWCIA 2008, Lecture Notes in Computer Science - LNCS, vol. 4958, pp. 13–25 (2008)
Wuthrich, C.A., Stucki, P.: An algorithm comparison between square- and hexagonal-based grids. Graph. Model Im. Proc. 53(4), 324–339 (1991)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nagy, B. Cellular topology and topological coordinate systems on the hexagonal and on the triangular grids. Ann Math Artif Intell 75, 117–134 (2015). https://doi.org/10.1007/s10472-014-9404-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-014-9404-z