David M. Mount
ABSTRACT
A simple algorithm is presented for detecting whether two preprocessed simple polygons intersect one another. Given a simple polygon, A, in O(n log n) time and O(n) space we preprocess A constructing an enveloping triangulation called a scaffold. To determine whether two preprocessed polygons A and B overlap another, we start with these two envelopes and successively strip away overlapping triangles of the scaffolds until we either detect an intersection between the objects or until we have succeeded in separating them spatially. The running time of the intersection query depends on the complexity of the minimum link polygonal curve separating the two objects. Given two preprocessed simple polygons A and B, placed at arbitrary locations in the plane we can determine whether these polygons intersect one another in O(m log2n is the total number of vertices and m is the complexity of a minimum link polygonal curve separating A from B. We generalize this to the problem of computing arbitrary Boolean functions of two preprocessed polygons.
- 1.B. Chazelle. Triangulating a simple polygon in linear time. In 31st Annual IEEE Symposium on Foundations of Computer Science, pages 220- 230, St. Louis, 1990.Google Scholar
Digital Library
- 2.B. Chazelle a.nd D. P. Dobkin. Intersecion of convex objexts in two and three dimensions. Journal of the ACM, 34:1-27, 1987. Google ScholarDigital Library
- 3.B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. In (In Proceedings of the 1991 ICALP) Springer Lecture Notes in Computer Science, number 510, pages 661-673, New York, 1991. Google ScholarDigital Library
- 4.B. Chazelle and L. J. Guibas. Visibility and intersection problems in plane geometry. Disscrete and Comptational Geometry, 4:551-581, 1989.Google ScholarDigital Library
- 5.L. P. Chew and K. Kedem. Placing the larg;est sirnilar copy of a cmwex polygon alnong polygonal obstacles. In Fifth ACM Symposium on Computational Geometry, pages 167-173, Saarbruchen, West Germany, 1989. Google ScholarDigital Library
- 6.D. P. Dobkin and D. G. Kirkpatrick. Determining the separation of preprocessed polyhedra: A unified approach, in Automata, Languages and Programming: 17th internatzonal Colloquium, Lecture Notes in Computer Science, volume 443, pages 400-413, Warwick University, England, 1990. Springer Verlag. Google ScholarDigital Library
- 7.H. Edelsbrunner. Computing the extreme distances bewteen two convex polygons. Journal of Algorithms, 6:213-224, 1985. Google ScholarDigital Library
- 8.S. J. Fortune. A fast algorithm for polygon containment by translation. In (In Proceedings of the 1985 ICALP) Sprznger Lecture Notes in Computer Science, pages 189-198, New York, 1985. Google ScholarDigital Library
- 9.L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics, 4:74-123, 1985. Google ScholarDigital Library
- 10.J. Hershberger and S. Suri. Private communication.Google Scholar
- 11.T. C. Kao and D. M. Mount. An algorithm for computing compacted Voronoi diagrams defined by convex distance functions. In Proceedings of the Third Canadian Conference on Computational Geometry, pages 104-109, Vancouver, British Columbia, 1991.Google Scholar
- 12.D. Leven and M. Sharir. Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams. Discrete and Complational Geometry, 2:9-31, 1987.Google ScholarDigital Library
- 13.F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer Verlag, New York, NY, 1985. Google ScholarDigital Library
- 14.H. Samet. The Design and Analysis of Spatial Data Structures. Addison Wesley, Reading, Mass., 1990 Google ScholarDigital Library
- 15.S. Suri. A linear time algorithm for minimum link paths inside a simple polygon. Computer Vision, Graphics and Image Processing, 35:99-110, 1986. Google ScholarDigital Library
Index Terms
- Intersection detection and separators for simple polygons
Recommendations
Decomposing a simple polygon into pseudo-triangles and convex polygons
In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-...
Efficient visibility queries in simple polygons
We present a method of decomposing a simple polygon that allows the preprocessing of the polygon to efficiently answer visibility queries of various forms in an output sensitive manner. Using O(n3 log n) preprocessing time and O(n3) space, we can, given ...
Minimum rectangular partition problem for simple rectilinear polygons
An O( n log log n ) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P , a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical ...
Comments