原创 有关路径搜索的一个算法

//查找某点的所有邻接点
void CFindRateWay::FindPtNear(AcGePoint3d pt,AcGePoint3dArray& PtAry)
{
 std::list<AcGeLineSeg3d>::iterator iter;
 for (iter=m_lstRate.begin(); iter!=m_lstRate.end(); iter++)
 {
  AcGeLineSeg3d line = *iter;
  if (line.isOn(pt) == Adesk::kTrue)
  {
   AcGePoint3d ptStart = line.startPoint();
   AcGePoint3d ptEnd = line.endPoint();
   int iFind = -1;
   if (!PtAry.find(ptStart,iFind) && !pt.isEqualTo(ptStart))
    PtAry.append(ptStart);
   if (!PtAry.find(ptEnd,iFind) && !pt.isEqualTo(ptEnd))
    PtAry.append(ptEnd);
  }
 }
}

//从栈中寻找指定点，找到返回TRUE
BOOL CFindRateWay::FindPtFromStack(AcGePoint3d pt, IN std::stack<AcGePoint3d>& staPt)
{
 std::stack<AcGePoint3d> staPt2; //用来临时存放栈元素
 BOOL bFind = FALSE;
 while (!staPt.empty())
 {
  AcGePoint3d ptItem = staPt.top();
  if (ptItem.isEqualTo(pt))
  {
   bFind = TRUE;
   break;
  }
  staPt2.push(ptItem);
  staPt.pop();
 }
 //将staPt2中元素依次压回
 while (!staPt2.empty())
 {
  staPt.push(staPt2.top());
  staPt2.pop();
 }

 return bFind;
}

---------------------------------

调用方式：

// This is command 'DEMOCMD'
//命令用来构建道路各段，
void ARXDemoDemoCmd()
{
 // TODO: Implement the command
 std::list<AcGeLineSeg3d> lstRate;
 AcGeLineSeg3d line1(AcGePoint3d(300,0,0),AcGePoint3d(300,100,0));
 lstRate.push_back(line1);
 
 AcGeLineSeg3d line2(AcGePoint3d(100,100,0),AcGePoint3d(100,500,0));
 lstRate.push_back(line2);
 
 AcGeLineSeg3d line3(AcGePoint3d(100,100,0),AcGePoint3d(300,100,0));
 lstRate.push_back(line3);
 
 AcGeLineSeg3d line4(AcGePoint3d(0,500,0),AcGePoint3d(100,500,0));
 lstRate.push_back(line4);
 
 AcGeLineSeg3d line5(AcGePoint3d(100,500,0),AcGePoint3d(200,500,0));
 lstRate.push_back(line5);
 
 AcGeLineSeg3d line6(AcGePoint3d(200,400,0),AcGePoint3d(200,500,0));
 lstRate.push_back(line6);
 
 AcGeLineSeg3d line7(AcGePoint3d(200,500,0),AcGePoint3d(400,500,0));
 lstRate.push_back(line7);
 
 AcGeLineSeg3d line8(AcGePoint3d(200,400,0),AcGePoint3d(400,400,0));
 lstRate.push_back(line8);
 
 AcGeLineSeg3d line9(AcGePoint3d(200,300,0),AcGePoint3d(200,400,0));
 lstRate.push_back(line9);
 
 AcGeLineSeg3d line10(AcGePoint3d(200,200,0),AcGePoint3d(200,300,0));
 lstRate.push_back(line10);
 
 AcGeLineSeg3d line11(AcGePoint3d(200,300,0),AcGePoint3d(400,300,0));
 lstRate.push_back(line11);
 
 AcGeLineSeg3d line12(AcGePoint3d(200,200,0),AcGePoint3d(400,200,0));
 lstRate.push_back(line12);
 
 AcGeLineSeg3d line13(AcGePoint3d(400,200,0),AcGePoint3d(400,300,0));
 lstRate.push_back(line13);
 
 AcGeLineSeg3d line14(AcGePoint3d(400,300,0),AcGePoint3d(400,400,0));
 lstRate.push_back(line14);
 
 AcGeLineSeg3d line15(AcGePoint3d(400,400,0),AcGePoint3d(400,500,0));
 lstRate.push_back(line15);

 AcGeLineSeg3d line16(AcGePoint3d(400,500,0),AcGePoint3d(600,500,0));
 lstRate.push_back(line16);

 AcGeLineSeg3d line17(AcGePoint3d(400,400,0),AcGePoint3d(600,400,0));
 lstRate.push_back(line17);

 AcGeLineSeg3d line18(AcGePoint3d(400,300,0),AcGePoint3d(600,300,0));
 lstRate.push_back(line18);

 AcGeLineSeg3d line19(AcGePoint3d(400,200,0),AcGePoint3d(600,200,0));
 lstRate.push_back(line19);

 AcGeLineSeg3d line20(AcGePoint3d(600,400,0),AcGePoint3d(600,500,0));
 lstRate.push_back(line20);

 AcGeLineSeg3d line21(AcGePoint3d(600,300,0),AcGePoint3d(600,400,0));
 lstRate.push_back(line21);

 AcGeLineSeg3d line22(AcGePoint3d(600,200,0),AcGePoint3d(600,300,0));
 lstRate.push_back(line22);

 AcGeLineSeg3d line23(AcGePoint3d(600,100,0),AcGePoint3d(600,200,0));
 lstRate.push_back(line23);

 AcGeLineSeg3d line24(AcGePoint3d(600,100,0),AcGePoint3d(700,100,0));
 lstRate.push_back(line24);

 AcGeLineSeg3d line25(AcGePoint3d(600,500,0),AcGePoint3d(700,500,0));
 lstRate.push_back(line25);

 AcGeLineSeg3d line26(AcGePoint3d(300,100,0),AcGePoint3d(500,100,0));
 lstRate.push_back(line26);

 AddAllRacePt();

 //按lst创建实体
 g_ObjIdAry.setLogicalLength(0);
 CreateLineEnt(g_ObjIdAry, lstRate);
 
 //调用搜索类查找所有路径
 CDlgSetRacePos dlg;
 if (dlg.DoModal() == IDOK)
 {
  AcGePoint3d ptStart = g_pt[dlg.m_iStartPtIndex];
  AcGePoint3d ptEnd = g_pt[dlg.m_iEndPtIndex];
  CFindRateWay clsFindRate(lstRate,ptStart, ptEnd);
  g_vecRateWay.clear();
  clsFindRate.FindWay(g_vecRateWay); 
  acutPrintf(_T("\n总共%d条路"), g_vecRateWay.size());

  ShowRace();
 }
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/lhscad/archive/2010/02/20/5313536.aspx