There is a polygon of arbitrary shape, the coordinates of the vertices are known. How can I randomly choose a random point so that it is in it , and not on the border or at all outside its region.
At the moment, thought so
1) Take the highest, lowest, rightmost, leftmost and connect them so that the figure "fit" into the rectangle.
2) Take random points from a rectangle
3) Check for belonging to a polygon
4) If not, repeat.
But something I do not understand how to perform the third.
The classical verification that a point belongs to a polygon - a ray is launched from it, and the number of intersections with the sides of the polygon is considered (in fact, they count the number of side-segments having a common point with the ray). If it is even - a point outside is otherwise inside. That she is not on the side is checked separately.
For simplicity of the software implementation, the beam is allowed only horizontal (or only vertical). And they control that neither side lies on the ray.
Source: https://ru.stackoverflow.com/questions/617393/
All Articles