Non-interactive geometric probing: Reconstructing non-convex polygons

We address the problem of characterizing polygonal shapes that can be recon structed from a class of scanners that have asymmetric resolution. We appro ach this problem using the methodology of non-interactive probing. Laser raster scanners provide very high precision along the direction of a scan, but it is not practical to place scans very close to each other. A sy stem capable of generating an omni-directional scan pattern can make a seri es of directional measurements sufficient to permit the reconstruction of a scanned polygon based on the position of edge crossings and the path of th e scanning beam between edge crossings. We provide a procedure to reconstru ct a polygon from such a data set, as well as a characterization of the sha pes that can be reconstructed given a particular scan density. Our system a pplies to both concave and convex polygons, as well as to polygons containi ng holes. (C) 1999 Elsevier Science B.V. All rights reserved.