Open AccessAn Algorithm to Generate Random Points in Polygon Based on Triangulation
Author(s) -
Zhimin Xu,
Li Zhang,
Rui Ma
Publication year - 2020
Publication title -
iop conference series. earth and environmental science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.179
H-Index - 26
eISSN - 1755-1307
pISSN - 1755-1315
DOI - 10.1088/1755-1315/428/1/012064
Subject(s) - polygon (computer graphics) , triangulation , algorithm , point (geometry) , minimum weight triangulation , computer science , mathematics , delaunay triangulation , bowyer–watson algorithm , geometry , telecommunications , frame (networking)
Random point generation plays an important role in assisting random sampling and is widely used in various disciplines. This paper proposes a new algorithm to generate random points in polygon based on Triangulation. Firstly, the polygons are triangulated, and then the number of random points in each triangle is allocated according to the triangle area. Finally, the given number of random points is generated inside the triangle. In the experiment, the results showed that the proposed algorithm is 20 times faster than the algorithm in QGIS software on average. And with the increase of the complexity of the polygon, the advantages of this algorithm are more obvious.