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

**Re: non linear system with 8 equations**

**Re: CDF Player vs. Mathematica browser plug-in**

**Re: determining boundary of a region in n-dimensional euclidean space**

**Re: determining boundary of a region in n-dimensional euclidean space**