一、规则
判断两多边形是否相交，排除边边重合、以及断点与边重合的情况
二、示意图
示意图.png
三、算法代码（js）
/**
* 判断两个多边形是否相交（边边重合，点边重合除外）
* 核心算法：1-快速排除算法 2-矢量叉乘跨立算法 3-射线算法
*
* @param polygon1
* @param polygon2
*/
function intersectsPolygonAndPolygonNew(polygon1, polygon2) {
// 两多边形是否相交标记
var _ifIntersect;
// 经纬度转换成平面坐标
var polygon1Points = pathConvert(polygon1);
var polygon2Points = pathConvert(polygon2);
// 快速排除法判断是否相交
_ifIntersect = fastExclude(polygon1Points, polygon2Points);
if (_ifIntersect == false) {
return _ifIntersect;
}
// 获取线段集合
var _polygon1Segs = getSegs(polygon1Points);
var _polygon2Segs = getSegs(polygon2Points);
// 跨立法判断相交
_ifIntersect = judgeIntersect(_polygon1Segs, _polygon2Segs);
if(_ifIntersect) {
return _ifIntersect;
}else {
// 判断是否包含
var _containPointNum = 0;
for (var i = 0; i < polygon1Points.length - 1; i++) {
var _ifContain = judgePointInPolygon(polygon1Points[i], _polygon2Segs);
if (_ifContain) {
_containPointNum++;
}
}
if (_containPointNum == polygon1Points.length - 1) {
return _ifIntersect = true;
} else {
return _ifIntersect = false;
}
}
// 获取多边形线段集合
function getSegs(points) {
var _segs = [];
for (var i = 0; i < points.length - 1; i++) {
var _element1 = points[i];
var _element2 = points[i + 1];
_segs.push({x1: _element1.x, y1: _element1.y, x2: _element2.x, y2: _element2.y});
}
return _segs;
}
}
/**
* 快速排除算法：初步判断多边形是否相交
*
* @param polygon1Points
* @param polygon2Points
*/
function fastExclude(polygon1Points, polygon2Points) {
// 多边形1最大X坐标
var _polygon1MaxX;
// 多边形1最大Y坐标
var _polygon1MaxY;
// 多边形1最小X坐标
var _polygon1MinX;
// 多边形1最小Y坐标
var _polygon1MinY;
// 多边形2最大X坐标
var _polygon2MaxX;
// 多边形2最大Y坐标
var _polygon2MaxY;
// 多边形2最小X坐标
var _polygon2MinX;
// 多边形2最小Y坐标
var _polygon2MinY;
for (var i = 0; i < polygon1Points.length; i++) {
var _polygon1Point = polygon1Points[i];
_polygon1MaxX = _polygon1MaxX > _polygon1Point.x ? _polygon1MaxX : _polygon1Point.x;
_polygon1MinX = _polygon1MinX < _polygon1Point.x ? _polygon1MinX : _polygon1Point.x;
_polygon1MaxY = _polygon1MaxY > _polygon1Point.y ? _polygon1MaxY : _polygon1Point.y;
_polygon1MinY = _polygon1MinY < _polygon1Point.y ? _polygon1MinY : _polygon1Point.y;
}
for (var i = 0; i < polygon2Points.length; i++) {
var _polygon2Point = polygon2Points[i];
_polygon2MaxX = _polygon2MaxX > _polygon2Point.x ? _polygon2MaxX : _polygon2Point.x;
_polygon2MinX = _polygon2MinX < _polygon2Point.x ? _polygon2MinX : _polygon2Point.x;
_polygon2MaxY = _polygon2MaxY > _polygon2Point.y ? _polygon2MaxY : _polygon2Point.y;
_polygon2MinY = _polygon2MinY < _polygon2Point.y ? _polygon2MinY : _polygon2Point.y;
}
if (_polygon1MaxX <= _polygon2MinX || _polygon2MaxX <= _polygon1MinX || _polygon1MinY >= _polygon2MaxY || _polygon2MinY >= _polygon1MaxY) {
return false;
} else {
return true;
}
}
/**
* 跨立算法：
* 利用矢量叉乘的物理意义判断两线段是否相交
*
* 有向量 a，b，c
* 若 (a*b)*(b*c) = 0 则两线段重合
* 若 (a*b)*(b*c) < 0 则两线段相交
* 若 (a*b)*(b*c) > 0 则两线段不相交
*
* @param polygon1Segs
* @param polygon2Segs
*/
function judgeIntersect(polygon1Segs, polygon2Segs) {
var _ifIntersect;
math.config({
number: 'BigNumber'
});
for (var i = 0; i < polygon1Segs.length; i++) {
var polygon1Seg = polygon1Segs[i];
for (var j = 0; j < polygon2Segs.length; j++) {
var polygon2Seg = polygon2Segs[j];
// 向量1
var _vector1 = new vector(math.parser().eval(polygon2Seg.x2 + "-" + polygon2Seg.x1), math.parser().eval(polygon2Seg.y2 + "-" + polygon2Seg.y1));
// 向量2
var _vector2 = new vector(math.parser().eval(polygon1Seg.x1 + "-" + polygon2Seg.x1), math.parser().eval(polygon1Seg.y1 + "-" + polygon2Seg.y1));
// 向量3
var _vector3 = new vector(math.parser().eval(polygon1Seg.x2 + "-" + polygon2Seg.x1), math.parser().eval(polygon1Seg.y2 + "-" + polygon2Seg.y1));
// 向量_vector2与_vector1叉乘的解
var _calculationVal1 = math.parser().eval(_vector2.x + "*" + _vector1.y + "-" + _vector1.x + "*" + _vector2.y);
// 向量_vector3与_vector1叉乘的解
var _calculationVal2 = math.parser().eval(_vector3.x + "*" + _vector1.y + "-" + _vector1.x + "*" + _vector3.y);
// 向量4
var _vector4 = new vector(math.parser().eval(polygon1Seg.x2 + "-" + polygon1Seg.x1), math.parser().eval(polygon1Seg.y2 + "-" + polygon1Seg.y1));
// 向量5
var _vector5 = new vector(math.parser().eval(polygon2Seg.x1 + "-" + polygon1Seg.x1), math.parser().eval(polygon2Seg.y1 + "-" + polygon1Seg.y1));
// 向量6
var _vector6 = new vector(math.parser().eval(polygon2Seg.x2 + "-" + polygon1Seg.x1), math.parser().eval(polygon2Seg.y2 + "-" + polygon1Seg.y1));
// 向量_vector5与_vector4叉乘的解
var _calculationVal3 = math.parser().eval(_vector5.x + "*" + _vector4.y + "-" + _vector4.x + "*" + _vector5.y);
// 向量_vector6与_vector4叉乘的解
var _calculationVal4 = math.parser().eval(_vector6.x + "*" + _vector4.y + "-" + _vector4.x + "*" + _vector6.y);
if (_calculationVal1 * _calculationVal2 < 0 && _calculationVal3 * _calculationVal4 < 0) {
return _ifIntersect = true;
}
}
}
return _ifIntersect = false;
// 向量对象，因为是同一平面线段，所以省略Z坐标
function vector(x, y) {
this.x = x;
this.y = y;
}
}
/**
* 射线法判断点是否在多边形内
* 点射线（向右水平）与多边形相交点的个数为奇数则认为该点在多边形内
* 点射线（向右水平）与多边形相交点的个数为偶数则认为该点不在多边形内
*
* @param point
* @param polygonSegs
*/
function judgePointInPolygon(point, polygonSegs) {
debugger
// 是否在多边形内
var _ifContain;
// 点坐标
var _X = point.x;
var _Y = point.y;
// 交点个数
var _intersecNum = 0;
// 判断射线与多边形的交点个数
for (var i = 0; i < polygonSegs.length; i++) {
var _seg = polygonSegs[i];
var _maxY = _seg.y1 < _seg.y2 ? _seg.y2 : _seg.y1;
var _minY = _seg.y1 < _seg.y2 ? _seg.y1 : _seg.y2;
if (_Y > _minY && _Y < _maxY) {
math.config({
number: 'BigNumber'
});
// 计算交点X坐标
var intersecPointX = math.parser().eval("(" + _seg.x1 + "*" + _seg.y2 + "-" + _seg.x2 + "*" + _seg.y1 + "-" + "(" + _seg.x1 + "-" + _seg.x2 + ")" + "*" + _Y + ")" + "/" + "(" + _seg.y2 + "-" + _seg.y1 + ")");
_X <= intersecPointX ? _intersecNum++ : _intersecNum + 0;
}
}
return _intersecNum % 2 == 0 ? _ifContain = false : _ifContain = true;
}
网友评论