GISdevelopment.net --> Application --> Miscellaneous
Mr. N. Subhash Chandra
Research Scholar
Dept. of CSE
JNT University
Hyderabad, A-P, India.
subhashchandra_n@yahoo.co.in
Prof. S. Srinivas
Professor
Dept. of IT
R.M. College of Engineering
Hyderabad, A-P, India
Dr. A. Govardhan
Professor
Dept. of CSE
School of Information Technology
JNT University, Hyderabad, A-P, India.
Email: govardhan_cse@yahoo.co.in
An efficient Decomposition of Polygon Spatial Object into Monotone Pieces with Plane Sweep Algorithm
Mr. N. Subhash Chandra
Research Scholar
Dept. of CSE
JNT University
Hyderabad, A-P, India.
subhashchandra_n@yahoo.co.in
Prof. S. Srinivas
Professor
Dept. of IT
R.M. College of Engineering
Hyderabad, A-P, India
Dr. A. Govardhan
Professor
Dept. of CSE
School of Information Technology
JNT University, Hyderabad, A-P, India.
Email: govardhan_cse@yahoo.co.in
Abstract:
Plane sweep algorithm is a powerful approach for solving problems involving geometric objects in the map. Decomposing an object in the spatial structure for real world system is one of the interesting and challenging issues in Map based applications.
Plane-sweep algorithm is used to solve the intersection problems of n straight line segments in time O(n logn). 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.
The 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 efficient method to decompose polygon spatial object into monotone sub polygons with Plane sweep algorithm.
Introduction
Plane sweep is powerful approach for solving problems involving Spatial objects in the plane. An imaginary horizontal sweep line moves from left to right across the objects. Plane sweep algorithms have been used for variety of problems like map overlay, Voronoi diagrams and hidden surface removal. The plane sweep approach is described in most text books on computational geometry[4,5]. Implementation of plane sweep algorithm usually is straightforward.
Sweep algorithms
Imagine a set O of objects in the plane about which something must be computed. Let us say a question Q need to be addressed. Take a vertical line left of all objects and sweep it right ward direction. During the sweep, make sure that all information relevant to answer Q becomes known when the sweep line passes the objects that give the information. During the sweep we have to maintain the subset of objects that is intersected by the sweep line. Since this subset changes repeatedly, this subset must be maintained in a dynamic data structure. This data structure is called Status structure.
Figure : 1
We also have to know somehow when the status changes, and when we can find bits of information to answer the question Q. This happens at certain positions of the sweep line. These positions are called events and they are given by x-coordinate since we assumed the sweep line to be vertical. We need to store events stored on x-coordinate. The data structure for this purpose is called the event list..
With the plane sweep, a 2-dimensional spatial object problem is solved by using dynamic 1-dimensional data structures.
Known applications of plane sweep related are Voronoi diagrams, map overlay, nearest object[1], triangulation, two-dimensional and three-dimensional point location, shortest paths and many other applications in GIS.
Implementation of plane sweep algorithm is not difficult. A major advantage of sweeping over other methods like divide-and-conquer is that not all objects need in the main memory simultaneously. Objects are needed in the order of their x-coordinates, and only the objects that intersect the sweep line in its current position need be in main memory.
Proposed procedure for Monotone Subdivision.
For applications like triangulation of a polygon Spatial object, inter section problems we can use monotone polygon pieces of spatial object. A process which is used for decomposing an arbitrary polygon into monotone sub polygons is known as regularization. A polygon is monotone if its boundary is composed of a monotone upper chain and a monotone lower chain. This is done by a plane-sweep approach.
The absence of x-monotonicity occurs only at vertices in which the interior angle is greater than 180 degrees and both edges lie either to the left of the vertex or the right. Our algorithm uses the notion of cusp. A reflex vertex – a vertex whose interior angle exceeds 180 degrees is cusp. It is easy to see that a polygon spatial object that is monotone cannot contain cusps.
The algorithm works by decomposing polygon spatial object P into sub polygons with out cusps. It contains two phases, the algorithm removes leftward-pointing cusps as it sweeps across P from left to right, in the second phase the algorithm removes rightward-pointing cusps as it sweeps from right to left.
Figure 2 : Leftward-pointing Cusps and rightward-pointing cusps.
The goal of the algorithm is to remove all cusps that in both the directions. For example regularize(p,left_to_right,p1) sweeps from left to right across polygon p to remove leftward-pointing cusps and appends to list p1. Whenever the sweep line reaches a leftward pointing cusp c, we split the polygon along the chord which connects c to some vertex f to the left of the c. We choose f the rightmost vertex from among those vertices which lie between edges a and e and to the left of sweep line (Figure : 2).
Figure : 3
When a left cusp c is encountered in the sweep, there will be an edge a of the polygon lying above and an edge e lying below. We might consider attaching the left cusp to left end point of one of these two edges, but it might be that neither endpoint is visible to split the vertex. We need to maintain a vertex that is visible to any split vertex that may arise between a and e. We claim that f is visible to every point along the sweep line between a and e. This suggests the following concept, which is defined for each edge a that intersects the sweep line, such that the polygon spatial object interior lies locally below a.
helper(a) : Let e be the edge of the polygon lying below a on the sweep line. The helper is the rightmost vertically visible vertex below a on the polygon chain between a and e.
Events : The end points of the edges of the polygon. These are sorted in the increasing order of x-coordinates.
Sweep line structure : The sweep line structure is a dictionary of active edges those polygon edges which currently cross the sweep line ordered by increasing y-coordinates.
These edges are stored in a dictionary so that the operations of insert, delete, find, predecessor and successor can be evaluated in O(log n) time each.
A transition occurs as sweep line reaches each polygon vertex. The type of transition depends on the type of vertex, where a vertex is classified according to the position of its neighbors relative to the sweep direction.
Event processing : There are six event types based on a case analysis of the local structure of edges around the each vertex. Let c be the current vertex encountered by the sweep.
Split vertex : Search the sweep line status to find edge a lying immediately above c. Add a diagonal connecting c to helper(a). Add the two edges incident to c in the sweep line status, and make c the helper of the lower of these two edges and make c be the new helper of a.
Merge vertex : Find the two edges incident to this vertex in the sweep line status. Delete them both.
Start vertex: Both edges lie to the right of c, but interior angle is less than 180 degrees. Insert this vertex’s edge into the sweep line status.
End Vertex : Both edges lie to the left of v but the interior is less than 180 degrees. Delete both edges from the sweep line status.
Upper-chain verte : One edge is to the left and one to the right, and the polygon interior is below. Replace the left edge with the right edge in the sweep line structure.
Lower-chain vertex: One edge is to the left, and one to the right, and polygon interior is above. Replace the left edge with the right edge in the sweep line structure.
Input polygon contains n vertices. The total number of vertices increases by two for every split that is performed making at most 2n vertices. Each vertex goes through at most two transitions no more than 4n transitions are performed total. Each type of transition may take constant number of dictionary operations taking O(log n) time. Since O(n) transitions are performed the algorithm runs in O(n log n) time.
Conclusion.
This paper explains the procedure for sweep algorithm applications to map related operations. This is also proposed an efficient decomposition of polygon spatial object into monotone pieces with plane sweep algorithm. The complexity of decomposition technique is observed as O(n log n).
References
Plane sweep algorithm is a powerful approach for solving problems involving geometric objects in the map. Decomposing an object in the spatial structure for real world system is one of the interesting and challenging issues in Map based applications.
Plane-sweep algorithm is used to solve the intersection problems of n straight line segments in time O(n logn). 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.
The 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 efficient method to decompose polygon spatial object into monotone sub polygons with Plane sweep algorithm.
Introduction
Plane sweep is powerful approach for solving problems involving Spatial objects in the plane. An imaginary horizontal sweep line moves from left to right across the objects. Plane sweep algorithms have been used for variety of problems like map overlay, Voronoi diagrams and hidden surface removal. The plane sweep approach is described in most text books on computational geometry[4,5]. Implementation of plane sweep algorithm usually is straightforward.
Sweep algorithms
Imagine a set O of objects in the plane about which something must be computed. Let us say a question Q need to be addressed. Take a vertical line left of all objects and sweep it right ward direction. During the sweep, make sure that all information relevant to answer Q becomes known when the sweep line passes the objects that give the information. During the sweep we have to maintain the subset of objects that is intersected by the sweep line. Since this subset changes repeatedly, this subset must be maintained in a dynamic data structure. This data structure is called Status structure.
Figure : 1
We also have to know somehow when the status changes, and when we can find bits of information to answer the question Q. This happens at certain positions of the sweep line. These positions are called events and they are given by x-coordinate since we assumed the sweep line to be vertical. We need to store events stored on x-coordinate. The data structure for this purpose is called the event list..
With the plane sweep, a 2-dimensional spatial object problem is solved by using dynamic 1-dimensional data structures.
Known applications of plane sweep related are Voronoi diagrams, map overlay, nearest object[1], triangulation, two-dimensional and three-dimensional point location, shortest paths and many other applications in GIS.
Implementation of plane sweep algorithm is not difficult. A major advantage of sweeping over other methods like divide-and-conquer is that not all objects need in the main memory simultaneously. Objects are needed in the order of their x-coordinates, and only the objects that intersect the sweep line in its current position need be in main memory.
Proposed procedure for Monotone Subdivision.
For applications like triangulation of a polygon Spatial object, inter section problems we can use monotone polygon pieces of spatial object. A process which is used for decomposing an arbitrary polygon into monotone sub polygons is known as regularization. A polygon is monotone if its boundary is composed of a monotone upper chain and a monotone lower chain. This is done by a plane-sweep approach.
The absence of x-monotonicity occurs only at vertices in which the interior angle is greater than 180 degrees and both edges lie either to the left of the vertex or the right. Our algorithm uses the notion of cusp. A reflex vertex – a vertex whose interior angle exceeds 180 degrees is cusp. It is easy to see that a polygon spatial object that is monotone cannot contain cusps.
The algorithm works by decomposing polygon spatial object P into sub polygons with out cusps. It contains two phases, the algorithm removes leftward-pointing cusps as it sweeps across P from left to right, in the second phase the algorithm removes rightward-pointing cusps as it sweeps from right to left.
Figure 2 : Leftward-pointing Cusps and rightward-pointing cusps.
The goal of the algorithm is to remove all cusps that in both the directions. For example regularize(p,left_to_right,p1) sweeps from left to right across polygon p to remove leftward-pointing cusps and appends to list p1. Whenever the sweep line reaches a leftward pointing cusp c, we split the polygon along the chord which connects c to some vertex f to the left of the c. We choose f the rightmost vertex from among those vertices which lie between edges a and e and to the left of sweep line (Figure : 2).
Figure : 3
When a left cusp c is encountered in the sweep, there will be an edge a of the polygon lying above and an edge e lying below. We might consider attaching the left cusp to left end point of one of these two edges, but it might be that neither endpoint is visible to split the vertex. We need to maintain a vertex that is visible to any split vertex that may arise between a and e. We claim that f is visible to every point along the sweep line between a and e. This suggests the following concept, which is defined for each edge a that intersects the sweep line, such that the polygon spatial object interior lies locally below a.
helper(a) : Let e be the edge of the polygon lying below a on the sweep line. The helper is the rightmost vertically visible vertex below a on the polygon chain between a and e.
Events : The end points of the edges of the polygon. These are sorted in the increasing order of x-coordinates.
Sweep line structure : The sweep line structure is a dictionary of active edges those polygon edges which currently cross the sweep line ordered by increasing y-coordinates.
These edges are stored in a dictionary so that the operations of insert, delete, find, predecessor and successor can be evaluated in O(log n) time each.
A transition occurs as sweep line reaches each polygon vertex. The type of transition depends on the type of vertex, where a vertex is classified according to the position of its neighbors relative to the sweep direction.
Event processing : There are six event types based on a case analysis of the local structure of edges around the each vertex. Let c be the current vertex encountered by the sweep.
Split vertex : Search the sweep line status to find edge a lying immediately above c. Add a diagonal connecting c to helper(a). Add the two edges incident to c in the sweep line status, and make c the helper of the lower of these two edges and make c be the new helper of a.
Merge vertex : Find the two edges incident to this vertex in the sweep line status. Delete them both.
Start vertex: Both edges lie to the right of c, but interior angle is less than 180 degrees. Insert this vertex’s edge into the sweep line status.
End Vertex : Both edges lie to the left of v but the interior is less than 180 degrees. Delete both edges from the sweep line status.
Upper-chain verte : One edge is to the left and one to the right, and the polygon interior is below. Replace the left edge with the right edge in the sweep line structure.
Lower-chain vertex: One edge is to the left, and one to the right, and polygon interior is above. Replace the left edge with the right edge in the sweep line structure.
Input polygon contains n vertices. The total number of vertices increases by two for every split that is performed making at most 2n vertices. Each vertex goes through at most two transitions no more than 4n transitions are performed total. Each type of transition may take constant number of dictionary operations taking O(log n) time. Since O(n) transitions are performed the algorithm runs in O(n log n) time.
Conclusion.
This paper explains the procedure for sweep algorithm applications to map related operations. This is also proposed an efficient decomposition of polygon spatial object into monotone pieces with plane sweep algorithm. The complexity of decomposition technique is observed as O(n log n).
References
- F.Bartling and K.Hinrichs. A Plane sweep algorithm for finding a closest pair among convex planar objects. Lecture notes in Computer Science, pages 221-232. Springer-verlag,1992.
- Philip J. Schneider, David H.Ebery “ Geometric tools for computer graphics” Elsevier publications.
- Michael J.Laszlo “Computational geometry and computer graphics in c++”.
- J.O.Rourke. Computational Geometry in C. Cambridge University Press, New York 1994.
- F.P.Preparata and M.I.Shamos.Computational Geometry: An Introduction. Springer – Verlag,New York,NY,1985.
- Marcvan krevel “Variations on sweep algorithms” :efficient computation of extended viewsheds and class intervals.
- N.Subhash Chandra et.al “Plane sweep algorithm to find point in punctured polygon” Map world forum,2007,hyderabad.