Professor/ Research schalor
JNT University, Kukatpally, Hyderabad , A-P,
Email: [email protected]
Professor
Dept. of Computer Science, JNT University, Ananthapur, A-P
Email: [email protected]
Professor
School of statistics and humanities, University of Hyderabad, Gabchibouli, Hyderabad, A-P.
Email: [email protected]
Locating an object in the spatial structure for real world system is one of the interesting and challenging issues in GIS applications, which is called a search problem. This possesses various research challenges:
1. Representation of the system
2. Search processing for given representation or independent of representation
3. Types of storage or storage complexity.
Shamos has addressed this problem for two dimensional (2D) environments as an identification of a given point which represents the object in a polygon (that is spatial data type for representing 2D real world spatial object in GIS) is now popularly known as Plane-sweep algorithm.
Plane-sweep algorithm is used to solve the intersection problems of n straight line segments in time O(n log n). In this paper, we consider a set polygon in the plane. The polygons are given by their edges and each edge is given by its two end points.
A feature of the algorithm is that intersection points of the originally given segments need not be known in advance, but are found during the sweep and considered as forthcoming tasks. No back-tracking is needed and no intersecting points are left discovered.
The efficiency of sweeping a geometrical configuration in a plane is based on transformation of a 2D problem into sequence of 1D problem. The 1D problem is significantly simpler than original 2D problem. The projections of line segments that define these 2D objects into 1D sweep line can be totally ordered, permitting logarithmic access time to any object intersected by sweep line. The sweep process consists of breaking down configuration into sequence of slices in which the order of segment projections into sweep line altered. The sequence of slices is obtained by projecting the segment end points on the axis orthogonal to sweep line.
This paper proposes an algorithm to decide whether a given point is inside of a punctured polygon (that is polygon with a hole) by exploring the merits and limitation of the plane-sweep algorithm. It also presents a unifying approach for various types of punctured polygons which arise in spatial object analysis.
