# How to return the coordinates of the respective 3 vertexes of a DelaunayMesh's face?

I have a set of points pts1 and a point redPts as below:-

pts1 = BlockRandom[SeedRandom[7]; RandomReal[1, {30, 2}]];
plot1 = DelaunayMesh[pts1]
redPts = {0.68, 0.75}
plot2a = ListPlot[pts1, AspectRatio -> 1];
plot2b = ListPlot[{redPts}, PlotStyle -> Red];
Show[plot2a, plot2b]


As you can see, redPts must lie inside a face of the Delaunay Mesh. I want to have the coordinates of the 3 vertexes of that face. What can I do?

One of my solutions is to check the distance of "all points v.s. red point" and then pick the 3 points with the smallest distance. But is that possible to make use of the DelaunayMesh?

Many thanks!

Update: As noted by Henrik and Rahul the original answer is not the correct approach. An alternative method that gives the correct polygon containing redPt is based on using GraphicsPolygonUtilsInPolygonQ:

ClearAll[f]
f[r_, p_] :=  Pick[#, GraphicsPolygonUtilsInPolygonQ[#, p] & /@ #] &@
MeshPrimitives[r, 2];

Show[plot1,
Graphics[{PointSize[Large], Point@redPt, Opacity[.5, Red],  f[plot1, redPt]}]]


To get the coordinates, use

f[plot1, redPt][[1, 1]]


{{0.67033, 0.84245}, {0.620283, 0.648944}, {0.829905, 0.700287}}

Using Henrik's example (R):

Show[R, Graphics[{PointSize[Large], Point@redPt, Opacity[.5, Red],  f[R, redPt]}]]


Nearest[MeshCoordinates[plot1], redPts, 3]

• This is incorrect; see Henrik Schumacher's answer. – Rahul Jun 17 '18 at 12:23
• Thank you @Rahul. – kglr Jun 17 '18 at 15:45
• @HMC, the original accepted version of this answer is incorrect as noted by Rahul and Henrik. I updated with a version that gives the correct answer. But you might reconsider your acceptance since the accepted version was incorrect. – kglr Jun 18 '18 at 5:57
• Ah, finding another working solution is even better than deleting the post. =) I'd like to mention that your solution tests the point against each triangle and thus has complexity $O(F)$ (where $F$ is the number of faces). There are certainly cleverer ways to find the right triangle, e.g. walks along edges backed up by some BSP-based heuristic for the initial edge. – Henrik Schumacher Jun 18 '18 at 8:49
• I expected RegionMeshMeshNearestCellIndex to do such a clever thing. While it is two orders of magnitude faster for Delaunay meshes with up to 80000 vertices, it starts getting super-linear growing runtime for larger meshes. (This could also be memory related and not related to the actual algorithm). – Henrik Schumacher Jun 18 '18 at 8:51

Finding the correct triangle is a very delicate business. See for example:

pts1 = BlockRandom[SeedRandom[1]; RandomReal[1, {30, 2}]];
R = DelaunayMesh[pts1];
redPt = {0.68, 0.75};
idx = Nearest[MeshCoordinates[R] -> Automatic, redPt, 3];
r = Max@Nearest[MeshCoordinates[R] -> "Distance", redPt, 3];
i = Position[Through[(RegionMember /@ MeshPrimitives[R, 2])[redPt]],
True][[1, 1]];
Show[
Graphics[{
Red, Point@redPt,
Circle[redPt, r]
}],
PlotRange -> All
]


Fortunately, there seems to be a built-in but undocumented function for this task:

j = RegionMeshMeshNearestCellIndex[R, redPt];
MeshPrimitives[R, j]
Show[
HighlightMesh[R, j],
Graphics[{Red, Point[redPt]}]
]


Polygon[{{0.925275, 0.578056}, {0.767697, 0.973336}, {0.544772, 0.562659}}]

• Wow, great example showing that Nearest is not always correct! – Will Robertson Jun 17 '18 at 10:04