Re: determining boundary of a region in n-dimensional euclidean space
- To: mathgroup at smc.vnet.net
- Subject: [mg117199] Re: determining boundary of a region in n-dimensional euclidean space
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Fri, 11 Mar 2011 04:33:50 -0500 (EST)
Nabeel Butt wrote:
> Hi Daniel
> Thanks for your response.Actually the problem is two-fold here.The
> first step is to actually extract the boundary points from a set of points
> in a list.I have found that built-in ConvexHull function in mathematica can
> do for 2-dimensions this extraction process.There exists a program also for
> 3-dimensions written in mathworld.To my best of my knowledge it hasnt been
> implemented in higher dimensions that well in mathematica(was just a random
> google search though !!) . Anyways after we get the list for boundary
> points , like you said I can use Interpolation on list to represent it
> numerically.What I am more interested in is actually extracting the boundary
> points from a set of points -Does there exist more robust convexhull like
> functions for higher dimensions ? Or after having a list of points I can
> send them to another software which helps me get the convex hull in high
> dimensions.Possibly if I can call another software inside mathematica that
> would be great.
> Thanks once again.
> Nabeel
> [...]
Some follow-up in private email indicates that what is needed,
primarily, is a reasonable approximation to an inside-outside predicate
function.
If given sufficiwently many points inside the region, that can be found
with the code below. The idea is to form a NearestFunction from the
point set, and declare an arbitrary point to be "inside" if it is within
some given epsilon of its nearest point in that set.
nf = Nearest[pts];
inRegion[pt : {_Real, _Real, _Real}, eps_Real] :=
TrueQ[Norm[nf[pt, 1][[1]] - pt] < eps]
Here is an example. We'll pick, nonuniformly, points inside the shpere
of radius 1 centered at the origin.
n = 200000;
pts = MapThread[
Times, {RandomReal[1, n], RandomReal[{-1, 1}, {n, 3}]}];
pts = Select[pts, Norm[#] <= 1 &];
Now compute our inRegion predicate function.
nf = Nearest[pts];
inRegion[pt : {_Real, _Real, _Real}, eps_Real] :=
TrueQ[Norm[nf[pt, 1][[1]] - pt] < eps]
To see what it gives, one can plot the region thus defined as below.
reg = RegionPlot3D[
inRegion[{x, y, z}, .05], {x, -1, 1}, {y, -1, 1}, {z, -1, 1},
Mesh -> False]
Offhand I am not sure how to go about this if not presented with a
"large" set of inside points. If you know your region is convex (which I
gather will often be the case for this query) then one way to go about
filling it would be to take some number of points, equally spaced
perhaps, on all segments connecting initial point pairs. Or could try to
dope out how to get the convex hull of the initial points, and maybe use
those for filling in purposes. I myself am not up to speed on how best
to do this. I offer one possibility below.
ComputationalGeometry`Methods`ConvexHull3D[
RandomReal[10, {20, 3}]] // InputForm
I remark that this might (probably will) become obsolete in a future
release. Also I suspect some others who follow this forum will know more
about how to go about this, perhaps using meshes generated by plotting
functions.
If you do succeed in getting a convex hull for the boundary, then yet
another inside-outside approach would be to shoot a segment from query
point northward, say, and count how many faces it hits before going to
infinity. If zero or two then it is outside, if one then inside.
To make this method fast, you might want to bin the faces so that a
given point need not test all of them for intersection. I have not done
this in 3d, but here is a link to some code that might be adapted from
the 2d case.
http://forums.wolfram.com/mathgroup/archive/2009/Feb/msg00519.html
If you have any interest in seeing where that inRegion originated (at
least, in my usage), here is a notebook with an algebraic surface
reconstruction. It turns out that an exact reconstruction, more or less,
was possible. But that is because there were derivable defining
equations. barely so, I might add.
http://download.wolfram.com/?key=VFK26V
Daniel Lichtblau
Wolfram Research