An efficient algorithm for planar subdivision intersection problems
Zhongmin Guo · Summit (Simon Fraser University) · 1994
Geometric intersection problem is a well developed topic in computational geometry which deals with pairwise intersections among a set of planar objects.A great number of algorithms for detecting whether two objects in the plane intersects have been proposed in the literature.While most of the objects involved in those algorithms are simple objects such as line segments, rectangles and circles, the intersecting properties among polygons are still relatively unknown.In this thesis, we will consider a special case of polygon intersection problems which is called planar subdivision intersection problem.Specifically, given two maps or planar subdivisions of simple polygons, we are required to report all the pairwise intersection of polygotis when one is overlayed on top of the other.This problem arises in spatial databases applications and the popular way to handle this is by means of spatial indexing.In this thesis, we will apply the technique of conlputational geometry to solve the problem.An algoritlim proposed by Mairson reports pairwise intersections between two sets of disjoint line segments in opti~nal time.However, this algorithm does not extend for the polygon case.We propose a generalization of Mairson's algorithm to solve the planar subdivision intersection problem.An implementation of the algorithm is presented and the empirical results are analyzed.years who made my life in Canada memorable.