Point generation in polygon

Question

I know about the Halton sequence. But so far I can’t find the formulas by which points are generated. Also worried is the question Halton sequence generates points only in the rectangle? Or can I generate points in any polygon using the Halton sequence? If the Halton sequence generates points only in the rectangle, what other way is there to generate points in the polygon? I need an optimal method for generating points in a polygon. What do you advise? It is advisable to describe the method and give specific formulas.

Answer 1

To generate points with the same distribution as the Halton sequence in a polygon you can just take a rectangle enclosing the polygon - for example take the convex hull of the polygon (assuming it may be concave ), pick two orthogonal directions, say the coordinate axes, project all points onto them, and take the min and max of the projections in each axis - this gives you 4 lines which define the enclosing rectangle. You can then generate the Halton sequence within this rectangle and throw away all the points which don't lie in your polygon. If you have a highly non-convex or self-intersecting polygon you can first subdivide the polygon into convex pieces using this answer and apply the above method to each convex piece separately.

If efficiency is a major consideration, which it may not be if the Halton sequence generation is fast enough, then you can look at finding enclosing rectangles with minimum area - this can be done using this answer. Note that you can always find an enclosing rectangle around a convex shape with area at most twice the shape area but typically it will be closer to 1 if the shape is reasonably regular - for an ellipse it is $4/\pi\approx1.3$.

Generation of Halton Sequence.

$\text{Rev[D_,b_]:=Reverse[IntegerDigits[D,b]]}$

$\text{Halton[n_,b_]:=FromDigits[Rev[n,b]/b^Length[Rev[n,b]],b]}$

$\text{Halton2[n_,b1_,b2_]:=Table[{Halton[i,b1],Halton[i,b2]},{i,1,n}]}$

The above Mathematica function $\text{Halton2[n,b1,b2]}$ generates a Halton sequence in $[0,1]\times [0,1]$ of length $n$ with respect to the bases b1 and b2. Here is a plot of $\text{Halton2[1000, 2, 3]}$:

(If you don't know Mathematica, $\text{IntegerDigits[D,b]}$ returns an ordered list of digits of $D$ in base $b$, $\text{FromDigits[l,b]}$ generates an integer with digits $l$, base $b$. $\text{Reverse[l]}$ returns the reverse of an ordered list and $\text{Table}$ generates an ordered list)

Example

Essentially to generate the $n$-th Halton number base b you take the digits of n base b, reverse them and place a decimal point in front. So $\text{Halton[12,2]} = .0011_2$ since 12 in base 2 is 1100. You generate a Halton point sequence in 2d by pairing up the Halton sequences for 2 different primes. So the 12-th Halton 2d point for the bases 2 and 3 is $(\text{Halton}[12,2], \text{Halton}[12,3]) = (.0011_2,.011_3)$

Filtering out points not in your polygon

If you have an ordered list $\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}$ of $n$ points comprising your convex polygon in anti-clockwise order then a point $(px,py)$ is inside the polygon iff the determinant

\begin{vmatrix} px & py & 1 \\ x_i & y_i & 1 \\ x_{i+1} & y_{i+1} & 1 \end{vmatrix}

is greater than 0 for all $0\leq i\leq n$ where indices are taken mod n.

Figures below show the process of generating the Halton sequence for the enclosing rectangle (Fig 1) then throwing away points outside in the dark region (Fig2).

Fig 1.

Fig 2.