判断一个点是否在某个区域内(多边形)
背景：
比如滴滴会根据乘客所在的不同区域，给出不同的价格。市区堵一点，那么价格也高点。获取服务范围只规定在某个范围内
原理：
求解从该点向右发出的水平线射线与多边形各边的交点，当交点数为奇数，则在内部。
不过要注意几种特殊情况：1、点在边或者顶点上;2、点在边的延长线上;3、点出发的水平射线与多边形相交在顶点上
源代码：
Point类-多边形顶点的封装类如坐标(166.3,18.4)
Line类-多边形对应的各个边的封装类，如{(166.3,18.4), (166.9,19)}
MapUtil类-地图公共处理类
point.h
//point.h
#include "Data_Pools/Data_Pools.h"
class Point
{
public:
//水平方向值/经度
double X;
//垂直方向值/纬度
double Y;
Point():X(0),Y(0) {}
Point(double x, double y) {
this->X = x;
this->Y = y;
}
// bool equals(Point *obj) {
// // 如果为同一对象的不同引用,则相同
// if (this == obj) {
// return true;
// }
// // 如果传入的对象为空,则返回false
// if (obj == nullptr) {
// return false;
// }
// Point point = *obj;
// if ( double_Equal(point.X,this->X) && double_Equal(point.Y,this->Y) ) {
// return true;
// }
// else {
// return false;
// }
// }
bool double_Equal(double num1, double num2)
{
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
return true;
else
return false;
}
};
line.h
/*line.h*/
#include "point.h"
class Line
{
public:
//端点1
Point POINTA;
//端点2
Point POINTB;
Line(Point &pointA, Point &pointB):POINTA(pointA),POINTB(pointB) {
}
/**
* 判断当前线段是否包含给定的点</br>
* 即给定的点是否在当前边上
* @param point
* @return
*/
bool isContainsPoint(Point point);
//叉积
double mult(Point a, Point b, Point c);
/**
* 给定线段是否与当前线段相交</br>
* 相交返回true, 不相交返回false
* @param line
* @return
*/
bool isIntersect(Line line);
bool double_Equal(double num1, double num2)
{
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
return true;
else
return false;
}
private:
/**
* 提供精确的加法运算。 未完成版
* @param v1 被加数
* @param v2 加数
* @return 两个参数的和
*/
static double add(double v1, double v2) {
return v1+v2;
}
/**
* 提供精确的减法运算。 未完成版
* @param v1 被减数
* @param v2 减数
* @return 两个参数的差
*/
static double sub(double v1, double v2) {
return v1-v2;
}
/**
* 提供精确的乘法运算。 未完成版
* @param v1 被乘数
* @param v2 乘数
* @return 两个参数的积
*/
static double mul(double v1, double v2) {
return v1*v2;
}
/**
* 提供（相对）精确的除法运算，当发生除不尽的情况时，精确到
* 小数点以后10位，以后的数字四舍五入。 未完成版
* @param v1 被除数
* @param v2 除数
* @return 两个参数的商
*/
static double div(double v1, double v2) {
return v1 / v2;
}
};line.cpp
//line.cpp
#include "line.h"
#include <algorithm>
using namespace std;
bool Line::isContainsPoint(Point point)
{
bool result = false;
//判断给定点point与端点1构成线段的斜率是否和当前线段的斜率相同
//给定点point与端点1构成线段的斜率k1
double k1 = 0;
bool needjudgment = true;
if (double_Equal(point.X,this->POINTA.X)) {
//k1 = -DBL_MAX;
needjudgment = false;
}
else {
k1 = div(sub(point.Y, this->POINTA.Y), sub(point.X, this->POINTA.X));
}
//当前线段的斜率k2
double k2 = 0;
if ( double_Equal(this->POINTB.X,this->POINTA.X) ) {
//k2 = -DBL_MAX;
needjudgment = false;
}
else {
k2 = div(sub(this->POINTB.Y, this->POINTA.Y), sub(this->POINTB.X, this->POINTA.X));
}
if (needjudgment == true) {
if (double_Equal(k1,k2)) {
//若斜率相同，继续判断给定点point的x是否在pointA.x和pointB.x之间,若在 则说明该点在当前边上
if (sub(point.X, this->POINTA.X) * sub(point.X, this->POINTB.X) < 0) {
result = true;
}
}
}
return result;
}
double Line::mult(Point a, Point b, Point c)
{
return (a.X - c.X)*(b.Y - c.Y) - (b.X - c.X)*(a.Y - c.Y);
}
bool Line::isIntersect(Line line)
{
Point aa = this->POINTA;
Point bb = this->POINTB;
Point cc = line.POINTA;
Point dd = line.POINTB;
if (max(aa.X, bb.X) < min(cc.X, dd.X)) {
return false;
}
if (max(aa.Y, bb.Y) < min(cc.Y, dd.Y)) {
return false;
}
if (max(cc.X, dd.X) < min(aa.X, bb.X)) {
return false;
}
if (max(cc.Y, dd.Y) < min(aa.Y, bb.Y)) {
return false;
}
if (mult(cc, bb, aa) * mult(bb, dd, aa) < 0) {
return false;
}
if (mult(aa, dd, cc) * mult(dd, bb, cc) < 0) {
return false;
}
return true;
}
maputil.h
#include "line.h"
#include "point.h"
#include <QVector>
class MapUtil
{
public:
//多边形的各个点要是依次连接的输入的
static bool isPointInPolygon(Point point, QVector<Point> &points) {
bool result = false;
int intersectCount = 0;
// 判断依据：求解从该点向右发出的水平线射线与多边形各边的交点，当交点数为奇数，则在内部
//不过要注意几种特殊情况：1、点在边或者顶点上;2、点在边的延长线上;3、点出发的水平射线与多边形相交在顶点上
/**
* 具体步骤如下：
* 循环遍历各个线段：
* 1、判断点是否在当前边上(斜率相同,且该点的x值在两个端口的x值之间),若是则返回true
* 2、否则判断由该点发出的水平射线是否与当前边相交,若不相交则continue
* 3、若相交,则判断是否相交在顶点上(边的端点是否在给定点的水平右侧).若不在,则认为此次相交为穿越,交点数+1 并continue
* 4、若交在顶点上,则判断上一条边的另外一个端点与当前边的另外一个端点是否分布在水平射线的两侧.若是则认为此次相交为穿越,交点数+1.
*/
for (int i = 0; i < points.size(); i++) {
Point pointA = points.at(i);
Point pointB;
Point pointPre;
//若当前是第一个点,则上一点则是list里面的最后一个点
if (i == 0) {
pointPre = points.at(points.size() - 1);
}
else {
pointPre = points.at(i - 1);
}
//若已经循环到最后一个点,则与之连接的是第一个点
if (i == (points.size() - 1)) {
pointB = points.at(0);
}
else {
pointB = points.at(i + 1);
}
Line line = Line(pointA, pointB);
//1、判断点是否在当前边上(斜率相同,且该点的x值在两个端口的x值之间),若是则返回true
bool isAtLine = line.isContainsPoint(point);
if (isAtLine) {
return true;
}
else {
//2、若不在边上,判断由该点发出的水平射线是否与当前边相交,若不相交则continue
//设置该射线的另外一个端点的x值=999,保证边的x永远不超过
Point radialPoint = Point(180 , point.Y);
Line radial = Line(point, radialPoint);
//给定线段是否与当前线段相交 相交返回true
bool isIntersect = radial.isIntersect(line);
if (!isIntersect) {
continue;
}
else {
//3、若相交,则判断是否相交在顶点上(边的端点是否在给定点的水平右侧).若不在,则认为此次相交为穿越,交点数+1 并continue
if (!( (pointA.X > point.X) && (double_Equal(pointA.Y,point.Y))
|| (pointB.X > point.X) && (double_Equal(pointB.Y,point.Y)) )) {
intersectCount++;
continue;
}
else {
//4、若交在顶点上,则判断上一条边的另外一个端点与当前边的另外一个端点是否分布在水平射线的两侧.若是则认为此次相交为穿越,交点数+1
if ((pointPre.Y - point.Y) * (pointB.Y - point.Y) < 0) {
intersectCount++;
}
}
}
}
}
result = intersectCount % 2 == 1;
return result;
}
static bool double_Equal(double num1, double num2)
{
if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001))
return true;
else
return false;
}
};