Re: determining boundary of a region in n-dimensional euclidean space
- To: mathgroup at smc.vnet.net
- Subject: [mg117203] Re: determining boundary of a region in n-dimensional euclidean space
- From: Nabeel Butt <nabeel.butt at gmail.com>
- Date: Fri, 11 Mar 2011 04:34:34 -0500 (EST)
Dear Daniel
Most of the time practically my region in d-dimensions is convex
but I really dont need to be very accurate so the inside-outside would work
reasonably fine.
Thanks for all your suggestions.Very useful tips- Ill consider them
all !
best regards,
Nabeel
On Thu, Mar 10, 2011 at 7:53 PM, Daniel Lichtblau <danl at wolfram.com> wrote:
> 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
>
--
"We have not succeeded in answering all our problems.The answers we have
found only serve to raise a whole set of new questions.In some ways we feel
that we are as confused as ever,but we believe we are confused on a higher
level and about more important things."
"Maybe one day we get to see all the beauty present in this world"
Nabeel Butt
UWO,London
Ontario, Canada