【原创】【算法】三点定位简述

　

三点定位

插叙：本想着每月都写呢，但是后来最近几个月工作和家庭太忙了，真是没时间写，且写且珍惜。

一、这是个什么玩意

望文生义一看名字肯定是用三个点来定位。先不说三点定位这个，由于我之前从来没在实际项目中搞过算法（面试刷题的不算，比如各种查找算法 https://www.cnblogs.com/leezx/p/5719012.html），简单说下对算法的肤浅理解，学习一个算法我个人觉得首先要弄清楚的就是这个算法解决了一个什么问题，它的应用场景是什么，然后再深入研究算法的实现过程，最后也是最不重要的就是根据项目需要编程实现，重思考轻编程，还有就是搞算法对数学要求比较高，因为算法最后基本都是转化成各种数学公式的推导换算。（转一篇博文总结的是C语言math.h中的常用函数https://blog.csdn.net/flyapy/article/details/38494935）当下随着现在大数据和人工智能的火热，算法工程师已成为香饽饽，并都是知名公司，薪水也直奔IT界第一，其实主要就是搞的人少造成的，就像2012、2013年时候做APP开发一样，而且现在公司面试的时候也会问一些算法实现或手写，其实这个主要考察你的基本内功怎么，虽然在工作中可能用不上，但是基本工的考察还是很有必要的

先复习个简单的数学问题，求三角形的面积：

1、（底 x 高）/ 2  ——>这种方法有个麻烦的地方就是还得必须算出高才能算面积，而算高的时候又会有额外的其他计算量。

2、———>这种感觉计算量能少点

好，然后接着来，判断一个点是否在三角形内部，这个方法就很多了，每个人的想法可能都不同，大部分人可能会想到的是面积法。（图片来源：http://www.cnblogs.com/TenosDoIt/p/4024413.html）

原理就是如果一个点在三角形内，那么该点与三角形的三个点构成的三个子三角形的面积就等于大三角形的面积。如果不在三角形内的话，则大于大三角形的面积。这样的话，这个问题就转化成了求三角形面积的问题。

再来一道，这次换成圆，判断一个点是否在圆内（给定圆心坐标和半径），这个直接算该点到圆心的距离然后和半径比较。小于半径则在圆内，大于在圆外，等于则在圆上。

现在说下三点定位。三点定位就是利用三个点的坐标位置信息来计算出当前的位置信息，即已知三点位置坐标(x0, y0), (x1, y1), (x2, y2)和所求位置点 (x, y)分别到三点的距离 d0，d1, d2。然后以 d0，d1, d2为半径作三个圆，依据毕达哥拉斯定理，得出未知点的位置计算公式，那定位的问题就转化成了求圆交点坐标的问题：

公式为：解方程式略，最后肯定能求出来位置点的坐标x和y的值（这篇文章是通过切线斜率切点这种方式解的https://blog.csdn.net/u013090676/article/details/73865137）

二、有毛用啊

很显然是用来定位的啊，上述说的都是些理论，在实际中应用场景中肯定不能这样，在实际应用中比较常见的基于RSSI的三点定位实现。

三、怎么用啊

下面主要介绍下基于RSSI的三点定位实现。

比如一种场景是用beacon限定好一个固定区域，然后计算设备在这个区域内的位置坐标。如下图所示：

该矩形区域由4个信标组成，并且信标的位置坐标是已知的，然后在该区域内的设备基于BLE可以获取到信标的坐标信息和RSSI值，根据RSSI值可以推导出距离各个信标的距离值，这样就转化成上面介绍的求交点坐标的问题了。当然在理想情况下是交于一点的，如下图:

上述情况是理想情况，在现实测试中几乎不存在。大部分情况是根据RSSI值算出的距离值画出的圆之间没有交点或多个交点，如下图：

等等各种复杂相交的情况，这样的话就涉及到“准不准”和“哪个准”的问题了，具体就又涉及到机制和策略来使其“准”。其实不管哪种情况决定最终的定位结果的值就是圆的半径，而圆的半径该值是通过RSSI换算得到的。这里涉及到两个关乎准不准的问题，一个是RSSI值准不准，可以采取一定的策略，比如多测几次求均值等等。另一个是RSSI值转换到半径后的准确度，不过该部分转换大多都采用RSSI测距公式。

接着在上面通过一系列策略或机制获取到相对“准”的三个半径值后（三点定位只需三个即可），然后各自画圆求出所有的交点（求两圆之间的交点的方法可以参考https://blog.csdn.net/zx3517288/article/details/53326420），如果两个圆没有交点的话，可以采用一定的策略来选出一个点。

接下来将得到的所有交点也是按照一定的算法（比如最小二乘法等https://www.cnblogs.com/wangkundentisy/p/7505487.html）选出N个点，然后再在这个N个点组成的区域（3个点的话就是三角形区域，4个点的话就是四边形区域）内也依据一定的算法计算出最终的定位点坐标。

代码暂不无偿公开，如有需要请留言联系方式

四、成为大神的用法

由于不是做算法方向，该部分欢迎各位大拿留言补充，在此跪谢。

转载请标明出处和链接

相关阅读

百度最新推出的“蓝天算法”内容是什么？

蓝天算法继百度绿萝算法、百度石榴算法、百度星火计划、百度天网算法、百度冰桶算法，百度最新推出了一个“蓝天算法”，听

粒子群优化算法(PSO)

  %% 最近写的粒子群的论文，再重新巩固一下 推荐一个优化算法代码网址：http://www.Hvass-Labs.org/ 1   研究背景 粒子群算法

【全源最短路问题】 --Floyd算法

Floyd算法的时间复杂度为O(n3)O(n^3)O(n3)。因此n的大小不超过200。 题目来源：codeup链接在本题中，读入一个有向图的带权邻接矩阵（

轮询调度算法(Round-Robin Scheduling)

http://blog.163.com/s_u/blog/static/1330836720105233102894/ 毫无疑问，随着互联网、移动网络接入成本的降低，互联网正在日益深入

CornerNet 算法笔记

论文：CornerNet: Detecting Objects as Paired Keypoints论文链接：https://arxiv.org/abs/1808.01244代码链接：https://github.com/u