Weiler-Atherton 算法 MFC 版

在上图中，执行了经典的Weiler-Atherton演示：品红色线段显示红色多边形在蓝色多边形内的点和线段；浅蓝色线段显示蓝色多边形在红色多边形内的点和线段。

用于判断多边形内的点和线段的关键过程。

void Polygon_2D::IntersectSegmentList(Polygon_2D * pT, Polygon_2D * pRslt)
{
 //Polygon_2D * pT - target polygon
 //Polygon_2D * pRslt - result set of polygons consisted of points 
 //and segments of this polygon inside the target
 if (pT == NULL)
  return;
 Polygon_2D * pStroke = NULL;          //polygon of points and lines of pT inside this  polygon 
 BOOL bChain = FALSE;                  //flag of is current chain polygon continue
 for (POSITION pos = m_PointList.GetHeadPosition(); pos != NULL;)
 {
  Vector_2D * pti = (Vector_2D *)m_PointList.GetNext(pos);//current point
  Vector_2D * ptiN = GetNextPoint(pti, TRUE);             //next point
  if (dist2(pti, ptiN)< GeomTreshold)     //if current == next skip
   continue;
  Polygon_2D sCross;                      //polygon of intersection 
                                          //segment(pti, ptiN) with target polygon pT
  pT->IsCrossStroke(pti, ptiN, &sCross);  //if segment intersect target
  if (pT->IsPointInside(pti))             //if current point inside target
  {
   if (!bChain)                           //if chain broken
    if (sCross.m_PointList.GetCount() || pT->IsPointInside(ptiN))//if segment intersect target 
    {
     pStroke = new Polygon_2D;            //start new polygon chain
     pStroke->fillStyle = HS_TRANSPARENT;
     pStroke->penWidth = 3;
     pStroke->fgColor = pRslt->fgColor;
     pStroke->m_bClosed = FALSE;
     pRslt->m_PlaneList.AddTail(pStroke); //new polygon chain appended to result polygon
     bChain = TRUE;
    }//if(!bChain)
   if (bChain)
    pStroke->AppendNewPoint(pti);         //current point append to current polygon chain
  }//if(pT->IsPointInside(pti))
  else
   bChain = FALSE;

  while (sCross.m_PointList.GetCount())   //check all intersection points
  {
   Vector_2D * pN = (Vector_2D *)sCross.m_PointList.GetHead();
   sCross.m_PointList.RemoveHead();
   if (pN->dist(*pti) < GeomTreshold)
    continue;
   if (pStroke != NULL)
    if (pStroke->m_PointList.GetCount())
    {
     Vector_2D * pvl = (Vector_2D *)pStroke->m_PointList.GetTail();
     Vector_2D vd = (*pvl + *pN)*0.5;
     if (bChain)
      bChain = pT->IsPointInside(&vd);
    }

   if (!bChain)   //if chain broken
   {
    pStroke = new Polygon_2D;             //start new polygon chain
    pStroke->fillStyle = HS_TRANSPARENT;
    pStroke->penWidth = 3;
    pStroke->fgColor = pRslt->fgColor;
    pStroke->m_bClosed = FALSE;
    pRslt->m_PlaneList.AddTail(pStroke);  //new polygon chain appended to result polygon
    bChain = TRUE;
   }//if(!bChain)

   pStroke->AppendNewPoint(pN);           //intersection point append to current polygon chain
  }//while(sCross.m_PointList.GetCount())

  if (pT->IsPointInside(ptiN))            //if next point inside target
  {
   if (!bChain)
   {
    pStroke = new Polygon_2D;             //start new polygon chain    
    pStroke->fillStyle = HS_TRANSPARENT;
    pStroke->penWidth = 3;
    pStroke->fgColor = pRslt->fgColor;
    pStroke->m_bClosed = FALSE;

    pRslt->m_PlaneList.AddTail(pStroke);  //new polygon chain appended to result polygon
    bChain = TRUE;
   }
   pStroke->AppendNewPoint(ptiN);         //next point append to current polygon chain
  }
  else
   bChain = FALSE;
 }//for (POSITION pos = m_PointList.GetHeadPosition(); pos != NULL;)
}

在下一张图中，为了演示目的，一组链式多边形稍微错开了。

这组链式多边形的开始和结束点通过Polygon_2D::MergeChains(Polygon_2D * pPl)过程相互连接，如图所示。

结果是本篇文章标题图中所示的黄色多边形集合。

使用提供的项目开发您自己的应用程序。

您可以获取整个项目，将其重命名为我的前一篇Code Project**文章《MFC Project from Existing Code in One Click》的项目，并根据需要组合和改进代码。