一、規(guī)則
判斷兩多邊形是否相交顷级，排除邊邊重合凫乖、以及斷點(diǎn)與邊重合的情況
二、示意圖
示意圖.png
三弓颈、算法代碼（js）
/**
* 判斷兩個多邊形是否相交（邊邊重合帽芽，點(diǎn)邊重合除外）
* 核心算法：1-快速排除算法 2-矢量叉乘跨立算法 3-射線算法
*
* @param polygon1
* @param polygon2
*/
function intersectsPolygonAndPolygonNew(polygon1, polygon2) {
// 兩多邊形是否相交標(biāo)記
var _ifIntersect;
// 經(jīng)緯度轉(zhuǎn)換成平面坐標(biāo)
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坐標(biāo)
var _polygon1MaxX;
// 多邊形1最大Y坐標(biāo)
var _polygon1MaxY;
// 多邊形1最小X坐標(biāo)
var _polygon1MinX;
// 多邊形1最小Y坐標(biāo)
var _polygon1MinY;
// 多邊形2最大X坐標(biāo)
var _polygon2MaxX;
// 多邊形2最大Y坐標(biāo)
var _polygon2MaxY;
// 多邊形2最小X坐標(biāo)
var _polygon2MinX;
// 多邊形2最小Y坐標(biāo)
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;
// 向量對象导街，因?yàn)槭峭黄矫婢€段，所以省略Z坐標(biāo)
function vector(x, y) {
this.x = x;
this.y = y;
}
}
/**
* 射線法判斷點(diǎn)是否在多邊形內(nèi)
* 點(diǎn)射線（向右水平）與多邊形相交點(diǎn)的個數(shù)為奇數(shù)則認(rèn)為該點(diǎn)在多邊形內(nèi)
* 點(diǎn)射線（向右水平）與多邊形相交點(diǎn)的個數(shù)為偶數(shù)則認(rèn)為該點(diǎn)不在多邊形內(nèi)
*
* @param point
* @param polygonSegs
*/
function judgePointInPolygon(point, polygonSegs) {
debugger
// 是否在多邊形內(nèi)
var _ifContain;
// 點(diǎn)坐標(biāo)
var _X = point.x;
var _Y = point.y;
// 交點(diǎn)個數(shù)
var _intersecNum = 0;
// 判斷射線與多邊形的交點(diǎn)個數(shù)
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'
});
// 計(jì)算交點(diǎn)X坐標(biāo)
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;
}
