Ralf Hartmut Güting and Zhiming Ding
LG Datenbanksysteme für neue Anwendungen, FB
Fernuniversität Hagen, D-58084 Hagen, Germany
Abstract: In this paper, we propose an improved plumb-line algorithm, the Partial-Scan Plumb-Line (PSPL) algorithm, to solve the point-in-region problem. In the PSPL algorithm, every edge of the region (or polygon) is represented as two half segments, and all half segments of the region are sorted according to their dominating points. This is a standard representation for regions in spatial databases, providing efficient support for many plane-sweep algorithms. To support PSPL additionally a “coverage number” is associated with each half segment. In this way, the algorithm can employ a binary search to quickly find the half segment whose dominating point is closest to the given point, and then access only the neighbouring half segments to evaluate the query, leading to dramatic performance improvements, especially for large regions.
Keywords: spatial databases, plumbline algorithm, point-in-region, databases, algorithms