computational geometry - Generating random polygons from a given triangulation of points

Given a triangulation $T$ of a planar set point $S$, we would like to randomly generate a polygon (hamiltonian cycle) $P$.

However, it has been proved that Hamiltonian Circuit Problem on maximal planar graphs is NP-complete.

So, I suppose that uniformly random generation of such polygons is hard.

A polygon on $n$ points can be decomposed in $n-2$ triangles. So, the dual graph of a polygon is a tree of $n-2$ nodes.

That implies that if we could count the induced trees of size $k=n-2$ (where $n$ is the size of $S$) on the dual graph of a triangulation (which is a 3-connected cubic planar graph), we could count the hamiltonian cycles of a maximal planar graph (planar point set triangulation). So counting the induced trees of size k on 3-connected cubic planar graph is also NP-complete.

So my question is. Is there any approximation algorithm (e.g. Markov Chain Monte Carlo) which deals with the counting of hamiltonian cycles of maximal planar set points or the induced trees of size k on 3-connected cubic planar graph ?