BIM论坛 › 开放图形库 › 判段点是否在多边形内

萧闫子 发表于 2014-1-9 14:27:29

判段点是否在多边形内

点在多边形内是几何,图形学,游戏领域经常用到的算法,算法的描述网上有很多,就是经过这点和多边形内一点连线,然后根据线与多边形的交点数目来判断,多的就不说了,直接来个源代码,大家用着方便

bool   IsPtInArea(AcGePoint3d pt, AcGePoint3dArray& pt3dArr)
{
    int iLen = pt3dArr.length();
    if (iLen < 3)
      return false;
    // 首先构造最小包络面并得到最大 x 坐标
    int i;
    double dblMaxX = pt3dArr.x;
    double dblMinX = pt3dArr.x;
    double dblMaxY = pt3dArr.y;
    double dblMinY = pt3dArr.y;
    for (i = 1; i < iLen; i++)
    {
      if (pt3dArr.x > dblMaxX)
            dblMaxX = pt3dArr.x;
      if (pt3dArr.x < dblMinX)
            dblMinX = pt3dArr.x;
      if (pt3dArr.y > dblMaxY)
            dblMaxY = pt3dArr.y;
      if (pt3dArr.y < dblMinY)
            dblMinY = pt3dArr.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.isEqualTo(p1)){
      pt3dArr.append(p1);
      iLen++;
      bAdd = true;
    }

    AcGePoint3d p2;
    int nCount = 0;
    for (i=1; i < iLen; i++)
    {
      p2 = pt3dArr;
      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; // 交点数为奇数，在区域内
}

EaBIM门户编辑 发表于 2017-6-1 10:16:16

好东西大家共享，一起进步，

宇航员 发表于 2014-6-12 09:47:57

路过！！！
不发表意见……

等你回来 发表于 2014-2-27 14:56:16

路过！！！
帮顶……

莞人莞事 发表于 2014-3-5 16:50:14

顶！！！！！！！！！！！！！！！！！！！！！！！！！

言子 发表于 2014-3-13 14:59:33

好强大啊，谢谢哈

秦惑 发表于 2014-3-26 16:09:27

路过！！！
不发表意见……

順順 发表于 2014-3-26 16:11:32

顶起来…………

野风 发表于 2014-3-26 16:15:15

顶!!!!!!!!!!

泰安oim 发表于 2014-3-26 16:15:25

顶！！！！！！！！！！！！！！！！！！！！！！！！！

入樽 发表于 2014-4-1 10:45:50

顶!!!!!!!!!!

国产008 发表于 2014-4-1 10:55:35

顶起来…………

MIMDxFzL 发表于 2014-4-1 10:58:32

顶起来…………

xy666 发表于 2014-4-11 11:26:37

顶......
楼下跟上.....

chen_0003 发表于 2014-4-11 11:30:39

顶！！！！！！！！！！！！！！！！！！！！！！！！！

苦田辛君 发表于 2014-4-11 11:37:35

顶起来…………

烈火ivk 发表于 2014-4-23 11:25:35

路过！！！
帮顶……

查看完整版本: 判段点是否在多边形内