Thursday, 31 January 2019

python - Generate random points in polygon. Algorithm question


i created a Random Point Generator in python using the algorithm described here by @whuber. The algorithm is implemented using Shapely, PostGIS and psycopg2. To boost performance pythons multiprocessing and threading libraries are used. The source code can be found in my GitHub Repository. The code generates a total of 57.990.970 Points within 6388 Polygons in ~3517 sec on my Xeon-1231v3 with 16GB Ram.


Procedure SimpleRandomSample(P:Polygon, N:Integer) {
U = Sorted list of N independent uniform values between 0 and 1
Return SRS(P, BoundingBox(P), U)
}


Procedure SRS(P:Polygon, B:Rectangle, U:List) {
N = Length(U)
If (N == 0) {Return empty list}
aP = Area(P)
If (aP <= 0) {
Error("Cannot sample degenerate polygons.")
Return empty list
}
t = 2

If (aP*t < Area(B)) {
# Cut P into pieces
If (Width(B) > Height(B)) {
B1 = Left(B); B2 = Right(B)
} Else {
B1 = Bottom(B); B2 = Top(B)
}
P1 = Clip(P, B1); P2 = Clip(P, B2)
K = Search(U, Area(P1) / aP)
V = Concatenate( SRS(P1, B1, U[1::K]), SRS(P2, B2, U[K+1::N]) )

} Else {
# Sample P
V = empty list
maxIter = t*N + 5*Sqrt(t*N)
While(Length(V) < N and maxIter > 0) {
Decrement maxIter
Q = RandomPoint(B)
If (Q In P) {Append Q to V}
}
If (Length(V) < N) {

Error("Too many iterations.")
}
}
Return V
}

But concerning the algorithm I have an open question. It mentions a U = Sorted list of N independent uniform values between 0 and 1 which i could build using numpy.uniform(0, 1, numberOfValues). But then the algorithm will generate weird results, like one part of the polygon will not have any points in it. I work around this issue by weighting the points to be created by the recursive call using k = int(round(n * (p1.area / polygon.area))).


So my question is why this List of uniform values between 0 and 1 should be used in the first place.




No comments:

Post a Comment

arcpy - Changing output name when exporting data driven pages to JPG?

Is there a way to save the output JPG, changing the output file name to the page name, instead of page number? I mean changing the script fo...