Generating a distribution of points relative to closed surface (alphshape)
15 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Carson Purnell
el 25 de Feb. de 2023
Comentada: Carson Purnell
el 28 de Feb. de 2023
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.
9 comentarios
John D'Errico
el 27 de Feb. de 2023
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.
Respuesta aceptada
John D'Errico
el 27 de Feb. de 2023
Editada: John D'Errico
el 27 de Feb. de 2023
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.
3 comentarios
Más respuestas (0)
Ver también
Categorías
Más información sobre Bounding Regions en Help Center y File Exchange.
Productos
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!