前几天R-help邮件列表中有人问如何计算Alpha Shape（注：Alpha Shape可以看作是闭包Convex Hull的扩展，它可以通过调整Alpha参数计算更精细的“闭包”从而大致描述平面或空间上一群点的外形），我给了一个K-Means聚类的做法：
set.seed(1234)
devAskNewPage(ask = TRUE)
par(pch = 20)
dat = iris[, 1:2]
n = nrow(dat)
for (k in 2:30) {
ch = integer()
cl = kmeans(dat, k, 50)$cluster
plot(dat, main = paste("k =", k))
for (i in unique(cl)) {
idx = chull(tmp <- dat[cl == i, ])
ch = c(ch, as.integer(rownames(tmp[idx, ])))
polygon(tmp[idx, ], border = NA, col = rgb(0, 0, 0, 0.2))
}
plot(dat, main = paste("Polygon shape when k =", k))
polygon(dat[ch, ], col = rgb(0, 0, 0, 0.2)) # need to be ordered
}
通过选择不同的k，可以逐步描述出点的外形，不过这种方法太粗略，而且最后找出来的多边形的顶点也没有排序，因此不是太好的解决方案。Alpha Shape的算法之一是用某个固定半径的圆去“套”一对一对的点，当一对点都刚好落在圆上而且圆内不包含任何其它点的时候，这两个点就是形状的边界点。通过这样的方法找出所有的边界点，便描述出了Alpha Shape。有兴趣的看官可以把这几句话转化为R代码试试。注意圆的半径是可变的参数，不同的半径对形状的描述精确程度有不同，显然当半径很大时，算法找出的就是闭包。
写出代码的看官请不吝分享一下：）
赞赏
作为一名没有固定工作的自由职业者，我非常感谢您通过捐赠的方式来支持我的写作和开源软件开发。当然，捐赠纯属自愿。无论金额多少，都是一片诚挚的心意。支付方式如下：
| 微信 | ← 奋力支开它俩 → | 支付宝 |
|---|---|---|
 |
其它爱心通道 ↓ Venmo: @yihui_xie Zelle: xie@yihui.name PayPal: xie@yihui.name |
 |
若使用 Venmo/Zelle/Paypal，请添加备注“gift”或“donation”，以免捐赠被视为我的可税收入。若使用 Paypal，支付类型请选 Family and Friends，而不要选 Goods and Services。
在不影响生活的前提下，我会将收到的捐赠以尽量大的比例回馈给开源社区和慈善机构。作为参考，2024-25 年间我共收到约三万美元捐赠，完税后我转手捐出了一万五千美元。