Remove overlapped regions in polygon sets, while ensuring that the intersection boundaries are minimized. This program is especially suitable for image moisaicing (GIS, SFM)..
- Polygon assignment: Assinging polygons. As shown in Figure 1(a), assume the user assigns two ranges F1 and F2, each forms one polygon R1 and R2 respectively.
- Polygon overlap detection: Using 2-D polygon boolen operations to detect all overlapped polygon pairs. Calculate the intersection polygon, difference polygons and the crossing points for each capture range pairs. As shown in Figure 1(b), the polygons R1 and R2 intersect to each other and form an intersection polygon ( R1 ∩ R2 ) and two difference polygons ( R1 - R2, R2 - R1 ). The R1 and R2 crossing points ( P1, P2, P3, P4 ) are estimated.
- Shortest path trimming: For each intersection polygon, provide it with a graph, where vertices are corners of intersection polygon, edges are connected to any vertices if the line between the two vertices is entirely within the intersection polygon. Using Dijkstra algorithm to find the shortest path of each adjacent crossing points pairs sequentially. Finally, adjusting the overlap region according to the shortest path. As shown in Figure 1(c), the shortest paths between P1 to P2, P2 to P3, P3 to P4, and P4 to P1 inside R1 ∩ R2 are S1,2, S2,3, S3,4, and S4,1, respectively. The overlap region R1 ∩ R2 and the differencies R1 - R2 and R2 - R1 are trimmed and modified to R1 ∩ R2' , R1 - R2' , and R2 - R1' according to these paths (In the figure, the upper lines are correspondent to the mark "'").
- Polygon Assignment: Assigning modified difference polygons to the corresponding range. Then, assign modified overlap polygons to the range that results in the minimum border distances. As shown in Figure 1(c), the overlap eliminated ranges F1 and F2 are assigned as R1 - R2' and R2 - R1' respectively. Now, if the modified overlap polygon R1 ∩ R2' is assigned to range F1, the generated border distances between F1 and F2 would be |S1,2|+|S3,4|. While, if the modified overlap polygon R1 ∩ R2' is assigned to range F2, the generated border distances would be |S2,3| + |S4,1|. Since |S2,3| + |S4,1| < |S1,3| + |S4,1|, the polygolns of overlap eliminated range F2 is R2' , which is the combination of R1 ∩ R2' and R2 - R1', while the polygons of overlap eliminated range F1 is R1', which is R1 - R2', as shown in Figure 1(d).
- Include header files
- Using MyPolygonSmartPtrs to declare polygons ( Clock-wise points, the first point must be identical to the last point, no self-intersection, no inner ring)
- Declare OverlapElimination
- (Optional) Use OverlapElimination::showPolys() function to visualize original polygons
- Use OverlapElimination::showPolys() function to perform overlap elimination algorithm and get result. The result is an unordered_map type, key: the index of the original polygon, value: the corresponding overlap eliminated polygons
- (Optional) Use OverlapElimination::showResults() function to visualize overlap eliminated result.
//1
#include "types.h"
#include "my_polygon.h"
#include "overlap_elimination.h"
int main() {
MyPolygonSmartPtrs polys{
MyPolygon(Point_xys{ {0, 2}, { 0,4 }, { 6,4 }, { 6,2 },{0, 2} }),
MyPolygon(Point_xys{ {4,0}, { 4,6}, { 10,6}, { 10,0},{4,0} }),
MyPolygon(Point_xys{ {2,3}, { 2,8}, { 12,8}, { 12,3},{2,3} })
}; //2
OverlapElimination overlapEliminator; //3
overlapEliminator.showPolys(polys); //4
std::unordered_map<int, MyPolygonSmartPtrs> result=overlapEliminator.run(polys); //5
overlapEliminator.showResults(result); //6
}