delaunay网格算法源码

// sanjiaowangView.cpp : implementation of the CSanjiaowangView class // #include "stdafx.h" #include "sanjiaowang.h" #include "sanjiaowangDoc.h" #include "sanjiaowangView.h" #include<windows.h> #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // CSanjiaowangView IMPLEMENT_DYNCREATE(CSanjiaowangView, CView) BEGIN_MESSAGE_MAP(CSanjiaowangView, CView) //{{AFX_MSG_MAP(CSanjiaowangView) ON_COMMAND(ID_dingdian, Ondingdian) ON_COMMAND(ID_Gouwang, OnGouwang) ON_WM_LBUTTONDOWN() ON_COMMAND(ID_Clear, OnClear) //}}AFX_MSG_MAP // Standard printing commands ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint) ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint) ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview) END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // CSanjiaowangView construction/destruction CSanjiaowangView::CSanjiaowangView() { // TODO: add construction code here m_dingdian=false; } CSanjiaowangView::~CSanjiaowangView() { } BOOL CSanjiaowangView::PreCreateWindow(CREATESTRUCT& cs) { // TODO: Modify the Window class or styles here by modifying // the CREATESTRUCT cs MessageBox("请阅读文件夹中的说明文档"); return CView::PreCreateWindow(cs); } ///////////////////////////////////////////////////////////////////////////// // CSanjiaowangView drawing void CSanjiaowangView::OnDraw(CDC* pDC) { CSanjiaowangDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); // TODO: add draw code for native data here } ///////////////////////////////////////////////////////////////////////////// // CSanjiaowangView printing BOOL CSanjiaowangView::OnPreparePrinting(CPrintInfo* pInfo) { // default preparation return DoPreparePrinting(pInfo); } void CSanjiaowangView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) { // TODO: add extra initialization before printing } void CSanjiaowangView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/) { // TODO: add cleanup after printing } ///////////////////////////////////////////////////////////////////////////// // CSanjiaowangView diagnostics #ifdef _DEBUG void CSanjiaowangView::AssertValid() const { CView::AssertValid(); } void CSanjiaowangView::Dump(CDumpContext& dc) const { CView::Dump(dc); } CSanjiaowangDoc* CSanjiaowangView::GetDocument() // non-debug version is inline { ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CSanjiaowangDoc))); return (CSanjiaowangDoc*)m_pDocument; } #endif //_DEBUG ///////////////////////////////////////////////////////////////////////////// // CSanjiaowangView message handlers void CSanjiaowangView::delaunay(CPoint p1, CPoint p2) { CPoint p3, ThirdPoint; ThirdPoint = GetThirdPoint(p1,p2); //获取第三点(采用余弦值最小判断) if (ThirdPoint.x!=0 && ThirdPoint.y!=0) { p3 = ThirdPoint; this->BuildTriangle(p1, p2, p3); Line l1; l1.p1 = p1; l1.p2 = p2; a2.push_back(l1); } else return;//储存已构成的直线 delaunay(p1,p3); delaunay(p3,p2); //标记已构三角形的边，对尚未构三角形的边用算法进行递归调用 } CPoint CSanjiaowangView::GetThirdPoint(CPoint p1, CPoint p2) { bool p=this->panduan(p1,p2); double temp=1; int j=0; for(int i=0;i<a1.size();i++) { double equation; equation = ((p1.y - p2.y) * (a1[i].x - p2.x)) - ((a1[i].y - p2.y) * (p1.x - p2.x));//确定基线的方向 if(equation<=0) continue; double a=sqrt(pow(p1.x-a1[i].x,2)+pow(p1.y-a1[i].y,2)); double b=sqrt(pow(p2.x-a1[i].x,2)+pow(p2.y-a1[i].y,2)); double c=sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2)); double d=(a*a+b*b-c*c)/(2*a*b); if(d<temp && equation>0 && p) { temp=d; j=i; } } if(j!=0) return a1[j]; else return CPoint(0,0); } void CSanjiaowangView::Ondingdian() { m_dingdian=true; } void CSanjiaowangView::OnGouwang() { // TODO: Add your command handler code here m_dingdian = false; int n = a1.size(); for (int i=0; i<n-1; i++)//确定基线 { for (int j=i+1; j<n; j++) { if (a1[i].x > a1[j].x) { CPoint tp1; tp1 = a1[i]; a1[i] = a1[j]; a1[j] = tp1; } } } if (n>=3) { if (a1[0].y > a1[1].y) this->delaunay(a1[0], a1[1]); else this->delaunay(a1[1], a1[0]); } else MessageBox("请输入至少三个以上的点"); a2.clear(); } void CSanjiaowangView::OnLButtonDown(UINT nFlags, CPoint point) { // TODO: Add your message handler code here and/or call default if(m_dingdian) { CClientDC dc(this); dc.Ellipse(point.x,point.y,point.x +5,point.y+5); a1.push_back(point); } CView::OnLButtonDown(nFlags, point); } bool CSanjiaowangView::panduan(CPoint p1, CPoint p2) { bool p=true; Line l1; l1.p1=p1; l1.p2=p2; for(int i=0;i<a2.size();i++) { if(l1.p1==a2[i].p1 && l1.p2==a2[i].p2) p=false; } return p; } void CSanjiaowangView::BuildTriangle(CPoint p1, CPoint p2, CPoint p3) { CClientDC dc(this); dc.MoveTo(p1.x,p1.y); dc.LineTo(p2.x,p2.y); dc.MoveTo(p2.x,p2.y); dc.LineTo(p3.x,p3.y); dc.MoveTo(p1.x,p1.y); dc.LineTo(p3.x,p3.y); } void CSanjiaowangView::OnClear() { // TODO: Add your command handler code here CClientDC dc(this); CRect rc; GetClientRect(rc); dc.FillSolidRect(rc,dc.GetBkColor()); }