Generating a distribution of points relative to closed surface (alphshape)

Is it possible to generate a set of points in a random distribution relative to a known surface? As in, a beta distribution upon an alphashape might have a u-shaped density of points if it was averaged over its normals.

Not surprised I can't find anything, but this is a shot in the dark to avoid needing to do some sort of horrific means of layering and pruning uniform points until they add up to a distribution.

[Walter Roberson]

alphashapes are at least 2D, but "beta distribution" used without qualification would be a function of one variable.

Multivariate beta distributions do exist; see for example https://stats.stackexchange.com/questions/87358/how-to-construct-a-multivariate-beta-distribution

[John D'Errico]

An alpha shape may be arbitrarily complex in shape. Trying to extend some sort of 1-dimensional distribution like a beta, into 2 or more dimensions on such an arbitrarily shaped domain will likely be nearly impossible. At best, any ad hoc scheme that does as you wish is the best you can do. Horrific? Yes. Coming up with something that has any valid statistical basis? More horrific yet.

[Walter Roberson]

If the alpha shape were a convex hull, then you could probably study Roger Stafford's randfixedsum file exchange contribution to see how to draw random numbers fairly.

(It has been some time since we heard from @Roger Stafford . I recall that he retired at over 80... I hope he is still doing well.)

[Carson Purnell]

I'm not seeing how either of those methods could be applied here. Even being able to draw points solely into the target area would be of huge use, but they assume that part.

And I am referring to distribution in the sense only as a density curve. It need not reflect any statistical information whatsoever, it just needs to have controllable density characteristics - specifically a peak near each inner/outer extremity.

[Walter Roberson]

specifically a peak near each inner/outer extremity.

I suggest you provide a mock-up diagram so we can understand what you are trying to do.

[Carson Purnell]

I can't provide a diagram that is useful. I want to create a density distribution of points that varies along the normals of a complex 3d shape. Imagine a shell of points around a sphere surface, with a skewed density towards for example the outside of the sphere radius. I could do this with spheres via spherical coordinates and generating radii with the distribution I want, but this does not work for complex surfaes.

[John D'Errico]

I've not seen any activity from Roger at all in the last few years. But I don't think the ideas from randfixedsum would apply here, though it has been a while since I looked at the code.

Regardless, it may be possible to help you, if I can understand the problem, AND if you are not that terribly worried about the true distribution of the points.

You have a 3-d alpha shape. It would want to be a simple one, without internal holes in it, and not disjoint pieces. If the latter was the case, you could always split the problem into separate pieces anyway.

If the problem was truly a convex hull, it would become easier, since then every point could see the centroid, for example (and that would make it a great deal simpler.) But an alpha shape may be far more complex than that. So is your alpha shape at least close to being a convex domain? For example, typically when I worked with alpha shapes in three dimensions, they corresponded to color gamuts, which were not that nasty in general. At most, a color gamut has some gentle concavities in the surface, but they were usually pretty simple things.

But I think I could offer some ideas on how to solve your problem, at least in a moderately ad hoc way, where the region near the surface of the domain is more heavily sampled, and the density would drop off in some moderately controllable fashion. Would that be sufficient?

[Carson Purnell]

Possibly. I need a sort of bimodal distribution, approximately the sum of two skewed densities centered on the surface, if it works one direction the other should be achievable by similar means, no?

[John D'Errico]

Um, This is far more of a problem than you think. Yes, it seems like it would be possible. But what makes sense in one dimension need not always make sense in higher dimensions. And any such scheme will have flaws. But I'll try to offer a few options for you in an answer that I'm writing now, all of which should be efficiently computable.

Answer 1

[John D'Errico]

Ok. I''ll offer a couple of solutions. Recognize that nothing will be perfect, since these are ad hoc solutions, and an alpha shape can be arbitrarily nasty. As well, you have not been terribly clear about exactly what distribution you want or need. (Sort of like a beta is not a mathematical definition I could use.) So at best I can only do something completely ad hoc.

I've attached a piece of code (randtess) that I should have posted on the FEX many years ago. But I never did, even though I've written similar codes many times in various incarnations. Oh well. The solutions I will offer here are based on that code.

I've given an example here, based on a 2-d alpha shape, since plotting in 3-d leaves things more difficult to visualize.

S = alphaShape(rand(100,2));S.Alpha = 0.4;
plot(S)

As you can see, it is an alpha shape, but not a severely concave one. Even so, it will offer some issues we would need to deal with.

Next, I'll use the randtess code to generate a set of points that lie uniformly distributed around the perimeter, and then a second set of points that lie uniformly distributed inside the volume.

xy1 = randtess(10000,S,'s'); % surface sample
N = 10000; % 10000 points to be generated inside the domain
xy2 = randtess(N,S,'v'); % volume sample

plot(xy2(:,1),xy2(:,2),'.')
title('Initial uniform sampling')
hold on
H = plot(S);
H.FaceAlpha = 0.1;
hold off

% for each internal point, find the nearest point on the boundary. Even
% Though the boundary was sampled randomly, the sampling is a
% sufficiently dense one that the nearest point on the boundary will be
% close to the truly nearest point. KNNSEARCH will find the closest point,
% and do so efficiently.
[IDX,D] = knnsearch(xy1,xy2);

% An important thing to note is that the closest boundary point will ALWAYS
% be directly visible to the point inside. So any line segment that
% connects the two points will be entirely inside the simplicial complex.
% next, choose a point randomly along that line segment. Uniform will be
% sufficient here.
r = rand(size(xy2,1),1);
xy3 = r.*xy2 + (1-r).*xy1(IDX,:);
plot(xy3(:,1),xy3(:,2),'r.')
hold on
H = plot(S);
H.FaceAlpha = 0.1;
hold off

As you can see, the points are now non-uniformly sampled, with a bias towards the surface of the region.

The problem is that in the direction of the surface, towards ANY external vertex of the alpha shape with a convex corner, the sampling will have fewer points. So there will be sparsely sampled regions internally. Conversely, any external concave vertex will attract points using this scheme. This is clearly a problem, but there will be similar flaws no matter how we try to solve the problem.

Note that I used a random sampling of the perimeter as merely a convenience. Since that perimeter sampling is a dense one, the closest point on the perimeter will be a very close approximation to the closest point from the perimeter random sample. I could have used other schemes for the 2-d case, but when I go to three dimensions, the closest point on a surface is not as easy to locate.

But if you think about how I solve the above problem, I started with a uniform internal sampling, and then migrated those points somewhat randomly towards the boundary.

A second option is to start with the perimeter random sampling, and then to migrate those points inwards. This could also be done, of course, but it too would have flaws. So I might have done this:

muxy = mean(S.Points,1);
% The value of rexp should be greater than the dimension of the space.
% since this is a 2-d problem, we need rexp to be at least greater than 2.
% values of rexp less than 2 would sample the domaim more densely towards the
% centroid.
rexp = 3.75; 
r = rand(N,1).^(1/rexp); 
xy4 = xy1.*r + (1-r).*muxy;
plot(xy4(:,1),xy4(:,2),'r.')
hold on
H = plot(S);
H.FaceAlpha = 0.1;
hold off

While thois seems to be a better solution than the first, it too has flaws. A flaw of this scheme is, IF the alpha shape was a more extreme one with deep concavities in the perimeter or even internal holes, then some points might actually end up outside of the alpha shape. For example as an extreme case, consider how this would work:

S.Alpha = 0.10;
plot(S)

Fugetaboutit. I would give up in that case. :) Again, if you would do anything like this with an alpha shape, it needs to be a fairly tame alpha shape, else expect complete crap as a result.

The same schemes would work in 3 dimensions. (I wrote randtess to run only in 2-d or 3-d. But the MATLAB alpha shape does not run in higher dimensions either. I think an alpha shape code I wrote many years ago could handle higher dimensions. Such is life.)

For example:

S = alphaShape(rand(100,3));S.Alpha = 0.5;
plot(S)

xyzs = randtess(10000,S,'s');
muxyz = mean(S.Points,1);
rexp = 6; % larger values of rexp will have the points more heavily weighted towards the boundary.
r = rand(N,1).^(1/rexp); 
xyz = xyzs.*r + (1-r).*muxyz;
plot3(xyz(:,1),xyz(:,2),xyz(:,3),'r.')
hold on
H = plot(S);
H.FaceAlpha = 0.1;
H.EdgeColor = 'none';
hold off

I'm not sure how to convince you easily that this will bias the sampled points to lie near the boundary surfaces of the alpha shape, except to see that it does so for the 2-case. I could probably write a few more pages, with 3-d histograms showing that the points are less frequently in the interior of the shape. Or, you could try to trust me. ;-) Anyway, it should work. Again, all totally ad hoc.

[Carson Purnell]

While these specific methods won't do the job, randtess looks like >50% of capabilities I am looking for, getting right to generating points at the shape. Avoids most of the horribleness of needing to prune 1e7 or so random points multiple times. I just need to modify randtess to generate the points by a certain density, not as a count.

Idea: generate alphashapes of the shell/inner/outer surface separated by the distance I want ~d. Fill the shell volume itself with a layer of points, and each inner/outer surface with points. Blur each set with random vectors to get the distribution I want, hopefully without any significant internal accumulation bias.

[John D'Errico]

What ever works for you.

[Carson Purnell]

It works! Now just to input points as density.