1

How to generate particles in 2D space using uniform random distribution such that there are triangular or diamond shaped holes within?

aks
  • 136
  • 1
  • 1
  • 6
  • If you use a random particle system, the "holes" between particles will be most probably _random_. Maybe what you're looking for is a _fractal_ (http://en.wikipedia.org/wiki/Sierpinski_carpet)? – Paweł Stawarz Jun 22 '14 at 21:51
  • `random` is a good tag for this post! It's not really a good match for Stack Overflow as it isn't specific enough (maybe add your code so far or try Programmers stack exchange?) - Anyway, to get you started: you could use any number of **monte-carlo** methods to achieve this. In essence you pick random points, check to see if they fit within your distribution, if not, discard and pick another random point. very simple, but not super efficient. More info here: http://en.wikipedia.org/wiki/Monte_Carlo_method – Matt Coubrough Jun 22 '14 at 21:51
  • I actually want to do something opposite of this. http://stackoverflow.com/questions/14021381/matlab-generate-and-plot-a-point-cloud-distributed-within-a-triangle/24356025#24356025 – aks Jun 22 '14 at 21:53
  • Well the method I suggested can achieve that. Pick a 2d point, if it's in the region you want, accept it otherwise reject it. As @pjs mentioned, it can take a lot of attempts to actually get the number of samples you require (which is why it's not efficient) but it does exactly what you need. – Matt Coubrough Jun 22 '14 at 22:05

2 Answers2

1

Acceptance/Rejection - define your cutout areas, generate points uniformly over the 2-d space, and if the result lands in a cutout reject it and try again. Probability of acceptance will be p(accept) = 1 - Area(cutouts) / Area(2-d_generating_space), and the expected number of attempts to generate will be the inverse of that. For example, if the holes make up 80% of your space then p(accept) = 0.2 for a given trial and on average it will take 5 attempts to get an acceptable point.

pjs
  • 18,696
  • 4
  • 27
  • 56
  • how shall i define cutout area for a diamond shape with vertices and centre known? Actually the cuouts are not random. I know their positions. – aks Jun 22 '14 at 22:06
  • If you know the vertices, you can derive the four lines that are the boundaries of the diamond. In order to be in the diamond, a point must be below the upper right and upper left lines, and above the lower left and lower right lines. A point is in the diamond only if it satisfies all four bounds simultaneously. – pjs Jun 22 '14 at 22:10
  • 1
    As an example, if your vertices were `{(1,0), (0,1), (-1,0), (0,-1)}`, then your constraints for an `(x,y)` pair to fall within that diamond would be `y >= -x - 1`, `y >= x - 1`, `y <= 1 - x`, and `y <= x + 1`. – pjs Jun 22 '14 at 22:36
0

I would start off with the triangle case, since the diamond case is really the same as having two triangles.

Here is another explanation of pjs' algorithm:

  1. Define your 2-d space in terms of x-min, x-max, y-min, y-max.
  2. Define your a set of triangles you are cutting from in terms of triangle1[point1, point2, point3] ... triangle_n[point1, point2, point3].
  3. Pick how many points you want to generate, call this numberOfPoints.
  4. Iterate over the numberOfPoints.
    1. Pick a random value within your x-range (from x-min to x-max)
    2. Pick a random value within your y-range (from y-min to y-max).
    3. This is your x,y position for your new random point.
    4. Check to see if this fits within any of your cutting triangles (you will have another loop here) and can use this, or another containment test.
    5. If it is within one of the cutting triangles, throw it away and do not increment your counter. Otherwise, you have successfully added a point.

There are ways to do this more efficiently, than checking every single point against every single cutting triangle. This is an OK first approach for not too many triangles.

Community
  • 1
  • 1
Brian Stinar
  • 1,080
  • 1
  • 14
  • 32