今天看到一个比较有意思的文章,如何实现多边形搜索,其实就是判断坐标系上一个点是否在多边形内。多边形搜索的用处还是很广泛的,比如搜索某个区域的酒店、饭馆。这又是一个数学问题,可以简单的用图论来表示:判断一个点A是否在多边形p中,先取一条经过A且与x轴平行的直线,然后计算直线与p的所有交点。
1)当A左边的交点数量为奇数,右边的交点数量也是奇数,A在多边形p中。
2)当A左边的交点数量为偶数,右边的交点数量也是偶数,A在多边形p外。
不过我发现这个判断方法没有考虑直线正好经过多边形某个顶点的情况,所以在算法中需要判断p的所有顶点不在直线上。
算法实现如下:
function pointInPolygon(points,lat,lon)
{
var i;
var j=points.length-1;
var inPoly=false;
{
var i;
var j=points.length-1;
var inPoly=false;
for (i=0; i<points.length; i++)
{
if (points[i].Longitude<lon && points[j].Longitude>=lon
|| points[j].Longitude<lon && points[i].Longitude>=lon)
{
if (points[i].Latitude+(lon-points[i].Longitude)/
(points[j].Longitude-points[i].Longitude)*(points[j].Latitude
-points[i].Latitude)<lat)
{
inPoly=!inPoly;
}
}
j=i;
}
return inPoly;
}