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

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

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

示例:
输入: 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.求简单多边形面积时非常有用的“鞋带公式”

相关文章
|
消息中间件 存储 Kubernetes
k8s1.20版本部署RabbitMQ集群(持久化)——2023.05
k8s1.20版本部署RabbitMQ集群(持久化)——2023.05
1354 1
IDEA报错:Lombok Requires Annotation Processing
IDEA报错:Lombok Requires Annotation Processing
1409 0
IDEA报错:Lombok Requires Annotation Processing
|
4月前
|
数据采集 存储 NoSQL
基于Scrapy-Redis的分布式景点数据爬取与热力图生成
基于Scrapy-Redis的分布式景点数据爬取与热力图生成
300 67
|
7月前
|
缓存 网络协议 Linux
PCIe 以太网芯片 RTL8125B 的 spec 和 Linux driver 分析备忘
本文详细介绍了 Realtek RTL8125B PCIe 以太网芯片的规格以及在 Linux 中的驱动安装和配置方法。通过深入分析驱动源码,可以更好地理解其工作原理和优化方法。在实际应用中,合理配置和优化驱动程序可以显著提升网络性能和稳定性。希望本文能帮助您更好地使用和管理 RTL8125B,以满足各种网络应用需求。
669 33
|
12月前
|
监控 安全 项目管理
『软件工程3』你应该知道的三种原型实现模型:抛弃式、演化式、增量式
该文章详细解释了三种原型实现模型——抛弃式、演化式、增量式模型的特点、流程、优缺点及适用场景。
『软件工程3』你应该知道的三种原型实现模型:抛弃式、演化式、增量式
|
存储 自然语言处理 关系型数据库
|
存储 缓存 Android开发
Android系统分区与升级
Android系统分区与升级
324 4
|
JavaScript 前端开发
qml 信号和处理程序事件系统(Signal and Handler Event System)
qml 信号和处理程序事件系统(Signal and Handler Event System)
227 0
|
网络安全 开发工具 Docker
为Docker下的qBittorrent配置更合理的权限,在环境中配置对应独立的UID和GID
为Docker下的qBittorrent配置更合理的权限,在环境中配置对应独立的UID和GID
1459 0
|
运维 自然语言处理 监控
微服务系列 1:服务化框架落地的挑战和核心需求
如果公司没有一套规范化的流程和服务化框架,那么公司内部的各个业务团队、部门之间的技术体系就会越走越远,从而会给公司的服务端系统的稳定性和可运维性带来很大的挑战,所以就需要一个统一的微服务架构的实践统一解决当前的架构问题,防止架构腐化,从而提升我们后端系统的稳定性。这也是大多数互联网公司微服务化的意义所在。