Skip to main content
SpringerLink
Log in

A Hierarchical Representation and Computation Scheme of Arbitrary-dimensional Geometrical Primitives Based on CGA

  • Published:
Advances in Applied Clifford Algebras Aims and scope Submit manuscript

Abstract

Resolving the conflicts between the high dimensionality of geometry representation and the linear organization and storage of geometrical objects in computer memories plays a key role in spatial data structure constructions. In this paper, a new data structure MVTree is developed based on geometric algebra to support the unified organization and computation of geometrical primitives. The MVTree is a tree-like data structure which has a dimensional hierarchical structure generated by outer product. Multidimensional geometrical primitives is represented as the combination of blades stored in the nodes of MVTrees. The geometric computation between different geometrical objects is operated with GA operators with a judgement-based hierarchical computation. Applications of the MVTree are demonstrated by a topological relation computation and a Delaunay-TIN intersection. The results suggest that the MVTree structure can support unified representation of arbitrary-dimensional geometrical primitives, and can integrate data organization and computation in a unitary structure as well. The application of the new MVTree data structure can not only reduce the complexity of data architectures but also inherit the power of geometric algebra computing to improve the processing ability of computer graphic software.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abdul R., Pilouk M.: Spatial Data Modelling for 3D GIS. Springer, Heidelberg (2007)

    Google Scholar 

  2. Ballard D.H., Brown C.M.: Computer Vision. Prentice Hall, Englewood Cliffs (1982)

    Google Scholar 

  3. Butler D.M., Pendley M.H.: A visualization model based on the mathematics of fiber bundles. Comput. Phys. 3(5), 45 (1989)

    Article  ADS  Google Scholar 

  4. Case, K., Gao, J.: Feature technology: an overview. Int. J. Comput. Integr. Manuf 6(1-2), 2–12 (1993)

  5. Charrier, P., Hildenbrand, D.: Geometric algebra enhanced precompiler for C++, OpenCL and Mathematicas OpenCLLink. Adv. Appl. Clifford Algebras 24, 613–630 (2014)

  6. Cohn A.G., Bennett B., Gooday J., Gotts N.M.: Qualitative spatial representation and reasoning with the region connection calculus. Geoinformatica 1(3), 275–316 (1997)

    Article  Google Scholar 

  7. Cugola G., Margara A.: Processing flows of information. ACM Comput. Surv. 44(3), 1–62 (2012)

    Article  Google Scholar 

  8. DeConto R.M., Pollard D.: A coupled climateCice sheet modeling approach to the Early Cenozoic history of the Antarctic ice sheet. Palaeogeogr. Palaeoclimatol. Palaeoecol. 198(1-2), 39–52 (2003)

    Article  ADS  Google Scholar 

  9. Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science: An Object-oriented Approach to Geometry. Morgan Kaufmann Publishers, San Francisco (2009)

  10. Egenhofer M.J., Franzosa R.D.: Point-set topological spatial relations. Int. J. Geogr. Inf. Syst. 5(2), 161–174 (1991)

    Article  Google Scholar 

  11. Franchini S., Gentile A., Sorbello F., Vassallo G., Vitabile S.: An embedded, FPGA-based computer graphics coprocessor with native geometric algebra support. Integr. VLSI J. 42(3), 346–355 (2009)

    Article  MATH  Google Scholar 

  12. Frank A.U.: Spatial concepts, geometric data models, and geometric data structures. Comput. Geosci. 18(4), 409–417 (1992)

    Article  ADS  Google Scholar 

  13. Goodchild M.F.: Citizens as sensors: the world of volunteered geography. GeoJournal 69(4), 211–221 (2007)

    Article  Google Scholar 

  14. Gossard D.C., Zuffante R.P., Sakurai H.: Representing dimensions, tolerances, and features in MCAE systems. IEEE Comput. Graph. Appl. 8(2), 51–59 (1988)

    Article  Google Scholar 

  15. Guibas L., Stolfi J.: Primitives for the manipulation of general subdivisions and the computation of Voronoi. ACM Trans. Graph. 4(2), 74–123 (1985)

    Article  MATH  Google Scholar 

  16. Guigue P., Devillers O.: Fast and robust triangle-triangle overlap test using orientation predicates. J. Graph. Gpu Game Tools 8(1), 25–42 (2003)

    Google Scholar 

  17. Hildenbrand D.: Foundations of Geometric Algebra Computing, Vol. 36. Springer, New York (2013)

    Book  MATH  Google Scholar 

  18. Klippel A.: Spatial information theory meets spatial thinking: is topology the Rosetta stone of spatio-temporal cognition. Ann. Assoc. Am. Geograph. 102(6), 1310–1328 (2012)

    Article  Google Scholar 

  19. Ledoux H., Gold C.M.: Modelling three-dimensional geoscientific fields with the Voronoi diagram and its dual. Int. J. Geogr. Inf. Sci. 22(5), 547–574 (2008)

    Article  Google Scholar 

  20. Li, H., Hestenes, D., Rockwood, A.: Generalized homogeneous coordinates for computational geometry. In: Sommer, G. (eds.), Geometric Computing with Clifford Algebras: Theoretical Foundations and Applications in Computer Vision and Robotics, pp. 27–59. Springer, Heidelberg (2001)

  21. Liu Y., Wang X., Bao S., Gomboši M., Žalik B.: An algorithm for polygon clipping, and for determining polygon intersections and unions. Comput. Geosci. 33(5), 589–598 (2007)

    Article  ADS  Google Scholar 

  22. Mantyla M.: An Introduction to Solid Modeling. Computer Science Press, Rockville, Maryland (1988)

    Google Scholar 

  23. Miller H.J., Wentz E.A.: Representation and spatial analysis in geographic information systems. Ann. Assoc. Am. Geogr. 93(3), 574–594 (2003)

    Article  Google Scholar 

  24. Möller, T.: A fast triangle-triangle intersection test. J. Graph tools 2(2), 25–30 (1997)

  25. Muller D.E., Preparata F.P.: Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7(2), 217–236 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  26. Palmer R.S., Shapiro V.: Chain models of physical behavior for engineering analysis and design. Res. Eng. Des. 5(3-4), 161–184 (1993)

    Article  Google Scholar 

  27. Reed, C.: 14 OGC standards and geospatial big data. In: Big Data: Techniques and Technologies in Geoinformatics, pp. 279–289. CRC Press, FL, USA (2014)

  28. Roa, E., Theoktisto, V., Fairén, M., Navazo, I.: GPU Collision Detection in Conformal Geometric Space. In: Silva, F., Gutierrez, D., Rodríguez, J., Figueiredo, M. (eds), SIACG. vol. 1, pp. 153–156 (2011)

  29. Siqueira T.L.L., de Aguiar C.D., Ciferri V., Times C., Ciferri R.R.: The SB-index and the HSB-index: efficient indices for spatial data warehouses. GeoInformatica 16(1), 165–205 (2012)

    Article  Google Scholar 

  30. Tsai V.J.D.: Delaunay triangulation in TIN creation: an overview and a linear-time algorithm. Int. J. Geogr. Inf. Syst. 7(6), 501–524 (1993)

    Article  Google Scholar 

  31. Yu, Z., Luo, W., Hu, Y., Yuan, L., Zhu, A., Lü, G.: Change detection for 3D vector data: a CGA-based Delaunay–TIN intersection approach. Int. J. Geogr. Inf. Sci. 29(12), 2328–2347 (2015)

  32. Yuan L., Yu Z., Luo W., Zhou L., Lü G.: A 3D GIS spatial data model based on conformal geometric algebra. Sci. China Earth. Sci. 54(1), 101–112 (2011)

    Article  Google Scholar 

  33. Yuan L., Lü G., Luo W., Yu Z., Yi L., Sheng Y.: Geometric algebra method for multidimensionally-unified GIS computation. Chin. Sci. Bull. 57(7), 802–811 (2012)

    Article  Google Scholar 

  34. Yuan L., Yu Z., Luo W., Yi L., Lü G.: Geometric algebra for multidimension-unified geographical information system. Adv. Appl. Cliff. Algebras 23(2), 497–518 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  35. Zlatanova S., Rahman A.A., Pilouk M.: Trends in 3D GIS development. J. Geospatial Eng. 4(2), 71–80 (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Key Laboratory of Virtual Geographic Environment, Ministry of Education, XianLin School of Nanjing Normal University, No.1 Wenyuan Road, Nanjing, China

    Wen Luo, Zhaoyuan Yu, Linwang Yuan & Guonian Lü

  2. Department of Computer Science and Technology, Nanjing Normal University, No.1 Wenyuan Road, Nanjing, China

    Yong Hu

Authors
  1. Wen Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yong Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhaoyuan Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Linwang Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Guonian Lü
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhaoyuan Yu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Luo, W., Hu, Y., Yu, Z. et al. A Hierarchical Representation and Computation Scheme of Arbitrary-dimensional Geometrical Primitives Based on CGA. Adv. Appl. Clifford Algebras 27, 1977–1995 (2017). https://doi.org/10.1007/s00006-016-0697-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00006-016-0697-3

Mathematics Subject Classification

Keywords

Search

Navigation