shortestpathview.cpp

该算法实现了任意两点间的最短路径选取

// ShortestPathView.cpp : implementation of the CShortestPathView class
//

#include "stdafx.h"
#include "ShortestPath.h"

#include "ShortestPathDoc.h"
#include "ShortestPathView.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CShortestPathView

void PathCopy(CArray<int,int>& source,CArray<int,int>& dest) //
{
	dest.RemoveAll();
	for(int i=0;i<source.GetSize();i++)
		dest.Add(source[i]);
}



IMPLEMENT_DYNCREATE(CShortestPathView, CFormView)

BEGIN_MESSAGE_MAP(CShortestPathView, CFormView)
	//{{AFX_MSG_MAP(CShortestPathView)
	ON_WM_SIZE()
	ON_COMMAND_RANGE(ID_MAP_SELECT, ID_MAP_PAN, OnMapTool)
	ON_UPDATE_COMMAND_UI_RANGE(ID_MAP_SELECT, ID_MAP_PAN, OnUpdateMapTool)
	ON_COMMAND(ID_MAP_FULLEXTENT, OnMapFullextent)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CFormView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CShortestPathView construction/destruction

CShortestPathView::CShortestPathView()
	: CFormView(CShortestPathView::IDD)
{
	//{{AFX_DATA_INIT(CShortestPathView)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// TODO: add construction code here
	 m_curTool=ID_MAP_SELECT;
}

CShortestPathView::~CShortestPathView()
{
}

void CShortestPathView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CShortestPathView)
	DDX_Control(pDX, IDC_MAP1, m_map);
	//}}AFX_DATA_MAP
}

BOOL CShortestPathView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CFormView::PreCreateWindow(cs);
}

void CShortestPathView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();

	CMoDataConnection conn;
	conn.CreateDispatch(TEXT("MapObjects2.DataConnection"));
	conn.SetDatabase(".\\Data");
	if(!conn.Connect()) 
		throw new CFileException(CFileException::fileNotFound);

	CMoLayers layers(m_map.GetLayers());
	CMoMapLayer arcLayer;
	arcLayer.CreateDispatch(TEXT("MapObjects2.MapLayer"));
	CMoGeoDataset arcGeoDataset(conn.FindGeoDataset("shortpatharc"));
	arcLayer.SetGeoDataset(arcGeoDataset);
	layers.Add(arcLayer);

	CMoMapLayer nodeLayer;
	nodeLayer.CreateDispatch(TEXT("MapObjects2.MapLayer"));
	CMoGeoDataset nodeGeoDataset(conn.FindGeoDataset("shortpathnod"));
	nodeLayer.SetGeoDataset(nodeGeoDataset);
	layers.Add(nodeLayer);

	selectState=0;
	MatrixInit();
}

/////////////////////////////////////////////////////////////////////////////
// CShortestPathView printing

BOOL CShortestPathView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CShortestPathView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CShortestPathView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

void CShortestPathView::OnPrint(CDC* pDC, CPrintInfo* /*pInfo*/)
{
	// TODO: add customized printing code here
}

/////////////////////////////////////////////////////////////////////////////
// CShortestPathView diagnostics

#ifdef _DEBUG
void CShortestPathView::AssertValid() const
{
	CFormView::AssertValid();
}

void CShortestPathView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

CShortestPathDoc* CShortestPathView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CShortestPathDoc)));
	return (CShortestPathDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CShortestPathView message handlers

void CShortestPathView::OnSize(UINT nType, int cx, int cy) 
{
	CFormView::OnSize(nType, cx, cy);
	
	// TODO: Add your message handler code here
	if(m_map.m_hWnd)
		m_map.SetWindowPos(0,0,0,cx,cy,SWP_NOZORDER);	
}

BEGIN_EVENTSINK_MAP(CShortestPathView, CFormView)
    //{{AFX_EVENTSINK_MAP(CShortestPathView)
	ON_EVENT(CShortestPathView, IDC_MAP1, -605 /* MouseDown */, OnMouseDownMap1, VTS_I2 VTS_I2 VTS_I4 VTS_I4)
	ON_EVENT(CShortestPathView, IDC_MAP1, 3 /* AfterLayerDraw */, OnAfterLayerDrawMap1, VTS_I2 VTS_BOOL VTS_I4)
	//}}AFX_EVENTSINK_MAP
END_EVENTSINK_MAP()

void CShortestPathView::OnMouseDownMap1(short Button, short Shift, long X, long Y) 
{
	// TODO: Add your control notification handler code here
	switch (m_curTool)
	{
	case ID_MAP_SELECT:
		{
			double tolerance=m_map.ToMapDistance((float)5);
			CMoPoint pt(m_map.ToMapPoint((float)X,(float)Y));
			CMoLayers layers(m_map.GetLayers());
			CMoMapLayer layer(layers.Item(COleVariant(TEXT("shortpathnod"))));
			CMoRecordset recs(layer.SearchByDistance(pt,tolerance,""));
			if(!recs.GetEof())
			{
				CMoFields fields(recs.GetFields());
				CMoField nodeIdField(fields.Item(COleVariant(TEXT("NodeID"))));
				CMoField nodeShapeField(fields.Item(COleVariant(TEXT("Shape"))));
				switch(selectState)
				{
				case 0:
				case 2:
					startPointID=nodeIdField.GetValue().iVal;
					startPoint.AttachDispatch(nodeShapeField.GetValue().pdispVal);
					selectState=1;
					break;
				case 1:
					destinationPointID=nodeIdField.GetValue().iVal;
					destinationPoint.AttachDispatch(nodeShapeField.GetValue().pdispVal);
					selectState=2;
					Dijkstra();
					break;
				}
				m_map.Refresh();
			}
		}
	case ID_MAP_ZOOMIN:
		{
			CMoRectangle r(m_map.TrackRectangle());
			if(LPDISPATCH(r))
			{
				m_map.SetExtent(r);
			}
			break;
		}
	case ID_MAP_ZOOMOUT:
		{
			CMoRectangle r(m_map.GetExtent());
			r.ScaleRectangle(1.5);
			m_map.SetExtent(r);
			break;
		}
	case ID_MAP_PAN:
		{
			m_map.SetMousePointer(moPanning);
			m_map.Pan();
			m_map.SetMousePointer(moPan);
			break;
		}
	}
}

void CShortestPathView::OnAfterLayerDrawMap1(short index, BOOL canceled, long hDC) 
{
	// TODO: Add your control notification handler code here
	CMoLayers layers(m_map.GetLayers());
	CMoMapLayer layer(layers.Item(COleVariant(index)));
	CString layerName=layer.GetName();
	if(layerName=="shortpatharc" && selectState ==2 )
	{
		if(shortestPathNodeId.GetSize()==0)
			return;
		CMoSymbol sym;
		sym.CreateDispatch("MapObjects2.Symbol");
		sym.SetSymbolType(moLineSymbol);
		sym.SetSize(4);
		sym.SetColor(moOrange);
		CString expression;

		int* pathArcId=new int[shortestPathNodeId.GetSize()];
		for(int ii=0;ii<shortestPathNodeId.GetSize()-1;ii++)
			pathArcId[ii]=arcIdMatrix[shortestPathNodeId[ii]][shortestPathNodeId[ii+1]];
		pathArcId[ii]=arcIdMatrix[shortestPathNodeId[ii]][destinationPointID];

		for(ii=0;ii<shortestPathNodeId.GetSize();ii++)
		{
			expression.Format("ArcID = %d",pathArcId[ii]);
			CMoRecordset recs(layer.SearchExpression(expression));
			CMoFields fields(recs.GetFields());
			CMoField shpField(fields.Item(COleVariant("Shape")));
			CMoLine line(shpField.GetValue().pdispVal);
			m_map.DrawShape(line,sym);
		}

		delete[] pathArcId;
	}
	else if(layerName=="shortpathnod")
	{
		CMoSymbol sym;
		sym.CreateDispatch("MapObjects2.Symbol");
		sym.SetSymbolType(moPointSymbol);
		sym.SetStyle(moCircleMarker);
		sym.SetSize(6);
		sym.SetColor(moRed);
		switch(selectState)
		{
		case 1:
				m_map.DrawShape(startPoint,sym);
				break;
		case 2:
				m_map.DrawShape(startPoint,sym);
				m_map.DrawShape(destinationPoint,sym);
				break;
		}
	}
}

void CShortestPathView::MatrixInit()
{
	for(int ii=0;ii<NODENUM;ii++)
		for(int jj=0;jj<NODENUM;jj++)
		{
			if(ii==jj)
				costMatrix[ii][jj]=0.0;
			else
				costMatrix[ii][jj]=-1.0;

			arcIdMatrix[ii][jj]=-1;
		}


	CMoLayers layers(m_map.GetLayers());
	CMoMapLayer arcLayer(layers.Item(COleVariant(TEXT("shortpatharc"))));
	CMoRecordset arcRecs(arcLayer.GetRecords());

	while(!arcRecs.GetEof())
	{
		CMoFields fields(arcRecs.GetFields());

		CMoField arcIdField(fields.Item(COleVariant(TEXT("ArcID"))));
		int arcId=arcIdField.GetValue().iVal;

		CMoField fromNodeIdField(fields.Item(COleVariant(TEXT("从节点"))));
		int fromNodeId=fromNodeIdField.GetValue().iVal;

		CMoField toNodeIdField(fields.Item(COleVariant(TEXT("到节点"))));
		int toNodeId=toNodeIdField.GetValue().iVal;

		CMoField costField(fields.Item(COleVariant(TEXT("实际长度"))));
		double cost=costField.GetValue().dblVal;

		if(costMatrix[fromNodeId][toNodeId]==-1 || costMatrix[fromNodeId][toNodeId]>cost )
		{
			costMatrix[fromNodeId][toNodeId]=cost;
			costMatrix[toNodeId][fromNodeId]=cost;

			arcIdMatrix[fromNodeId][toNodeId]=arcId;
			arcIdMatrix[toNodeId][fromNodeId]=arcId;
		}

		arcRecs.MoveNext();
	}
}

void CShortestPathView::Dijkstra()
{
	if(startPointID==destinationPointID)
	{
		shortestPathNodeId.RemoveAll();
		return;
	}
	
	bool* s=new bool[NODENUM];
	double* dist=new double[NODENUM];
	CArray<int,int> *path=new CArray<int,int>[NODENUM];

	for(int ii=0;ii<NODENUM;ii++)		//初始化s,dist,path
	{
		s[ii]=false;
		dist[ii]=costMatrix[startPointID][ii];
		if(dist[ii]!=-1)
			path[ii].Add(startPointID);
	}
	s[startPointID]=true;

	for(ii=0;ii<=NODENUM-1;ii++)	
	{
		double currShortestDist=-1;
		int currShortestId=-1;
		for(int jj=0;jj<NODENUM;jj++)
		{
			if(s[jj]==false && dist[jj]!=-1)
				if( currShortestDist==-1 || (currShortestDist!=-1 && currShortestDist>dist[jj]))
				{
					currShortestDist=dist[jj];
					currShortestId=jj;
				}
		}

		if(currShortestDist==-1)
		{
			shortestPathNodeId.RemoveAll();
			break;
		}

		s[currShortestId]=true;
		if(currShortestId==destinationPointID)
		{
			PathCopy(path[currShortestId],shortestPathNodeId);
			break;
		}

		for(jj=0;jj<NODENUM;jj++)
		{
			if(s[jj]==false && costMatrix[currShortestId][jj]!=-1)
				if(dist[jj]==-1 || (dist[jj]!=-1 && dist[jj]>dist[currShortestId]+costMatrix[currShortestId][jj]))
				{
					dist[jj]=dist[currShortestId]+costMatrix[currShortestId][jj];
					PathCopy(path[currShortestId],path[jj]);
					path[jj].Add(currShortestId);
				}
		}
	}

	delete[] s;
	delete[] dist;
	delete[] path;
}

void CShortestPathView::OnMapTool(UINT nID) 
{
	// TODO: Add your command handler code here
	m_curTool=nID;	
	switch (m_curTool)
	{
	case ID_MAP_SELECT:
		m_map.SetMousePointer(moDefault);
		break;
	case ID_MAP_ZOOMIN:
		m_map.SetMousePointer(moZoomIn);
		break;
	case ID_MAP_ZOOMOUT:
		m_map.SetMousePointer(moZoomOut);
		break;
	case ID_MAP_PAN:
		m_map.SetMousePointer(moPan);
		break;
	}
}

void CShortestPathView::OnUpdateMapTool(CCmdUI* pCmdUI) 
{
	// TODO: Add your command update UI handler code here
	pCmdUI->SetCheck(pCmdUI->m_nID==m_curTool);	
}

void CShortestPathView::OnMapFullextent() 
{
	// TODO: Add your command handler code here
	CMoRectangle r(m_map.GetFullExtent());
	m_map.SetExtent(r);
}