点在多边形内是几何,图形学,游戏领域经常用到的算法,算法的描述网上有很多,就是经过这点和多边形内一点连线,然后根据线与多边形的交点数目来判断,多的就不说了,直接来个源代码,大家用着方便
bool IsPtInArea(AcGePoint3d pt, AcGePoint3dArray& pt3dArr)
{
int iLen = pt3dArr.length();
if (iLen < 3)
return false;
// 首先构造最小包络面并得到最大 x 坐标
int i;
double dblMaxX = pt3dArr[0].x;
double dblMinX = pt3dArr[0].x;
double dblMaxY = pt3dArr[0].y;
double dblMinY = pt3dArr[0].y;
for (i = 1; i < iLen; i++)
{
if (pt3dArr[i].x > dblMaxX)
dblMaxX = pt3dArr[i].x;
if (pt3dArr[i].x < dblMinX)
dblMinX = pt3dArr[i].x;
if (pt3dArr[i].y > dblMaxY)
dblMaxY = pt3dArr[i].y;
if (pt3dArr[i].y < dblMinY)
dblMinY = pt3dArr[i].y;
}
// 如果点位于最小包络面之外，则肯定不在区域内，直接返回 false
if (( pt.x > dblMaxX) ||
( pt.x < dblMinX) ||
( pt.y > dblMaxY) ||
( pt.y < dblMinY)
)
return false;
pt.z = 0.0;
AcGePoint3d xpt, ipt;
xpt = pt;
xpt.x = dblMaxX + 10.0;
//xpt.x = 1.7e208;
AcGeLineSeg3d lineseg3d(pt, xpt);
AcGePoint3d p1 = pt3dArr.first();
bool bAdd = false;
if (!pt3dArr[iLen - 1].isEqualTo(p1)){
pt3dArr.append(p1);
iLen++;
bAdd = true;
}
for (i=1; i < iLen; i++)
{
p2 = pt3dArr[i];
p2.z = 0.0;
// 如果所给点与顶点相等，直接返回
if (pt.isEqualTo(p1))
{
if (bAdd)
pt3dArr.removeLast();
return true;
}
AcGeLineSeg3d xlineseg3d(p1, p2);
// 如果所给点在某一条边上，直接返回
if (xlineseg3d.isOn(pt) == Adesk::kTrue)
{
if (bAdd)
pt3dArr.removeLast();
return true;
}
// 如果构造线段与交点存在，加入交点表
if (lineseg3d.intersectWith(xlineseg3d, ipt) == Adesk::kTrue)
{
//bool bAdd = true;
// 如果交点正好为顶点，判断另外的端点在哪一侧
if (ipt.isEqualTo(p1))
{
if (p2.y > ipt.y)
nCount++;
}
else if(ipt.isEqualTo(p2))
{
if (p1.y > ipt.y)
nCount++;
}
else
nCount++;
}
p1 = p2;
}
pt3dArr.removeLast();
if ((nCount % 2) == 0)
return false; // 交点数为偶数，不在区域内
else
return true; // 交点数为奇数，在区域内
}
{
int iLen = pt3dArr.length();
if (iLen < 3)
return false;
// 首先构造最小包络面并得到最大 x 坐标
int i;
double dblMaxX = pt3dArr[0].x;
double dblMinX = pt3dArr[0].x;
double dblMaxY = pt3dArr[0].y;
double dblMinY = pt3dArr[0].y;
for (i = 1; i < iLen; i++)
{
if (pt3dArr[i].x > dblMaxX)
dblMaxX = pt3dArr[i].x;
if (pt3dArr[i].x < dblMinX)
dblMinX = pt3dArr[i].x;
if (pt3dArr[i].y > dblMaxY)
dblMaxY = pt3dArr[i].y;
if (pt3dArr[i].y < dblMinY)
dblMinY = pt3dArr[i].y;
}
// 如果点位于最小包络面之外，则肯定不在区域内，直接返回 false
if (( pt.x > dblMaxX) ||
( pt.x < dblMinX) ||
( pt.y > dblMaxY) ||
( pt.y < dblMinY)
)
return false;
// 循环求取交点
pt.z = 0.0;
AcGePoint3d xpt, ipt;
xpt = pt;
xpt.x = dblMaxX + 10.0;
//xpt.x = 1.7e208;
AcGeLineSeg3d lineseg3d(pt, xpt);
AcGePoint3d p1 = pt3dArr.first();
p1.z
= 0.0;bool bAdd = false;
if (!pt3dArr[iLen - 1].isEqualTo(p1)){
pt3dArr.append(p1);
iLen++;
bAdd = true;
}
AcGePoint3d p2;
for (i=1; i < iLen; i++)
{
p2 = pt3dArr[i];
p2.z = 0.0;
// 如果所给点与顶点相等，直接返回
if (pt.isEqualTo(p1))
{
if (bAdd)
pt3dArr.removeLast();
return true;
}
AcGeLineSeg3d xlineseg3d(p1, p2);
// 如果所给点在某一条边上，直接返回
if (xlineseg3d.isOn(pt) == Adesk::kTrue)
{
if (bAdd)
pt3dArr.removeLast();
return true;
}
// 如果构造线段与交点存在，加入交点表
if (lineseg3d.intersectWith(xlineseg3d, ipt) == Adesk::kTrue)
{
//bool bAdd = true;
// 如果交点正好为顶点，判断另外的端点在哪一侧
if (ipt.isEqualTo(p1))
{
if (p2.y > ipt.y)
nCount++;
}
else if(ipt.isEqualTo(p2))
{
if (p1.y > ipt.y)
nCount++;
}
else
nCount++;
}
p1 = p2;
}
if (bAdd)
pt3dArr.removeLast();
if ((nCount % 2) == 0)
return false; // 交点数为偶数，不在区域内
else
return true; // 交点数为奇数，在区域内
}