r - 图上顶点子集周围的多边形/轮廓(比 igraph 中的 mark.groups 更精确)

Question

问题定义
我需要生成许多特定的图形，并在这些图形上，通过在它们周围或上方绘制轮廓/多边形/范围来突出显示顶点(节点)的子集(见下图)。

一个图可能有多个这些轮廓/范围，并且它们可能重叠，如果一个或多个顶点属于多个子集。

给定 N 个顶点的图，任何子集的大小都可能是 1..N。

但是，不属于子集的顶点不能在轮廓内(因为这会产生误导，所以这是第一优先级)。这是我的问题的要点。

所有这些图碰巧都具有范围是连续的特性，因为它们所代表的数据仅涵盖顶点的直接连接子集。

所有图都将是无向和连通的(永远不会绘制未连通的顶点)。

可重复的尝试
我正在使用 R 和 igraph包裹。我已经尝试了一些解决方案，但没有一个工作得足够好。
第一次尝试， mark.groups 在 plot.igraph :

library(igraph)
g = make_graph("Frucht")
l = layout.reingold.tilford(g,1)
plot(g, layout=l, mark.groups = c(1,3,6,12,5), mark.shape=1)  
 # bad, vertex 11 should not be inside the contour
plot(g, layout=l, mark.groups = c(1,6,12,5,11), mark.shape=1) 
 # 3 should not be in; image below
 # just choosing another layout here is not a generalizable solution

plot.igraph 调用 igraph.polygon，后者调用convex_hull(也称为igraph)，后者调用xspline。根据我的理解，结果是一种叫做凸包的东西(否则看起来非常好!)，但就我的目的而言，它不够精确，覆盖了不应该被覆盖的顶点。
第二次尝试 contour .所以我尝试实现我自己的版本，基于建议的解决方案 here :

library(MASS)
xx <- runif(5, 0, 1);yy <- abs(xx)+rnorm(5,0,0.2) 
plot(xx,yy, xlim=c( min(xx)-sd(xx),max(xx)+sd(xx)), ylim =c( min(yy)-sd(yy),    max(yy)+sd(yy))) 
dens2 <- kde2d(xx, yy, lims=c(min(xx)-sd(xx), max(xx)+sd(xx), min(yy)- sd(yy), max(yy)+sd(yy) ),h=c(bandwidth.nrd(xx)/1.5, bandwidth.nrd(xx)/ 1.5), n=50 ) 
contour(dens2, level=0.001, col="red", add=TRUE, drawlabels=F) 

等高线图原则上看起来像我可以使用的东西，只要对带宽和级别值进行足够的调整(使等高线足够贴合，使其不覆盖组外的任何点)。但是，此解决方案的缺点是，当电平值太小时，轮廓会中断(不会产生连续的区域) - 所以如果我要那样做，控制连续性(并确定良好的带宽/电平值) fly) 应该自动实现。另一个问题是，我不太明白如何在 igraph 生成的图上绘制轮廓。 : layout.*命令生成看起来像坐标矩阵的东西，但坐标与绘图上的轴坐标不匹配:

# compare:
layout.reingold.tilford(g,1)
plot(g, layout=l, axes=T)

问题:
在图形上绘制此类范围的更好方法是什么 (理想情况下是 igraphs)在 R 中符合上述标准 - 范围仅包括属于其子集的顶点并排除所有其他顶点 - 同时是连续范围？
我正在寻找的解决方案应该可以扩展到我可能需要创建的不同大小和布局的图形(因此使用例如 tkplot 手动调整每个图形并不是一个好的解决方案)。我知道在一些带有顶点组的图上，满足这两个标准在实践中确实是不可能的，但直觉上应该可以实现一些仍然有效的东西 most时间较小(10..20 个顶点)和不太复杂的图形(理想情况下，如果无法绘制完美拟合的范围，则可以检测并发出警告)。要么是 mark.groups的改进方法(不一定在包内，但使用上面提到的船体想法)，或带有 contour 的东西或类似的合适功能，或者建议完全不同的东西会受到欢迎，只要它有效(大部分时间)。
来自讨论的更新:只利用核心 R 或 CRAN 包(而不是外部软件)的功能的解决方案是可取的，因为我最终希望将此功能合并到一个包中。
编辑:根据评论指定最后一段。

Answer 1

评论区的长度不够适合我的答案，所以我把它放在这里，尽管我更愿意将它作为评论发布，因为它不是一个完整的解决方案。

相当长的距离，但首先出现在我脑海中的是 support vector machines .这个想法是你构建一个支持向量机分类器，使用一些非线性核函数(我会尝试径向基函数)根据顶点的坐标将你的点分为两组(入或出)。然后绘制受过训练的支持向量机的分离超平面。一个缺点是您通过这种方式获得的区域可能是无限的(即在某些方向上趋于无穷大)，因此这个想法肯定需要一些进一步的思考，但至少这是一个可能的方向。