;;; 用递归解决
;;; use recursion to solve this problem (divide-and-conquer)
(defun f2 (Pts TOL / l m n pt1 pt2 Pts1 Pts2 Pts3 Pts4 Mx x1 x2)
(setq l (length Pts))
(cond
((= l 1) nil)
((= l 2)
;; 两点还用说
;; judge directly if 2 points
(setq pt1 (car Pts))
(setq pt2 (cadr Pts))
(if (and (equal (car pt1) (car pt2) TOL)
(equal (cadr pt1) (cadr pt2) TOL)
(<= (distance pt1 pt2) TOL)
)
(setq pairs (cons pt1 pairs) ;add the start point into pairs;
pairs (cons pt2 pairs) ;add the end point into pairs;
)
)
)
((> l 2)
(setq n (/ l 2)
m (- l n)
)
(setq Pts1 (Array Pts n)) ;Divide
(setq Pts2 (cadr Pts1)) ;R points
(setq Pts1 (car Pts1)) ;L points
(f2 (reverse Pts1) TOL) ;Recurse Left
(f2 Pts2 TOL) ;Recurse Right
(setq Mx (caar Pts2)) ;Midpoint
(setq x1 (- Mx tol)) ;L points in the TOL
(setq x2 (+ Mx tol)) ;R points in the TOL
(while (and pts2 (<= (caar pts2) x2)) ;gather the points in the Right
(setq Pts3 (cons (cons (car pts2) 1) Pts3)) ;1 means in the Right
(setq pts2 (cdr pts2))
)
(setq pts3 (reverse pts3))
(while (and pts1 (>= (caar pts1) x1)) ;gather the points in the Left
(setq Pts3 (cons (cons (car pts1) 0) Pts3)) ;0 means in the Left
(setq pts1 (cdr pts1))
)
(setq Pts3 (sorty pts3 tol)) ;sort these points by Y value
(setq pts4 (cdr pts3)) ;consider these points one by one
(if pts4
(while pts3
(setq pt1 (caar pts3))
(setq pt2 (caar pts4))
(while (and pts4 (<= (- (cadr pt2) (cadr pt1)) tol))
(if (and (/= (cdar pts3) (cdar pts4)) ;different side;
(equal (car pt1) (car pt2) tol) ;x value in tol;
(<= (distance pt1 pt2) tol) ;distance <= tol;
)
(setq pairs (cons pt1 pairs) ;add the start point into pairs;
pairs (cons pt2 pairs) ;add the end point into pairs;
)
)
(setq pts4 (cdr pts4))
(setq pt2 (caar pts4))
)
(setq pts3 (cdr pts3))
(setq pts4 (cdr pts3))
)
)
Pairs
)
)
)Ok ,this is the main code. I considered the duplicate points. So this program can be used for removing duplicate elements, or finding those closed points,etc. these kinds of finding will get easier and quicklier. I have no idea for analysing the time complexity of this algorithm. maybe it's in O(n*log(n)),because I tested it many times, found that it's faster than pkohut's. I think his algorithm is in O(n*log(n)).
by the way, I posted these LSP files,and a program for generating random points(it's real random,not fake random). just for 2004-2006,if someone can help me to compile these to the other versions,I will thank him very much.
//-----------------------------------------------------------------------------
//----- acrxEntryPoint.h
//-----------------------------------------------------------------------------
#include "StdAfx.h"
#include "resource.h"
#include "tchar.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
//-----------------------------------------------------------------------------
#define szRDS _RXST("")
//-----------------------------------------------------------------------------
//----- ObjectARX EntryPoint
class CCreatRandomPointsApp : public AcRxArxApp {
public:
CCreatRandomPointsApp () : AcRxArxApp () {}
virtual AcRx::AppRetCode On_kInitAppMsg (void *pkt) {
// TODO: Load dependencies here
// You *must* call On_kInitAppMsg here
AcRx::AppRetCode retCode =AcRxArxApp::On_kInitAppMsg (pkt) ;
// TODO: Add your initialization code here
acutPrintf(_T("\nThe command is:rand."));
return (retCode) ;
}
virtual AcRx::AppRetCode On_kUnloadAppMsg (void *pkt) {
// TODO: Add your code here
// You *must* call On_kUnloadAppMsg here
AcRx::AppRetCode retCode =AcRxArxApp::On_kUnloadAppMsg (pkt) ;
// TODO: Unload dependencies here
return (retCode) ;
}
virtual void RegisterServerComponents () {
}
// - CreatRandomPoints._Rand command (do not rename)
static void CreatRandomPoints_Rand(void)
{
// Add your code for command CreatRandomPoints._Rand here
// 输入范围
ads_point pt1,pt2;
int ret=acedGetPoint(NULL,_T("\nPlease drag the First coner of region: "),pt1);
if (ret!= RTNORM)
{
acutPrintf(_T("\nInvalid!"));
return;
}
ret=acedGetCorner(pt1,_T("\nPlease drag the region: "),pt2) ;
if (ret!= RTNORM)
{
acutPrintf(_T("\nInvalid!"));
return;
}
//转化坐标系
acdbUcs2Wcs(pt1,pt1,0);
acdbUcs2Wcs(pt2,pt2,0);
//防止点过于密集
double deltaX = (pt2[X]-pt1[X]);
double deltaY = (pt2[Y]-pt1[Y]);
if (abs(deltaX) < 1e-4 || abs(deltaY) < 1e-4 )
{
acutPrintf(_T("\nYour region is too small,Please drag it again."));
return;
}
deltaX = deltaX / 32767.0;
deltaY = deltaY / 32767.0;
//输入数量
double Number;
acedInitGet(7,NULL);
ret = acedGetReal(_T("\nPlease Enter the Number of Points:"),&Number);
if (ret!= RTNORM)
{
acutPrintf(_T("\nInvalid input!"));
return;
}
//初始化种子
srand((unsigned int)time(NULL));
//获得块表
Acad::ErrorStatus es;
AcDbBlockTable * pBlockTable;
es=acdbHostApplicationServices()->workingDatabase()->getBlockTable(pBlockTable, AcDb::kForRead);
if(es!=Acad::eOk)
return ;
pBlockTable->close();
//获得当前空间
resbuf tilemode;
AcDbBlockTableRecord * pBlockTableRecord;
acedGetVar(_T("TILEMODE"),&tilemode);
if(tilemode.resval.rint )
es=pBlockTable->getAt(ACDB_MODEL_SPACE, pBlockTableRecord,AcDb::kForWrite);
else
es=pBlockTable->getAt(ACDB_PAPER_SPACE, pBlockTableRecord,AcDb::kForWrite);
if (es!=Acad::eOk)
return;
AcDbPoint * pPoint;
AcGePoint3d pt;
double Cx,Cy;
Cx = pt1[X];
Cy = pt1[Y];
pt.z = 0;
//画点
int n = (int) Number;
for (int i = 0;i<n;i++)
{
pt.x = Cx + deltaX * rand();
pt.y = Cy + deltaY * rand();
pPoint = new AcDbPoint(pt);
es=pBlockTableRecord->appendAcDbEntity(pPoint);
pPoint->close();
}
pBlockTableRecord->close();
}
} ;
//-----------------------------------------------------------------------------
IMPLEMENT_ARX_ENTRYPOINT(CCreatRandomPointsApp)
ACED_ARXCOMMAND_ENTRY_AUTO(CCreatRandomPointsApp, CreatRandomPoints, _Rand, Rand, ACRX_CMD_TRANSPARENT, NULL)
