二维空间的最近点对问题图解(动态规划算法实现)

元始天尊 · 发表于 2014-7-29 13:11:08

欢迎访问技术宅的结界，请注册或者登录吧。

您需要登录才可以下载或查看，没有账号？立即注册→加入我们

×

在网上搜了一遍，貌似没找到这种实际代码，于是自己用MFC写了一下，当然这种问题适合用图形方式来直观展示，整个搜索过程一目了然
采用的算法是动态规划，应用算法之前需要对所有点先按照横坐标排下序，这样有利于区域判定

效果展示：
红色代表已找到的最近点，蓝色表示正在找的点
QQ图片20140729131005.jpg

核心代码：

// FindNearestPointDlg.cpp : implementation file
//
#include "stdafx.h"
#include "FindNearestPoint.h"
#include "FindNearestPointDlg.h"
#include <math.h>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define distance(a,b) sqrt(((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)))
#define abs(a,b) ((a>b)?a-b:b-a)
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CFindNearestPointDlg dialog
int showdata::curminindex1=INT_MAX;
int showdata::curminindex2=INT_MAX;
float showdata::mindis=INT_MAX;
CFindNearestPointDlg::CFindNearestPointDlg(CWnd* pParent /*=NULL*/)
: CDialog(CFindNearestPointDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CFindNearestPointDlg)
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CFindNearestPointDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CFindNearestPointDlg)
DDX_Control(pDX, IDC_VELOCITY, m_velocity);
DDX_Control(pDX, IDC_PTNUM, m_ptnum);
DDX_Control(pDX, IDC_DRAW, m_draw);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CFindNearestPointDlg, CDialog)
//{{AFX_MSG_MAP(CFindNearestPointDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_MAKE, OnMake)
ON_WM_TIMER()
ON_NOTIFY(NM_CUSTOMDRAW, IDC_VELOCITY, OnCustomdrawVelocity)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CFindNearestPointDlg message handlers
BOOL CFindNearestPointDlg::OnInitDialog()
{
CDialog::OnInitDialog();
// Add "About..." menu item to system menu.
// IDM_ABOUTBOX must be in the system command range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX < 0xF000);
CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
CString strAboutMenu;
strAboutMenu.LoadString(IDS_ABOUTBOX);
if (!strAboutMenu.IsEmpty())
{
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
}
}
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
// TODO: Add extra initialization here
srand(time(NULL));
SetTimer(1,200,NULL);
m_ptnum.SetRange(10,1000);
m_ptnum.SetPos(10);
m_velocity.SetRange(200,1000);
m_velocity.SetPos(200);
return TRUE; // return TRUE unless you set the focus to a control
}
void CFindNearestPointDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
CDialog::OnSysCommand(nID, lParam);
}
// If you add a minimize button to your dialog, you will need the code below
// to draw the icon. For MFC applications using the document/view model,
// this is automatically done for you by the framework.
void CFindNearestPointDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting
SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialog::OnPaint();
if(show.empty())
return;
showdata& cur=show.front();
CClientDC dc(&m_draw);
RECT rt;
CBrush clearbrush(RGB(255,255,255));
CDC MemDC;
CBitmap MemBitmap;
m_draw.GetClientRect(&rt);
MemDC.CreateCompatibleDC(&dc);
MemBitmap.CreateCompatibleBitmap(&dc,rt.right,rt.bottom);
MemDC.SelectObject(&MemBitmap);
MemDC.FillRect(&rt,&clearbrush);
CBrush normalbrush(RGB(0,0,0)),stressbrush(RGB(0,255,0,));
CPen normalpen(PS_SOLID,1,RGB(0,0,0)),stresspen(PS_SOLID,2,RGB(0,255,0));
MemDC.SelectObject(&normalbrush);
for(int i=0;i<cur.points.size();i++)
{
pt& curpt=cur.points.at(i);
MemDC.Ellipse(curpt.x-5,curpt.y-5,curpt.x+5,curpt.y+5);
}
if(cur.type == 1)
{
MemDC.SelectObject(&stressbrush);
pt& pt1=cur.points.at(cur.data.line.index1);
pt& pt2=cur.points.at(cur.data.line.index2);
MemDC.Ellipse(pt1.x-5,pt1.y-5,pt1.x+5,pt1.y+5);
MemDC.Ellipse(pt2.x-5,pt2.y-5,pt2.x+5,pt2.y+5);
MemDC.SelectObject(stresspen);
MemDC.MoveTo(pt1.x,pt1.y);
MemDC.LineTo(pt2.x,pt2.y);
}
else if(cur.type == 2)
{
MemDC.SelectObject(&stressbrush);
pt& pt1=cur.points.at(cur.data.rect.leftindex);
pt& pt2=cur.points.at(cur.data.rect.rightindex);
MemDC.Ellipse(pt1.x-5,pt1.y-5,pt1.x+5,pt1.y+5);
MemDC.Ellipse(pt2.x-5,pt2.y-5,pt2.x+5,pt2.y+5);
MemDC.SelectObject(stresspen);
MemDC.MoveTo(pt1.x,pt1.y);
MemDC.LineTo(pt2.x,pt2.y);
MemDC.SelectObject(normalpen);
int d=cur.data.rect.d;
pt& mid=cur.points.at(cur.data.rect.midindex);
MemDC.MoveTo(mid.x,mid.y-d);
MemDC.LineTo(mid.x+d,mid.y-d);
MemDC.LineTo(mid.x+d,mid.y+d);
MemDC.LineTo(mid.x,mid.y+d);
MemDC.LineTo(mid.x,mid.y-d);
}
if(cur.mindis < INT_MAX)//如果有最小距离点
{
CBrush b(RGB(255,0,0));
CPen p(PS_SOLID,2,RGB(255,0,0));
pt& pt1=cur.points.at(cur.curminindex1);
pt& pt2=cur.points.at(cur.curminindex2);
MemDC.SelectObject(b);
MemDC.SelectObject(p);
MemDC.Ellipse(pt1.x-5,pt1.y-5,pt1.x+5,pt1.y+5);
MemDC.Ellipse(pt2.x-5,pt2.y-5,pt2.x+5,pt2.y+5);
MemDC.MoveTo(pt1.x,pt1.y);
MemDC.LineTo(pt2.x,pt2.y);
}
if(show.size() > 1)
show.pop();
dc.BitBlt(0,0,rt.right,rt.bottom,&MemDC,0,0,SRCCOPY);
MemDC.DeleteDC();
MemBitmap.DeleteObject();
}
}
// The system calls this to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CFindNearestPointDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
void CFindNearestPointDlg::OnMake()
{
// TODO: Add your control notification handler code here
data.clear();
while(!show.empty())
show.pop();
showdata::curminindex1=INT_MAX;
showdata::curminindex2=INT_MAX;
showdata::mindis=INT_MAX;
RECT rt;
m_draw.GetClientRect(&rt);
int i,j;
int size=m_ptnum.GetPos();
TRACE("width:%d height:%d\n",rt.right,rt.bottom);
for(i=0;i<size;i++)
{
int x=rand()%rt.right,y=rand()%rt.bottom;
data.push_back(pt(x,y));
}
//先排序
for(i=0;i < size-1;i++)
{
for(j=size-1;j > i;j--)
{
if(data[j].x < data[j-1].x)
{
int tmpx=data[j].x;
int tmpy=data[j].y;
data[j].x=data[j-1].x;
data[j].y=data[j-1].y;
data[j-1].x=tmpx;
data[j-1].y=tmpy;
}
}
}
for(i=0;i<size;i++)
{
TRACE("%d:(%d,%d)\n",i,data.at(i).x,data.at(i).y);
}
show.push(showdata(data));
FindNear(0,size-1);
show.push(showdata(data));
pt& pt1=data.at(showdata::curminindex1);
pt& pt2=data.at(showdata::curminindex2);
TRACE("min:(%d,%d)->(%d,%d)=%f\n",pt1.x,pt1.y,pt2.x,pt2.y,showdata::mindis);
Invalidate(FALSE);
}
void CFindNearestPointDlg::OnTimer(UINT nIDEvent)
{
// TODO: Add your message handler code here and/or call default
Invalidate(FALSE);
CDialog::OnTimer(nIDEvent);
}
float CFindNearestPointDlg::FindnearIntersect(float& curmin,int begin,int end)
{
int mid=(end-begin)/2;
//找到所有在中位数左侧且横坐标距离中位数横坐标小于curmin的点
for(int i=mid;i >= begin;i--)
{
if(data[mid].x - data[i].x > curmin)
break;
//对于每一个这样的点寻找右侧可能的6个邻点
for(int j=mid+1;j <= end;j++)
{
if(data[j].x - data[mid].x > curmin)
break;
if(abs(data[j].y,data[mid].y) > curmin)
continue;
show.push(showdata(i,j,mid,curmin,data,curmin));
//对于在2d*d矩形内的点
float dis=distance(data[i],data[j]);
if(dis < curmin)
{
curmin=dis;
show.push(showdata(i,j,data,curmin));
}
}
}
return curmin;
}
float CFindNearestPointDlg::FindNear(int begin,int end)
{
if(begin == end)//如果只有1个点，则距离设为无穷大
return INT_MAX;
else if(begin+1 == end)//如果有2个点，则返回他们的距离
{
float dis=distance(data[begin],data[end]);
show.push(showdata(begin,end,data,dis));
return dis;
}
int mid=(end+begin)/2;
//(begin,end)点的最小距离=min[(begin,mid)点的最小距离,(mid+1,end)点的最小距离,(begin,mid)右侧点和(mid+1,end)左侧点最小距离]
float d1=FindNear(begin,mid);//(begin,mid)点的最小距离
float d2=FindNear(mid+1,end);//(mid+1,end)点的最小距离
float curmin=(d1<d2)?d1:d2;
return FindnearIntersect(curmin,begin,end);//(begin,mid)右侧点和(mid+1,end)左侧点最小距离
}
void CFindNearestPointDlg::OnCustomdrawVelocity(NMHDR* pNMHDR, LRESULT* pResult)
{
// TODO: Add your control notification handler code here
KillTimer(1);
SetTimer(1,m_velocity.GetPos(),NULL);
*pResult = 0;
}

复制代码

元始天尊 · 发表于 2014-7-29 13:11:36

可以调整点数和搜索速度
工程：

FindNearestPoint.rar (1 MB, 下载次数: 71)

账号		自动登录	找回密码
密码			立即注册→加入我们