An optimal O(n log n) algorithm for contour reconstruction from rays

ABSTRACT

We present an optimal algorithm to reconstruct the planar cross section of a simple object from data points measured by rays. The rays are semi-infinite curves representing, for example, the laser beam or the articulated arms of a robot moving around the object. The object is assumed to be a unique simply connected object, and the contour to be reconstructed is a simple polygon having the data points as vertices and intersecting none of the measuring rays. Such a contour does not exist for any given sets of points and rays but only for legal data. In this paper, we prove that the solution to the contour problem is unique whenever such a solution exists. For a set of n points and n rays, the algorithm presented here provides in &Ogr;(nlogn) time, a polygon which is the solution to the contour problem when the data are legal. Updating this contour if a new measure is available can be done in &Ogr;(logn) time. Both results are asymptotically optimal in the worst-case. Moreover, once the solution has been found, we can check if the data are legal in &Ogr;(nlogn) time.

REFERENCES

• AE: Avis D., ElGindy H., Seidel R., Simple On-Line Afgorithmsfor Convex Polygons, Computational Geometry, Ed.G.T. Toussaint, North-Holland, 1985.
• Bo: Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984 [doi>10.1145/357346.357349]
• Be: Bernstein H.J., Determining the Shape of a Convex n-sided Polygon by using 2n+k Tactile Probes, New York University, Courant Institute of Mathematical Sciences, Computer Science Division, Technical Report No. 125, Robotics Report No. 29, June 1984.
• Ch: Chazelle B., IEEE Transactions on information theory, IT-31, p 509, 1985.
• CG: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• CY: Cole R., Yap C., Shape From Probing, Technical Report No. 104, Robotics Report No. 15, New York University,Courant Institute of Mathematical Sciences, Computer Science Division, December 1983.
• CR: Joseph Culberson , Gregory Rawlins, Turtlegons: generating simple polygons for sequences of angles, Proceedings of the first annual symposium on Computational geometry, p.305-310, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323272]
• K: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• L: James J. Little, Extended Gaussian images, mixed volumes, shape reconstruction, Proceedings of the first annual symposium on Computational geometry, p.15-23, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323236]
• OR: O'Rourke, J., Uniqueness of Orthogonal Connect-the-Dots, Johns Hopkins University, 1986.
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• R: D. Rappaport, Computing simple circuits from a set of line segments is NP-complete, Proceedings of the third annual symposium on Computational geometry, p.322-330, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41993]
• RIT: D Rappaport , H Imai , G T Toussaint, On computing simple circuits on a set of line segments, Proceedings of the second annual symposium on Computational geometry, p.52-60, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10521]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Shape
      I.2.9 Robotics
          Subjects: Manipulators
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION

General Terms:
Algorithms, Theory