这是一个人类 child 可以做的事情,但我需要一台电脑来做:D
猜猜你有一个点 P(x,y) 并且你有一个点数组
A = [P1, P2, P3, …]
我基本上需要得到的是3点
- 围绕P形成一个三角形
- 从围绕 P 的那些中形成尽可能小的三角形
当然,我可以通过计算所有可能的三角形来暴力破解它,如果它们包含该点则进行重心插值并比较所得三角形的面积大小,但这很快就会变得非常耗时。
我认为这已经完成了并且是那些 ›if-you-know-the-name-of-the-algorythm-you-know-what-to-implement‹-problems 之一。
我要补充一点,如果两个三角形的大小相当接近,那么它们中的任何一个都是一个很好的解决方案,所以在这种情况下,更快的解决方案会更好。
最佳答案
构建Delaunay triangulation对于给定的一组点并找到包含该点的三角形。
也许它不会是最优三角形,但算法众所周知且速度很快。
关于algorithm - 我如何从一堆点中找到包含三角形的最小点 P(x,y)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41571752/