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

0 Members and 1 Guest are viewing this topic.

ronjonp

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

Thanks ElpanovEvgeniy  :oops:

Windows 10 x64 - AutoCAD /C3D 2019

Custom Build PC

nullptr

  • BricsCAD
  • Needs a day job
  • Posts: 6820
  • 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: 1535
  • 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.
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1535
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #18 on: September 25, 2009, 01:01:28 PM »
> Daniel
Your program on arx!
It is a pity, I am not able to enjoy such code.
 But result good!
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

Lee Mac

  • Seagull
  • Posts: 12109
  • 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: 1045
  • 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: 1535
  • 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
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

nullptr

  • BricsCAD
  • Needs a day job
  • Posts: 6820
  • 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: 6802
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  :-o. It's funny how different the mind thinks after years of practice.

Windows 10 x64 - AutoCAD /C3D 2019

Custom Build PC

Lee Mac

  • Seagull
  • Posts: 12109
  • 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...   :wink:

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1535
  • Moscow (Russia)
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

VovKa

  • Swamp Rat
  • Posts: 1045
  • 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: 1535
  • 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!

蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

Lee Mac

  • Seagull
  • Posts: 12109
  • 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: 12109
  • 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))