1

Suppose I have a set of points $S$ in the plane, which defines a curve in a discretized fashion. This could be $3\cdot 10^3$ points on the unit circle:

circle

But also could be $3\cdot 10^3$ points describing any closed shape, for example:

kirby scatter

My question is as follows: How do I sample points from the inside of these shapes ? I'd like to randomly fill the shape's inside.

ArnoV
  • 1,170
  • 3
  • 8
  • 2
    For your second example, do you want to sample in the entire hull of your points, or do you want to "cut out the holes"? Maybe you could color the parts that you actually want to sample in. – Stephan Kolassa Mar 08 '21 at 08:47
  • The second example is complex because it's made of several "closed" shapes. A goal would be to sample from the inside of every closed "sub-shape". I would however accept an answer which "removes the holes" and fills the resulting shape. – ArnoV Mar 08 '21 at 09:03
  • Acceot-reject suggests finding a simple shape including the complex one and sampling uniformly over the simple shape with rejection when outside the complex shape. – Xi'an Mar 08 '21 at 09:32
  • This is exactly how I would do it, but how do you find whether the point is inside or outside ? I do not have a parametric expression for the inside of the shape. If you know a procedure for this, it would be good enough ! – ArnoV Mar 08 '21 at 09:47
  • If you only have points, then you don't have "shapes" and there is no definite sense of "inside" or outside. Evidently, then, you have additional information. For instance, in the first example perhaps you know the sum of squares of coordinates equals $1$ and that equality (implicitly) defines the boundary of a shape. Or maybe your points are all of the form $(\cos(a),\sin(a))$ and that parameterizes the boundary So: what is this additional information and what form does it take? – whuber Mar 08 '21 at 17:01

1 Answers1

1

If you have a very simple shape, like a disk, or an annulus or a square minus an inscribed disk, you can directly generate samples. For anything more complicated, and indeed the general case, rejection sampling is the way to go: pick $x$ and $y$ uniformly distributed on your canvas and keep $(x,y)$ if it is inside your shape, rejecting it otherwise.

So the key issue is how to efficiently decide whether your sample point is inside or outside a given shape.

As whuber notes, a cloud of points does not make up a shape. Perhaps you are thinking of the convex hull of a cloud of points, but your second example is not convex, so this is probably not what you want to do. So I'll assume you have an ordered list of $n$ points $(p_0, \dots, p_n=p_0)$ that make up a simple closed curve; that is, the connecting segments $p_ip_{i+1}$ and $p_jp_{j+1}$ do not intersect for $i\neq j$, and $p_i\neq p_j$ for all $i,j$, unless $i,j\in\{0,n\}$. This defines an interior and an exterior.

First off, you can do some very simple checks, like calculating the minimum bounding box (just take the minimal and maximal $x$ and $y$ values of your points). If your sampled point is outside that bounding box, you can immediately reject it. (Or simpler: generate new candidates in the bounding box directly.)

Next, perhaps you can inscribe a simple object (or multiple ones), like circles or rectangles, where you can easily test inclusion. If a candidate point is in one of the inscribed objects, it is also in the larger shape.

Finally, you need to test whether your new point $p$ is inside the general shape defined by $(p_0, \dots, p_n=p_0)$, i.e., a polygon. This is the point in polygon problem, which is standard fare in computational geometry. The Wikipedia page offers a number of standard algorithms, and you should be able to find something in computational geometry textbooks, too. Finally, there are definitely implementations in standard libraries. For instance, the sp package for R has an appropriately-named function point.in.polygon(). You can even use such algorithms for points in polygons with holes.

Stephan Kolassa
  • 95,027
  • 13
  • 197
  • 357
  • Re convex hulls: a generalization is the [alpha hull](https://math.stackexchange.com/questions/1928818/difference-between-a-convex-hull-and-alpha-shape). This is one reason I would be reluctant to suggest using convex hulls. Another reason is that the implied shapes in the question are clearly non-convex. – whuber Mar 09 '21 at 16:10