Existing function for generating of random point in polygon in PostGIS may take a very long time in narrow and long polygons because the functions have to test lots of points that fall within bounding rectangle but outside actual polygon. Examples are here and here.
The idea is to use a function to subdivide bounding rectangle recursively and process only tiles that overlap with the polygon:
- subdivide the bounding rectangle into smaller rectangles (2, 4, or more, whichever is easier)
- randomly pick a rectangle
- create an intersection of the rectangle with the original polygon, return to the previous step if intersection is empty
- check if the ratio between the areas of the rectangle and intersection is big enough * ratio 1:10 means that search for a point in polygon will take roughly 10 iterations
- if ratio is small enough return the result of normal random point function
One more idea is to modify the point-in-polygon algorithm:
- Drop a random point inside the bounding rectangle
- if it is inside the polygon return the result, if not go to the next step
- create a straight line between the original point and a random point on the boundary of the binding rectangle (this can be done by either choosing a random direction and then finding intersection with the binding rectangle or by selecting a point on the boundary rectangle within a random distance from one of the rectangle corners)
- clip the line with the polygon, repeat the previous step if clipped line is empty
- random select a segment of the clipped line
- create a point on the segment at a random distance from the segment starting vertex (is there a function in PostGIS for that?)
Or is it possible to rig polygon centroid function to produce a random point instead of the centroid?
Plus there should be an option to create many random points inside a polygon in one step.