# RegionNearest and neighborhoods

In this previous question we see that RegionNearest isn't quite as 'capable' as Nearest for some things.

Similarly, I need to be able to find a given neighborhood of points on a MeshRegion. With just a set of vertices, one can easily use Nearest with the form Nearest[p,{nDesired,radius}]. Unfortunately, this does not work with MeshRegion, RegionNearestFunction, and friends. For example-

r = BoundaryDiscretizeRegion[Ball[]];
v = MeshCoordinates[r];
p = v[[1]];
f = RegionNearest[r];

f[p]
(* {-0.156227, 0.987698, 0.00678839} *)

f[p, {10, 0.1}]
(* RegionNearestFunction::argx: RegionNearestFunction [...] called with 2 arguments; 1 argument is expected *)


Obviously, I can use Nearest[] on the mesh coordinates and get an answer -

ff = Nearest[v];
ff[p, {10, 0.5}]
(* {{-0.156227, 0.987698, 0.00678839}, {-0.232192, ... *)


But this doesn't take advantage of the graph-connectivity in the MeshRegion data structure. The meshes that I deal with are much more complicated than a simple sphere here, so the Norm[p-q] method it uses in this case gives bad values when there are 'creases' or 'folds' in the surface.

It would seem that getting the n-Ring neighbors of a point p on a MeshRegion should be a pretty straight forward thing (I have plenty of code that does this for GraphicsComplex style data) and maybe even something that should be built in, but I can't quite figure out how to do it (or traverse a MeshRegion as if it were a Graph for what that's worth.) Does anyone have a suggestion for how to take advantage of the new ...Region features for this sort of thing?

(n.b.- more specifically, I need this information to compute the differential geometry at all discrete v in r or, even better, an interpolation for any point in r. I've been playing with some of the new Computational Geometry features but can't quite figure out how to do this on MeshRegions. I again have some code that turns meshes into nonuniform-interpolated functions that I can play with this way, but, again, would like to find a way to do, say, ArcCurvature, FrenetSetretSystem sort of things on surfaces instead of just lines. See this mercifully closed question of mine for related angst.)

If you don't mind using undocumented stuff, you can access lots of useful properties by converting the BoundaryMeshRegion to a MeshObject. In this case "VertexVertexConnectivityRules" is useful. Here I start at vertex 1 and go up to 4 steps out along the mesh edges:

r = BoundaryDiscretizeRegion[Ball[]];

vvcr = GraphicsRegionToMeshObject[r]["VertexVertexConnectivityRules"];

q = Union@Flatten@NestList[ReplaceAll[vvcr], {1}, 4];

HighlightMesh[r, {0, q}, MeshCellShapeFunction -> (Sphere[#, .03] &)]


Alternatively, to get the connectivity graph you could extract the edges with MeshCells:

g = Graph[MeshCells[r, 1] /. Line[{x__}] :> UndirectedEdge[x]];


Then use standard graph functions

HighlightGraph[g, NeighborhoodGraph[g, 1, 4]]


• Nice solution,But if we just want to highlight the boundry like this.Do you have same method? – yode Apr 10 '16 at 7:33
• Thanks @simon-woods ! It's almost as if there should be a Wiki somewhere with the undocumented stuff 'documented' :) – flip Apr 10 '16 at 8:25
• That would be nice - I've lost count of the number of times I've coded something from scratch only to discover it was already implemented in some obscure context. Hopefully some future version will give access to all these internal mesh properties through a documented interface. – Simon Woods Apr 10 '16 at 11:16
• @yode, I guess you could take the complement of the n radius neighborhood and the (n-1) radius neighborhood to get just the boundary vertices. – Simon Woods Apr 10 '16 at 11:18
• Now all of the r["Properties"] make sense! For the 'higher level' BMO, none of them do anything meaningful, but after ToMeshObject they do. For what its worth, this is a (much more complete) version of what I was storing / computing on in all my pre-MeshRegion stuff. – flip Apr 11 '16 at 7:56