c++ - 四边形的面积

Question

我在一个平面上有 n 个点和一个目标区域 P。我试图找到面积最接近 P 的四边形角点的四个点。以下是 n=5 且 P=30 的示例:

• 0, 0
• 10, 0
• 0, 10
• 10, 10
• 7, 3

答案应该是 30.0(最接近 P，在本例中它是相等的)。

你知道我该怎么做吗？我知道我可以使用 Heron 公式计算每个四边形的面积，但我是否必须尝试所有组合或者是否有更短的方法？

Answer 1

你可以

1. 采用具有所需顶点数和形状的单元/模板多边形。

2. 给它加一个乘法比例因子t，这样它的坐标看起来像

   0, 0
   10t, 0
   0, 10t
   10t, 10t
   7t, 3t
   

3. 使用 shoelace formula计算面积，说f(t)。

4. 针对比例因子 t 和多边形的相关坐标求解多项式方程 f(t) = 30.0。

这应该会为您提供所需区域的多边形 (30.0)。

顺便说一下，我假设您知道多边形的形状，否则，有(无限)多种解决方案可以适合您的目标区域。