Skip to main content

2016 | OriginalPaper | Buchkapitel

An Improved Polygon Clipping Algorithm Based on Affine Transformation

verfasst von : Mugdha Sharma, Jasmeen Kaur

Erschienen in: Proceedings of the Second International Conference on Computer and Communication Technologies

Verlag: Springer India

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Today, Computer Graphics is used almost in all the domains including gaming, entertainment, education, CAD/CAM, etc. One of the most important operations in computer graphics is clipping, such as line clipping and polygon clipping. Its importance emerges from the fact that polygon clipping can be applied in VLSI CAD, GIS, garment industry, etc. Many algorithms exist at the present moment but the intersection calculations incur huge costs. Our paper proposes an algorithm based on affine transformation which eliminates degeneracies while clipping self-intersecting and multi-polygons. Experimental results show that the new algorithm outperforms Greiner-Hormann and Vatti Algorithms for real-time datasets which are used in the packing industry.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Sutherland, E., Hodgman, G.W.: Reentrant polygon clipping. Commun. ACM 17(1), 32–42 (1974) Sutherland, E., Hodgman, G.W.: Reentrant polygon clipping. Commun. ACM 17(1), 32–42 (1974)
2.
Zurück zum Zitat Liang, Y.-D., Barsky, B.A.: An analysis and algorithm for polygon clipping. Commun. ACM 26(11), 868–877 (1983) Liang, Y.-D., Barsky, B.A.: An analysis and algorithm for polygon clipping. Commun. ACM 26(11), 868–877 (1983)
3.
Zurück zum Zitat Maillot, P.G., New, A.: Fast method for 2D polygon clipping: analysis and software implementation. ACM Trans. Graphics 11(3), 276–290 (1992)MATHCrossRef Maillot, P.G., New, A.: Fast method for 2D polygon clipping: analysis and software implementation. ACM Trans. Graphics 11(3), 276–290 (1992)MATHCrossRef
4.
Zurück zum Zitat Weiler, K., Atherton, P.: Hidden surface removal using polygon area sorting, computer graphics. In: Proceedings of SIGGRAPH, vol. 11(2), pp. 214–222, July 1977 Weiler, K., Atherton, P.: Hidden surface removal using polygon area sorting, computer graphics. In: Proceedings of SIGGRAPH, vol. 11(2), pp. 214–222, July 1977
5.
Zurück zum Zitat Vatti, B.R.: A generic solution to polygon clipping. Commun. ACM 35(7), 56–63 (1992) Vatti, B.R.: A generic solution to polygon clipping. Commun. ACM 35(7), 56–63 (1992)
6.
Zurück zum Zitat Greiner, G., Hormann, K.: Efficient clipping of arbitrary polygons. ACM Trans. Graph. 17, 71–83 (1998)CrossRef Greiner, G., Hormann, K.: Efficient clipping of arbitrary polygons. ACM Trans. Graph. 17, 71–83 (1998)CrossRef
7.
Zurück zum Zitat Liu, Y.K., Wang, X.Q., Bao, S.Z., Gombosi, M., Zalik, B.: An algorithm for polygon clipping, and for determining polygon intersections and unions. Comp. & Geosci. 33, 589–598 (2007)CrossRef Liu, Y.K., Wang, X.Q., Bao, S.Z., Gombosi, M., Zalik, B.: An algorithm for polygon clipping, and for determining polygon intersections and unions. Comp. & Geosci. 33, 589–598 (2007)CrossRef
8.
Zurück zum Zitat Kim, H., Kim, M.-J.: An extension of polygon clipping to resolve degenerate cases. Comp.-Aided Des. & Appl. 3(1–4), 447–456 (2006) Kim, H., Kim, M.-J.: An extension of polygon clipping to resolve degenerate cases. Comp.-Aided Des. & Appl. 3(1–4), 447–456 (2006)
9.
Zurück zum Zitat Foster, E.L., Overfelt, J.R.: Clipping of arbitrary polygons with degeneracies. ACM Trans. Graphics 1–5 (2014) Foster, E.L., Overfelt, J.R.: Clipping of arbitrary polygons with degeneracies. ACM Trans. Graphics 1–5 (2014)
10.
Zurück zum Zitat Chakraborty, A.: An extension of Weiler-Atherton algorithm to cope with the self-intersecting polygon. Cornell University Library, Computer Graphics. arXiv:1403.0917v1 Submitted on 4 March 2014 Chakraborty, A.: An extension of Weiler-Atherton algorithm to cope with the self-intersecting polygon. Cornell University Library, Computer Graphics. arXiv:1403.0917v1 Submitted on 4 March 2014
Metadaten
Titel
An Improved Polygon Clipping Algorithm Based on Affine Transformation
verfasst von
Mugdha Sharma
Jasmeen Kaur
Copyright-Jahr
2016
Verlag
Springer India
DOI
https://doi.org/10.1007/978-81-322-2517-1_75