### Author Topic: (Challenge) To draw the shortest lwpolyline  (Read 25896 times)

0 Members and 1 Guest are viewing this topic.

#### ronjonp

• Needs a day job
• Posts: 6901
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #15 on: September 25, 2009, 12:49:58 PM »
Hello Ron.
My code, much more long...

Thanks ElpanovEvgeniy

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

#### It's Alive!

• Needs a day job
• Posts: 6923
• AKA Daniel
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #16 on: September 25, 2009, 12:54:04 PM »
My code is slightly long

Code: [Select]
`#pragma once#include <set>#include <vector>#include <algorithm>class CDPoint { public:  double x,y,z,w;  __forceinline CDPoint(void) : x(0.0),y(0.0),z(0.0),w(0.0){}  __forceinline CDPoint(double X,double Y, double Z,double dist)     : x(X),y(Y),z(Z),w(dist){}  __forceinline CDPoint(const AcGePoint3d &p,double dist)     : x(p.x),y(p.y),z(p.z),w(dist){}   static bool byZ (const CDPoint &pt1, const CDPoint &pt2) {    return (pt1.z > pt2.z);  }   double distanceTo(const CDPoint &pt) const  {    double dx = x - pt.x;    double dy = y - pt.y;    double dz = z - pt.z;    return sqrt(dx*dx + dy*dy + dz*dz);  }   double distanceTo(const AcGePoint3d &pt) const  {    double dx = x - pt.x;    double dy = y - pt.y;    double dz = z - pt.z;    return sqrt(dx*dx + dy*dy + dz*dz);  }   AcGePoint3d toPoint3d() const  {    return AcGePoint3d(x,y,z);  }  bool operator == (const CDPoint &pt) const{    return (w == pt.w);  }  bool operator < (const CDPoint &pt) const{    if(w == pt.w){ return ( z < pt.z); }    return ( w > pt.w);  }};typedef std::set<CDPoint> sDPoints;typedef std::vector<CDPoint> vDPoints;typedef std::vector<AcGeLine3d> vLines;inline static void addPoint(sDPoints &points, const CDPoint &p){  points.insert(p);}static void sortPoints(vDPoints &sPoints)  {    sort( sPoints.begin(), sPoints.end());  }  static void setPointDist(const AcGePoint3d &basePt, vDPoints &sPoints)  {    for(int i = 0; i < sPoints.size();i++)     {      sPoints[i].w = sPoints[i].distanceTo(basePt);    }  }  static int fillPoints(vDPoints &sPoints)  {    int cnt = 0;    AcDbDatabase *pDb = acdbHostApplicationServices()->workingDatabase();    AcDbBlockTableRecord *pRec;    if(acdbOpenAcDbObject((AcDbObject *&) pRec,        pDb->currentSpaceId(), AcDb::kForRead) == Acad::eOk)    {      AcDbBlockTableRecordIterator *pIter;      if(pRec->newIterator(pIter) == Acad::eOk) {        for(pIter->start(); !pIter->done(); pIter->step()) {          AcDbObjectId objId;          AcDbEntity *pEnt;          if(pIter->getEntity(pEnt, AcDb::kForRead) == Acad::eOk){            AcDbPoint *pPoint = AcDbPoint::cast(pEnt);            if(pPoint) {              CDPoint p(pPoint->position(),0);              sPoints.push_back(p);              cnt++;            }            pEnt->close();          }        }        delete pIter;      }      pRec->close();    }    return cnt;  }  static void ArxShortestPl_doit(void)  {    AcDbObjectId plid;    vDPoints sPoints;    vDPoints::const_iterator sIter;    vLines lineVec;    int cnt = fillPoints(sPoints);    sortPoints(sPoints);    if (cnt < 2)      return;    AcDbPolyline *pl = new AcDbPolyline(cnt);    AcGePoint3d basePt(0.0,0.0,0.0);    AcGePoint3d lastpt = basePt;    for(int i = 0 ; i < cnt ; i++)    {      unsigned int last = sPoints.size() -1;      setPointDist(basePt,sPoints);      sortPoints(sPoints);      lastpt = sPoints[last].toPoint3d();      pl->addVertexAt(pl->numVerts(),AcGePoint2d(lastpt.x,lastpt.y));      basePt = lastpt;      sPoints.pop_back();    }    pl->setClosed(Adesk::kTrue);    double dist,endparam;    pl->getEndParam(endparam);    pl->getDistAtParam(endparam,dist);    acutPrintf(_T("Length = %g"), dist);    AddEntityToDataBase(pl,plid);  }  static void    AddEntityToDataBase(AcDbEntity *pEnt, AcDbObjectId &pOutputId,                                          Adesk::UInt16 color = 7)   {    pOutputId = AcDbObjectId::kNull;    AcDbDatabase* pDb = acdbHostApplicationServices()->workingDatabase();    AcDbBlockTableRecordPointer pBTR(pDb->currentSpaceId(), AcDb::kForWrite);     if (pEnt && Acad::eOk == pBTR.openStatus())    {      pEnt->setDatabaseDefaults();      pEnt->setColorIndex(color);      pBTR->appendAcDbEntity(pOutputId, pEnt);      pEnt->close();    }  }`
« Last Edit: September 25, 2009, 01:36:07 PM by Daniel »

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1540
• Moscow (Russia)
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #17 on: September 25, 2009, 12:57:10 PM »
heres mine ... am I even close?

Salesman should return!

ps. For the list lst-b the result will be nearby 2500 mm.

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1540
• Moscow (Russia)
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #18 on: September 25, 2009, 01:01:28 PM »
> Daniel
It is a pity, I am not able to enjoy such code.
But result good!

#### Lee Mac

• Seagull
• Posts: 12195
• London, England
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #19 on: September 25, 2009, 01:02:24 PM »
Got the same result as Ron, but maybe with quicker code

Code: [Select]
`(defun mkPoly (lst / qsort rslt x)  (defun qsort (pt lst)    (vl-sort lst      (function (lambda (a b) (< (distance pt a) (distance pt b))))))  (setq rslt (list (car lst)))  (while (setq x (car (setq lst (qsort (car rslt) (cdr lst)))))    (setq rslt (cons x rslt)))  (make-lwpolyline rslt)  (princ))`

#### VovKa

• Swamp Rat
• Posts: 1087
• Ukraine
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #20 on: September 25, 2009, 01:02:54 PM »
i vote for the long code.
i think we have to bruteforce it. thus making factorial of (length lst) iterations.

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1540
• Moscow (Russia)
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #21 on: September 25, 2009, 01:06:48 PM »
i vote for the long code.
i think we have to bruteforce it. thus making factorial of (length lst) iterations.

Bruteforce any of the offered lists, some years will occupy!
This method is not interesting

#### It's Alive!

• Needs a day job
• Posts: 6923
• AKA Daniel
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #22 on: September 25, 2009, 01:13:05 PM »
I'm also getting the same result as Ron when I return the end point

#### ronjonp

• Needs a day job
• Posts: 6901
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #23 on: September 25, 2009, 01:22:12 PM »
Got the same result as Ron, but maybe with quicker code

Code: [Select]
`(defun mkPoly (lst / qsort rslt x)  (defun qsort (pt lst)    (vl-sort lst      (function (lambda (a b) (< (distance pt a) (distance pt b))))))  (setq rslt (list (car lst)))  (while (setq x (car (setq lst (qsort (car rslt) (cdr lst)))))    (setq rslt (cons x rslt)))  (make-lwpolyline rslt)  (princ))`

I like it Lee  ...that's how I'd write it now. I wrote that function about 2 years ago for an in-house routine  . It's funny how different the mind thinks after years of practice.

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

#### Lee Mac

• Seagull
• Posts: 12195
• London, England
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #24 on: September 25, 2009, 01:24:58 PM »
Thanks Ron

The penny suddenly dropped when I realised in my previous code that I was removing items in the list that I hadn't added to the result list - I was shortening the input list before it was sorted - bad idea...

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1540
• Moscow (Russia)
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #25 on: September 25, 2009, 01:38:15 PM »

#### VovKa

• Swamp Rat
• Posts: 1087
• Ukraine
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #26 on: September 25, 2009, 03:36:22 PM »
Lee, this task is not as simple as it appears. Evgeniy is not up to thowing easy tasks
try your function on both list-b and (reverse lst-b)

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1540
• Moscow (Russia)
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #27 on: September 26, 2009, 05:42:36 AM »
Has come to give time the first help...
Each self-crossing, increases length of a contour!

#### Lee Mac

• Seagull
• Posts: 12195
• London, England
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #28 on: September 26, 2009, 08:41:57 AM »
Lee, this task is not as simple as it appears. Evgeniy is not up to thowing easy tasks
try your function on both list-b and (reverse lst-b)

Good spot Vovka -

this solves the inconsistency, but its still not the shortest...

Code: [Select]
`(defun mkPoly (lst / qsort mPt rslt x)  (defun qsort (pt lst)    (vl-sort lst      (function (lambda (a b) (< (distance pt a) (distance pt b))))))  (setq lst (cons mPt (qsort (setq mPt (apply 'mapcar (cons 'min lst)))                             (vl-remove mPt lst))))    (setq rslt (list mPt))  (while (setq x (car (setq lst (qsort (car rslt) (cdr lst)))))    (setq rslt (cons x rslt)))  (make-lwpolyline rslt)  (princ))`
« Last Edit: September 26, 2009, 08:51:44 AM by Lee Mac »

#### Lee Mac

• Seagull
• Posts: 12195
• London, England
##### Re: (Challenge) To draw the shortest lwpolyline
« Reply #29 on: September 26, 2009, 09:48:41 AM »
Looking at your link, I tried the inversion method - I don't get a better result though - if anything, worse...

Code: [Select]
`(defun mkPoly (lst / x sect lst nlst e nlen end)  (defun SubLst (lst i j / k)    (setq k -1)    (or j (setq j (length lst)))    (vl-remove-if-not      (function        (lambda (x)          (<= i (setq k (1+ k)) (+ i (1- j))))) lst))  (setq x -1)  (while (and (setq sect (SubLst lst (setq x (1+ x)) 4))              (= 4 (length sect)))    (setq nlst (append (if (zerop x) '( ) (SubLst lst 0 x))                       (reverse sect)                       (if (= (length lst) (+ x 4)) '( ) (SubLst lst (+ x 4) nil))))    (setq e (make-lwpolyline nlst))    (setq nLen (vlax-curve-getDistatParam e (vlax-curve-getEndParam e)))    (entdel e)    (if len      (if (< nlen len)        (setq len nlen lst nlst))      (setq len nlen)))  (setq e (make-lwpolyline lst))  (Princ (strcat "\n length lwpolyline "                (rtos (vlax-curve-getDistAtParam e (vlax-curve-getEndParam e)) 2 4)" mm."))  (princ))`