最大三角形面积鞋带公式&海伦公式

微芒不朽

发布于 2022-09-06 20:48:24

1K0

发布于 2022-09-06 20:48:24

给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。

示例:
输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出: 2
解释: 
这五个点如下图所示。组成的橙色三角形是最大的，面积为2。

注意:

    3 <= points.length <= 50.
    不存在重复的点。
     -50 <= points[i][j] <= 50.
    结果误差值在 10^-6 以内都认为是正确答案。

思路：

1. 鞋带公式，用于计算任意多边形的面积，可用于计算三角形的面积；
1. 海伦公式，从三个顶点得到三边长，并使用海伦公司计算出面积；
3.三角形面积公式S = 1/2 * a * b * sin(C)，首先得到两边的长度，通过叉积算出夹角的正弦值，并使用公式计算出面积。

主要记录前两种实现方式。

1.鞋带公式：

比如已知 ΔABC 三个顶点的坐标 A:(x1,y1)、 B:(x2,y2)、 C:(x3,y3)，对应的矩阵是这样：

计算面积先计算中间的矩阵：

a=(x1×y2)+(x2×y3)+(x3×y1)

再从最右侧矩阵计算：

b=(y1×x2)+(y2×x3)+(y3×x1)

则三角形面积为：

SΔABC=12|a?b|=12|((x1×y2)+(x2×y3)+(x3×y1))?((y1×x2)+(y2×x3)+(y3×x1))|

抽离出来即有：

公式中约定：当下标大于 n 时， xn+1=x1, yn+1=y1。在此就不证明了。

鞋带公式-实现代码

var largestTriangleArea1 = function (points) {
  var maxs = 0;
  for (var i = 0; i < points.length; i++) {
    for (var j = i+1; j < points.length; j++) {
      for (var s = j+1; s < points.length; s++) {
        maxs = Math.max(maxs,0.5*Math.abs(
          points[i][0]*points[j][1]+
          points[j][0]*points[s][1]+
          points[s][0]*points[i][1]-
          points[i][1]*points[j][0]-
          points[j][1]*points[s][0]-
          points[s][1]*points[i][0]))
      }
    }
  }
  return maxs;
};

2.海伦公式

不同的面积公式对应不同的分割方法。

S = 1/2hb

对应的是割补矩形法，而海伦公式对应如下

海伦公式-实现代码

var largestTriangleArea = function (points) {
  var maxs = 0;
  for (var i = 0; i < points.length; i++) {
    for (var j = i+1; j < points.length; j++) {
      for (var s = j+1; s < points.length; s++) {
        console.log(points[j][0],points[i][0])
          var a = Math.sqrt(Math.pow( Math.abs(points[j][0] - points[i][0]),2)+Math.pow( Math.abs(points[j][1] - points[i][1]),2));
          var b = Math.sqrt(Math.pow( Math.abs(points[s][0] - points[j][0]),2)+Math.pow( Math.abs(points[s][1] - points[j][1]),2));
          var c = Math.sqrt(Math.pow( Math.abs(points[i][0] - points[s][0]),2)+Math.pow( Math.abs(points[i][1] - points[s][1]),2));
          var l = (a+b+c)*0.5;
          maxs = Math.max(maxs,Math.sqrt(l*(l-a)*(l-b)*(l-c)))
      }
    }
  }
  return maxs;
};

tips:该方式还存在精度问题。

参考文档：

1.海伦公式的几何意义是什么？ 2.【Green公式】Hunter’s Apprentice（判断多边形为顺时针或逆时针）--鞋带公式 3.求简单多边形面积时非常有用的“鞋带公式”

本文参与?腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-08-10，如有侵权请联系?cloudcommunity@tencent.com 删除

本文分享自叫我詹躲躲微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度