.png){kind=icon}
Return
A parallel method to accelerate spatial operations involving polygon intersections
.png){kind=icon}
PRE
AI
DOI：10.1080/13658816.2018.1508689.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Polygon intersection is an important spatial data-handling process, on whichmany spatial operations are based. However, this process is computationally intensive because it involves the detection and calculation of polygon intersections. We addressed this computation issue based on two perspectives. First, we improved a method called boundary algebra filling to efficiently rasterize the input polygons. Polygon intersections were subsequently detected in the cells of the raster. Owing to the use of a raster data structure, this method offers advantages of reduced task dependence and improved performance. Based on this method, we developed parallel strategies for different procedures in terms of workload decomposition and task scheduling. Thus, the workload across different parallel processes can be balanced. The results suggest that our method can effectively accelerate the process of polygon intersection. When addressing datasets with 1,409,020 groups of overlapping polygons, our method could reduce the total execution time from 987.82 to 53.66 s, thereby obtaining an optimal speedup ratio of 18.41 while consistently balancing the workloads. We also tested the effect of task scheduling on the parallel efficiency, showing that reducing the total runtime is effective, especially for a lower number of processes. Finally, the good scalability of the method is demonstrated.
Keywords:
Polygon intersection
boundary algebra filling
parallel computing
workload balance
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
5.1
Papers:
2.7K
Citations:
9.3K
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSaveAn efficient algorithm for clipping operation based on trapezoidal meshes and sweep-line technique
PREAI
ShareSave
View more