Intersection algorithms for lines and circles

ABSTRACT

This paper presents a unified representation scheme for the implicit equations of points, lines, and circles. An associated set of geometric algorithms operates successfully on degenerate and nearly degenerate geometry, and when necessary produces degenerate geometric results. Computation errors are interpreted geometrically in order to establish preconditions for reliable results and requirements on the resolution of computer arithmetic. The algorithms thus provide a basis for the wide range of geometric constructions required by computer-aided drafting and design systems.

REFERENCES

• 1: Sylvan H. Chasen, Geometric Principles and Procedures for Computer Graphic Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1978
• 2: MIDDLEDITCH, A. E., STACEY, T. W., AND TOR, S.B. A unified representation for points lines and circles. Inter. Tech. Merao ITM-848, CAE Group, Polytechnic of Central London, London, 1984.
• 3: ROGERS, D.F. Interactive graphics and numerical control. CAD J. 12, 5 (Sept. 1980), 253-261.
• 4: SABIN, M.A. The use of piecewise forms for the numerical representation of shape. Ph.D. thesis, Hungarian Academy of Sciences, 1976.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Measurement