[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article
Free access

Performing geometric transformations by program transformation

Published: 03 January 1990 Publication History

Abstract

Problems in geometry often possess symmetry properties that may be exploited in order to develop solutions. Algorithms based on these symmetry properties will frequently use geometric transformations to transform one case into another (symmetric) case. One advantage of this approach is that the algorithm avoids enumeration of cases and thus is shorter and generally easier to read. One disadvantage is that some additional execution time is required to perform these transformations. We describe how simple program equivalences may be used as program transformations to eliminate this additional execution time from programs that use geometric transformations. This approach has been used to develop an efficient implementation of a new algorithm for the two-dimensional line-clipping problem.

References

[1]
CONRADI, R., DIDRIKSEN, T. M., AND WANVIK, D. H., EDS. Advanced Programming Environments. Lecture Notes in Computer Science, vol. 244. Springer-Verlag, New York, 1986.
[2]
FOLEY, J. D., AND VAN DAM, A. Fundamentals of Interactive Graphics. Addison-Wesley, Reading, Mass., 1984.
[3]
HOARE, C. A. R., ET AL. Laws of programming. Commun. ACM 30, 8 (Aug. 1987), 672-686.
[4]
NICHOLL, R. A., AND NICHOLL, T.M. Laws about programs with inverses. Rep. 178, Dept. of Computer Science, Univ. of Western Ontario, London, 1987.
[5]
NICHOLL, T. M., LEE, D. T., AND NICHOLL, R. A. An efficient new algorithm for 2-D line clipping: Its development and analysis. Comput. Graph. 21, 4 (July 1987) (also Proc. SIGGRAPH 87), 253-262.
[6]
PARTSCH, H., AND STEINBRUEGGEN, R. Program transformation systems. ACM Comput. Surv. 15, 3 (Sept. 1983), 199-236.
[7]
SPROULL, R.F. Using program transformations to derive line-drawing algorithms. ACM Trans. Graph. 1, 4 (Oct. 1982), 257-273.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 9, Issue 1
Jan. 1990
141 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/77635
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1990
Published in TOG Volume 9, Issue 1

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)34
  • Downloads (Last 6 weeks)5
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2018)Image analysis and computer visionCVGIP: Image Understanding10.1016/1049-9660(91)90020-P53:3(322-365)Online publication date: 12-Dec-2018
  • (2005)Analysis of the nicholl-lee-nicholl algorithmProceedings of the 2005 international conference on Computational Science and its Applications - Volume Part I10.1007/11424758_75(726-736)Online publication date: 9-May-2005
  • (1994)2D line and polygon clipping based on space subdivisionThe Visual Computer10.1007/BF0190066510:7(407-422)Online publication date: Aug-1994
  • (1992)VLSI architectures for image processing and address mapping[Proceedings] 1992 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.1992.230356(1668-1671)Online publication date: 1992

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Full Access

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media