JTS is very cool, the algorithm is complex but really powerful. All the intersection/union/difference/symmetry difference operations in all kinds of geometry types could be done in a very generic algorithm.
How the cropping works, here is what I understood:
1> The first step is to get all the intersection points between two geometries. The algorithm used here is the sweep-line algorithm.
2> Then it will need to create the split edges based on those intersection points. The split edge is the edge between two intersection points on the same geometry.
3> For each split edge, we have two directed edge end generated from it. One is starting from the beginning, and the other one is starting from the end. For the labelling, if it starts from the beginning, it will use the parent edge label, if it starts from the end, it will filp the parent edge label.
4> Based on those directed edges, we can create a planar graph, and all the vertices in the graph are made from the starting point of the directed edge end.
5> We need compute the labels (topological relationship) of the directed edge and vertice relative to the two different geometries.
a> Each edge end in the edge end map has a label.
b> The edge end star map has its own label, which will be used to update the label of the node.
c> Get the starting edge in the edge end star map, loop through each edge in the edge end map, and compute the labelling location.
d> We also need to merge the label from one directed edge with its symmentric directed edge.
e> Merge the label of the node with the label of the edge end star map.
6> We can determine whether each edge is in result or not based on the topological relationship with two geometries. For each different operation like intersection / union / difference, the criteria to determine whether it is in result is different.
7> We sort each vertice in the planar graph firstly by X coordinate, then by Y coordinate. By looping each vertice in the graph, we will determine how the edges in each vertice link together.
8>For the polygon building, we must determine which edge will actually qualify for the result polygon. There are generally three conditions which will make it qualify for the polygon edge:
8-a. The label of the edge has to show that it is an area edge to both geometries.
8-b. The edge is not an interior area edge. The interior area ege means that the label is an area label for both geometries and for each geometry, both sides are interior.
8-c. The right sides of the edge to both geometries should be inside.
9>We build the maximal edge ring and minimum edge ring based on linking results.
The maximal edge rings will be built firstly, and then we loop through each node. If there are more than one outgoing directed edge which is in result, we must consider the minimal edge ring too. Because if we have one more outgoing edge in one particular vertice, it means that we cannot simply link the edge to form a polygon, we must do another step to form the minimum edge ring, which is based on the maximum edge ring.
10> The actual geometries are built based on the linking results. If there are only maximum edge rings, then build polygons based on that. If there are minimum edge rings, then we need build polygon based on it instead of maximum edge rings.
11> We will collect the geometries in the following order: polygons firstly, lines second, and points last. The lines could be generated by an input geometry of line, or
two touching polygons.
No comments:
Post a Comment