I would like to random sample points within an n-sided polygon. One idea I've thought of is to discretize the area of the n-sided polygon with triangles.
I can assign each triangle a unique number in the range $[1, M]$ where $M$ is the number of triangles. Assuming the triangle areas are equal, I can use a uniform distribution $\sim U(1, M)$ to random sample a triangle and use its centroid as the random sampled point within the polygon.
The problems with this approach are:
(1) It's a discrete approximation since I'm mapping a triangular region to a single value, i.e., the centroid. Is there a straightforward continuous approach?
(2) The assumption that the rectangles have the same area. In practice, if I have some irregular shape, I think it would be quite difficult to get all the triangle areas to be the same. Is there some sort of weighted uniform distribution you could use?
One thought that I had was to say use $\sim U(0,1)$ and for each $A_i$ (area of i-th triangle) we assign a specific range within [0, 1] where the range spans the normalized area of $A_i$. e.g., say you had 2 triangles that discretized some n-sided polygon. Say $A_1 = 50, A_2 = 100$. Then $50/(50+100) = 1/3$ and $100/(150) = 2/3$. So we could take anything within $[0, 1/3]$ and $[1/3, 1]$ from $\sim U(0,1)$ as corresponding to the first and second triangles, respectively.
What are some other approaches?
One approach that I've used with spheres is rejection sampling, but spherical surfaces are quite easily described by an equation, so rejection sampling becomes simply. For an n-sided polygon, this would seem rather difficult as there would be an equation corresponding to each side, so checking whether to accept or reject a random sample would be tedious.
Your idea could work. You could decompose the polygon into triangles, a process known as polygon triangulation. Then choose a triangle randomly, but weighted by the area of the triangle. But then instead of simply choosing the centroid of that triangle, you could then choose a random point within the triangle using this approach.
If you are trying to make this as efficient as possible in a computer program, one source of inefficiency could be the polygon triangulation (although the Wikipedia page mentions the fan triangulation [given that the polygon is convex] which would be simple and efficient). It would depend on how the polygon is stored in memory.
Edit to clarify choosing the triangle randomly: Let's say the triangles are given by $T_1, T_2, ..., T_k$ and the corresponding weights are given by $A_1, A_2, ..., A_k$. Then after generating a random $x \in [0, \sum_{i=1}^k A_i)$, if $x < A_1$, the chosen triangle would be $T_1$. If $A_1 < x < A_1 + A_2$, the chosen triangle would be $T_2$. In general if $\sum_{i=1}^{m-1} A_i < x < \sum_{i=1}^{m} A_i$, the chosen triangle would be $T_m$. This is pretty much what you said, but all multiplied by the area of the polygon.