convexhullview.cpp

Gramham法求解凸包。从最基本数据结构定义开始实现

    out.y = sY;
}

/*
坐标变换，从坐标轴坐标变换到客户端窗口坐标
*/
//##ModelId=443378C8034D
VOID CConvexHullView::AxisPointToClientPoint(dse::point2d &p, CRect &clientRect, dse::point2d &out)
{
    double cmX, cmY;
    cmX = clientRect.left + clientRect.Width() / 2;
    cmY = clientRect.top + clientRect.Height() / 2;

    double x, y;
    x = p.x;
    y = p.y;
    x += m_AxisXOffset;
    y += m_AxisYOffset;
    x *= m_ZoomRatio;
    y *= m_ZoomRatio;
    out.x = x + cmX;
    out.y = -(y - cmY);
}

// 缩小显示区域
//##ModelId=443378C8031D
VOID CConvexHullView::ZoomOut(double ratio )
{
    m_ZoomRatio /= ratio;
    Invalidate(FALSE);
}

// 放大显示区域
//##ModelId=443378C80325
VOID CConvexHullView::ZoomIn(double ratio )
{
    m_ZoomRatio *= ratio;
    Invalidate(FALSE);
}

// 根据显示内容自动调整所放比例和位置
//##ModelId=443378C8032E
VOID CConvexHullView::ZoomAdjust()
{

    double l, t, r, b;
    dse::convex_hull &ch = GetDocument()->GetConvexHull();
    dse::size_t i, count = ch.get_points_count();

    if(count == 0)
        return;

    dse::point2d &p = ch.get_point(0);
    l=p.x;
    t=p.y;
    r=p.x;
    b=p.y;
    for(i = 1; i < count; i++)
    {
        dse::point2d &p = ch.get_point(i);
        if(p.x < l) l = p.x;
        if(p.y < t) t = p.y;
        if(p.x > r) r = p.x;
        if(p.y > b) b = p.y;
    }

    CRect rect;
    GetClientRect(rect);
    double pw = r - l, ph = b - t;
    if(IS_ZERO(pw)) pw = 1 / m_ZoomRatio;
    if(IS_ZERO(ph)) ph = 1 / m_ZoomRatio;

    if(count != 1)
    {
        double ratio1 = rect.Width() / pw, ratio2 = rect.Height() / ph;
        m_ZoomRatio = min(ratio1, ratio2);
        m_ZoomRatio /= 1.2;
    }
    
    m_AxisXOffset = -(l + pw / 2);
    m_AxisYOffset = - (t + ph / 2);

    Invalidate(FALSE);
}

// 在当前显示区域随机添加点
//##ModelId=443378C8033B
VOID CConvexHullView::AddRandomPoints(int n)
{
    if(n >= 50000)
    {
        if(AfxMessageBox("您要添加的点太多，有可能超出本程序的处理能力。本程序对这种情况下发生的意外情况将不负责。确认要继续吗？", MB_ICONQUESTION + MB_YESNO) != IDYES)
            return;
    }

    CWaitCursor c;
    
    CRect r;
    GetClientRect(r);
    dse::point2d p;
    double x, y, w, h;
    x = r.Width() * 0.1;
    y = r.Height() * 0.1;
    w = r.Width() * 0.8;
    h = r.Height() * 0.8;

    for(int i = 0; i < n; i++)
    {
        ClientPointToAxisPoint(dse::point2d(x + w * rand() / RAND_MAX,  y + h * rand() / RAND_MAX), r, p);
        GetDocument()->GetConvexHull().add_point(p.x, p.y);
    }

    GetDocument()->SetModifiedFlag(TRUE);
    Invalidate(FALSE);
}

// 设置客户区的工作状态
//##ModelId=443378C80315
VOID CConvexHullView::SetClientStatus(ClientStatus st)
{
    if(m_ClientStatus == st) return;

    if(m_ClientStatus == CLIENT_STATUS_DEMO)
        KillTimer(ID_TIMER_DEMO);

    if(st == CLIENT_STATUS_DEMO)
    {
        //Demo模式，进行演示
        GetDocument()->GetConvexHull().prepare();
        Invalidate(FALSE);
        m_IsDemoPaused = FALSE;
        SetTimer(ID_TIMER_DEMO, 1000, NULL);
    }
    m_ClientStatus = st; 

}

// 暂停演示
//##ModelId=443378C8031B
VOID CConvexHullView::PauseDemo(BOOL bPause)
{
    m_IsDemoPaused = bPause;
}

// 通过鼠标滚轮所放显示区域
//##ModelId=443378C803C8
BOOL CConvexHullView::OnMouseWheel(UINT nFlags, short zDelta, CPoint pt) 
{
    if(zDelta < 0 )
    {
        ZoomOut();
    }
    else if(zDelta > 0)
    {
        ZoomIn();
    }
    
	return CView::OnMouseWheel(nFlags, zDelta, pt);
}

// 通过鼠标位置添加点
//##ModelId=443378C8032F
void CConvexHullView::AddPointByMouse(CPoint &point)
{
    dse::point2d p;
    CRect r;
    GetClientRect(r);
    ClientPointToAxisPoint(dse::point2d(point.x, point.y), r, p);

    GetDocument()->GetConvexHull().add_point(p.x, p.y);
    GetDocument()->SetModifiedFlag(TRUE);
    Invalidate(FALSE);
}

//通过鼠标位置删除点，radius为鼠标覆盖的半径，once指定是否只删除一个点
//##ModelId=443378C80331
void CConvexHullView::ErasePointsByMouse(CPoint &point, int radius, BOOL once)
{
    dse::point2d p;
    CRect r;
    GetClientRect(r);
    dse::size_t i;
    dse::convex_hull &ch = GetDocument()->GetConvexHull();
    BOOL modified = FALSE;
    for(i = 0; i < ch.get_points_count(); )
    {
        AxisPointToClientPoint(ch.get_point(i), r, p);
        if(p.x - radius <= point.x && point.x <= p.x + radius
            &&
           p.y - radius <= point.y && point.y <= p.y + radius)
        {
            ch.delete_point(i);
            modified = TRUE;
            if(once)
                break;
        }
        else
        {
            i++;
        }
    }
    if(modified)
    {
        GetDocument()->SetModifiedFlag(TRUE);
        Invalidate(FALSE);
    }
}

//##ModelId=443378C803C4
void CConvexHullView::OnMouseMove(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
    dse::point2d p;
    CRect r;
    GetClientRect(r);
    ClientPointToAxisPoint(dse::point2d(point.x, point.y), r, p);

    if(IsClientStatus_None() || IsClientStatus_Demo())
    {
        //拖动显示区域
        if(m_IsDragging)
        {
            dse::point2d &p1 = p, p2;
            ClientPointToAxisPoint(dse::point2d(point.x, point.y), r, p1);
            ClientPointToAxisPoint(dse::point2d(m_LastMousePoint.x, m_LastMousePoint.y), r, p2);
	        m_AxisXOffset += p1.x - p2.x;
            m_AxisYOffset += p1.y - p2.y;

            m_LastMousePoint = point;
            Invalidate(FALSE);
        }
    }
    else if(IsClientStatus_PutPoint())
    {
        //通过鼠标添加点
        if((nFlags & MK_LBUTTON) == MK_LBUTTON 
            &&
            (nFlags & MK_SHIFT) == MK_SHIFT)
            AddPointByMouse(point);
    }
    else if(IsClientStatus_DeletePoint())
    {
        //通过鼠标删除点（只删除一个）
        if((nFlags & MK_LBUTTON) == MK_LBUTTON)
            ErasePointsByMouse(point, 3, TRUE);
    }
    else if(IsClientStatus_ErasePoints())
    {
        //通过鼠标擦除点，擦除一片范围
        if((nFlags & MK_LBUTTON) == MK_LBUTTON)
            ErasePointsByMouse(point, 10, FALSE);
    }

    //状态栏提示鼠标位置
    CString s;
    s.Format("鼠标坐标：(%.4lf, %.4lf)", p.x, p.y);
    ((CMainFrame *)AfxGetMainWnd())->GetStatusBar()->SetPaneText(0, s);
	CView::OnMouseMove(nFlags, point);
}

//##ModelId=443378C803D1
void CConvexHullView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
    SetCapture();
	if((nFlags & MK_LBUTTON) == MK_LBUTTON)
    {
        if(IsClientStatus_None() || IsClientStatus_Demo())
        {
            //非加点状态，仅仅拖动
            m_IsDragging = TRUE;
            m_LastMousePoint = point;
            SetCursor(::LoadCursor(AfxGetInstanceHandle(), MAKEINTRESOURCE(IDC_HAND_CLOSE) ));
        }
        else if(IsClientStatus_PutPoint())
        {
            AddPointByMouse(point);
        }
        else if(IsClientStatus_DeletePoint())
        {
            ErasePointsByMouse(point, 3, TRUE);
        }
        else if(IsClientStatus_ErasePoints())
        {
            ErasePointsByMouse(point, 10, FALSE);
        }
    }
	CView::OnLButtonDown(nFlags, point);
}

//##ModelId=443378C803DB
void CConvexHullView::OnLButtonUp(UINT nFlags, CPoint point) 
{
    ReleaseCapture();
	// TODO: Add your message handler code here and/or call default
	m_IsDragging = FALSE;
	CView::OnLButtonUp(nFlags, point);
}

//##ModelId=443378C803E4
void CConvexHullView::OnTimer(UINT nIDEvent) 
{
	// TODO: Add your message handler code here and/or call default
	
    if(nIDEvent == ID_TIMER_DEMO)
    {
        //动画演示

        if(!m_IsDemoPaused)
        {
            if(!GetDocument()->GetConvexHull().finished())
            {
                GetDocument()->GetConvexHull().search_next_point();
                Invalidate(FALSE);
            }
            else
            {
                SetClientStatus(CLIENT_STATUS_NONE);
            }
        }
    }
	CView::OnTimer(nIDEvent);
}

//##ModelId=443378C90004
void CConvexHullView::OnRButtonDown(UINT nFlags, CPoint point) 
{
	// TODO: Add your message handler code here and/or call default
	if(IsClientStatus_PutPoint())
        SetClientStatus(CLIENT_STATUS_NONE);
	if(IsClientStatus_DeletePoint())
        SetClientStatus(CLIENT_STATUS_NONE);
	if(IsClientStatus_ErasePoints())
        SetClientStatus(CLIENT_STATUS_NONE);
    
	CView::OnRButtonDown(nFlags, point);
}

//设置正确的鼠标指针样式
//##ModelId=443378C90008
BOOL CConvexHullView::OnSetCursor(CWnd* pWnd, UINT nHitTest, UINT message) 
{
	// TODO: Add your message handler code here and/or call default
    if(IsClientStatus_DeletePoint() || IsClientStatus_PutPoint())
        SetCursor(::LoadCursor(NULL, IDC_CROSS));
    else if(IsClientStatus_ErasePoints())
        SetCursor(::LoadCursor(AfxGetInstanceHandle(), MAKEINTRESOURCE(IDC_ERASE_POINTS)));
    else
    {
        if(m_IsDragging)
            SetCursor(::LoadCursor(AfxGetInstanceHandle(), MAKEINTRESOURCE(IDC_HAND_CLOSE) ));
        else
            SetCursor(::LoadCursor(AfxGetInstanceHandle(), MAKEINTRESOURCE(IDC_HAND_OPEN) ));
    }
    return TRUE;
}

//由于使用了双缓冲防闪烁，窗口大小变化的时候要重新构造后备缓冲区
//##ModelId=443378C90011
void CConvexHullView::OnSize(UINT nType, int cx, int cy) 
{
	CView::OnSize(nType, cx, cy);

    
    if(m_pBufferOldBitmap != NULL)
    {
        m_BufferDC.SelectObject(m_pBufferOldBitmap);
        m_pBufferOldBitmap = NULL;
        m_BufferBitmap.DeleteObject();
    }
    
    m_BufferBitmap.CreateCompatibleBitmap(GetDC(), cx, cy); 
    m_pBufferOldBitmap = m_BufferDC.SelectObject(&m_BufferBitmap); 
}

//##ModelId=443378C9001C
void CConvexHullView::OnDestroy() 
{
	CView::OnDestroy();
	
	// TODO: Add your message handler code here
    if(m_pBufferOldBitmap != NULL)
    {
        m_BufferDC.SelectObject(m_pBufferOldBitmap);
        m_pBufferOldBitmap = NULL;
        m_BufferBitmap.DeleteObject();
    }
}