通常最好从您能想到的最简单、最容易实现的算法开始，以测试您对问题的直觉是否正确，以及您构建的内容是否符合您的需要。

在这种情况下，这是使用O(N³)算法来查看所有点的组合，并选择形成最小面积包含三角形的三个点。

在随机点集上这样做会给出如下解决方案：

如果这是您想要的，那么您可以考虑找到更快的解决方案。如果没有，您可能需要额外的约束。例如，Delaunay 三角剖分最大化三角剖分中存在的最小角度。您可以使用此处描述的方法找到包含三角形。

执行

#!/usr/bin/env python3
import matplotlib.pyplot as plt
import numpy as np

def gen_data(N: int) -> np.ndarray:
  return np.random.rand(N,2)

def sign(p1: np.ndarray, p2: np.ndarray, p3: np.ndarray) -> bool:
    return (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1])

def point_in_triangle(pt: np.ndarray, tri_pts: np.ndarray) -> bool:
    d1 = sign(pt, tri_pts[0,:], tri_pts[1,:])
    d2 = sign(pt, tri_pts[1,:], tri_pts[2,:])
    d3 = sign(pt, tri_pts[2,:], tri_pts[0,:])

    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)

    return not (has_neg and has_pos)

def heron_formula(pts: np.ndarray) -> float:
  a = np.sqrt((pts[0,0]-pts[1,0])**2 + (pts[0,1]-pts[1,1])**2)
  b = np.sqrt((pts[1,0]-pts[2,0])**2 + (pts[1,1]-pts[2,1])**2)
  c = np.sqrt((pts[2,0]-pts[0,0])**2 + (pts[2,1]-pts[0,1])**2)
  s = (a + b + c) / 2
  return np.sqrt(s*(s-a)*(s-b)*(s-c))

def smallest_triangle(pt_to_find: np.ndarray, pts: np.ndarray) -> np.ndarray:
  min_area_tri = np.inf
  tri_pts = None
  for i in range(len(pts)):
    for j in range(i+1,len(pts)):
      for k in range(j+1,len(pts)):
        if point_in_triangle(pt_to_find, pts[(i,j,k),:]):
          area = heron_formula(pts[(i,j,k),:])
          if area < min_area_tri:
            min_area_tri = area
            tri_pts = pts[(i,j,k),:].copy()
  if tri_pts is None:
    raise Exception("No containing triangle found!")
  else:
    return tri_pts

pts = gen_data(100)
pt_to_find = gen_data(1)[0,:]
smallest = smallest_triangle(pt_to_find, pts)
print("Best area", heron_formula(smallest))

# Add first point to the end for drawing purposes
smallest = np.vstack((smallest, smallest[0,:]))

plt.scatter(pts[:,0], pts[:,1])
plt.scatter(pt_to_find[0], pt_to_find[1], c="red", s=20)
plt.plot(smallest[:,0], smallest[:,1], '-')
plt.show()

我不明白反对票，社区机器人应该更聪明。

无论如何，这是一个非常快速和肮脏的方法。

• 首先，可以使用其顶点将凸包离散为三角形，因此您要寻找的实际上是最小三角形。
• 其次，一些草图让我相信最接近您的任意点的点（来自现有点集）必须是最小三角形的顶点，称为 P0 和您的任意点 PA。
• 第三，使用射线 P0-PA 及其在 PA 处的垂线将您的点划分为三个象限。P0 位于一个象限中，因此您从其余两个象限中的每个象限中为其他两个三角形顶点选择一个点（根据到 PA 的最近距离）。注意：象限这个词的使用不是很精确。

欢迎反例，其中上述方法至少不能很好地近似。