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

0 Members and 1 Guest are viewing this topic.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
(Challenge) To draw the shortest lwpolyline
« on: September 25, 2009, 09:22:35 AM »
Hello!
I wish to offer you the next competition.
It is given: the list of points
It is necessary: to draw lwpolyline passing through all points.

I think, it is necessary to pay attention on length lwpolyline.
Two lists of points are attached.
Stay home. Stay safe. Save lives.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #1 on: September 25, 2009, 10:05:24 AM »
Explanation
Stay home. Stay safe. Save lives.

VovKa

  • Swamp Rat
  • Posts: 1235
  • Ukraine
Re: (Challenge) To draw the shortest lwpolyline
« Reply #2 on: September 25, 2009, 10:12:23 AM »
seems that Evgeniy is trying to spoil other people's friday night :)

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #3 on: September 25, 2009, 10:14:34 AM »
seems that Evgeniy is trying to spoil other people's friday night :)

On the native land of a forum, now morning!
Stay home. Stay safe. Save lives.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10387
Re: (Challenge) To draw the shortest lwpolyline
« Reply #4 on: September 25, 2009, 11:13:42 AM »
Oh, The Traveling Salesman Problem.
Wish I had time today but a deadline calls.  :?
I've reached the age where the happy hour is a nap. ()
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #5 on: September 25, 2009, 11:39:16 AM »
Well, I do not put deadline.

Enjoy the task! :)
Stay home. Stay safe. Save lives.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #6 on: September 25, 2009, 11:59:40 AM »
I see, it is necessary to lay out a simple code, I am fast it I will make!
Any code, will be better...
Stay home. Stay safe. Save lives.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #7 on: September 25, 2009, 12:15:55 PM »
Code: [Select]
(defun make-lwpolyline(l / e)
 ;;(make-lwpolyline lst)
 (setq e (entmakex (append (list '(0 . "LWPOLYLINE")
                                 '(100 . "AcDbEntity")
                                 '(67 . 0)
                                 '(410 . "Model")
                                 '(8 . "Kant")
                                 '(62 . 3)
                                 '(100 . "AcDbPolyline")
                                 (cons 90 (length l))
                                 '(70 . 1)
                           ) ;_  list
                           (mapcar (function (lambda (a) (cons 10 a))) l)
                   ) ;_  append
         ) ;_  entmakex
 ) ;_  setq
 (Princ (strcat "\n length lwpolyline "
                (rtos (vlax-curve-getDistAtParam e (vlax-curve-getEndParam e)) 2 4)
                " mm."
        ) ;_  strcat
 ) ;_  Princ
 (Princ)
) ;_  defun
Stay home. Stay safe. Save lives.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #8 on: September 25, 2009, 12:38:26 PM »
The interesting approach, for the chaotic list, results is better than the starting list.
Stay home. Stay safe. Save lives.

ronjonp

  • Needs a day job
  • Posts: 7138
Re: (Challenge) To draw the shortest lwpolyline
« Reply #9 on: September 25, 2009, 12:41:12 PM »
Here's mine:
Code: [Select]
(defun rjp-sortpt2pt (pt lst / tmp newlst)
  (defun dsort (pt lst / d1 d2)
    (vl-sort lst (function (lambda (d1 d2) (< (distance pt d1) (distance pt d2)))))
  )
  (setq tmp (dsort pt lst))
  (repeat (length lst)
    (setq tmp (dsort (car tmp) tmp)
 newlst (cons (car tmp) newlst)
 tmp (vl-remove (car tmp) tmp)
    )
  )
  (reverse newlst)
)
(make-lwpolyline (rjp-sortpt2pt (car lst-a) lst-a))
;;3908.169
(make-lwpolyline (rjp-sortpt2pt (car lst-b) lst-b))
;;3206.567
« Last Edit: September 26, 2009, 11:31:54 AM by ronjonp »

Windows 10 x64 - AutoCAD /C3D 2020

Custom Build PC

Lee Mac

  • Seagull
  • Posts: 12379
  • London, England
Re: (Challenge) To draw the shortest lwpolyline
« Reply #10 on: September 25, 2009, 12:46:30 PM »
Nice one Ron,

I tried a different approach, but I think mine misses a few points  :oops:

Code: [Select]
(defun mkPoly (lst / rslt tmp lst ply)
 
  (setq rslt (list (car lst)))
  (while (setq lst (cdr lst))
    (setq tmp (car rslt))
    (setq rslt
      (cons
        (car (vl-sort lst
               (function
                 (lambda (a b)
                   (< (distance tmp a)
                        (distance tmp b)))))) rslt)))

  (setq ply
    (entmakex
      (append (list (cons 0 "LWPOLYLINE")
                    (cons 100 "AcDbEntity")
                    (cons 100 "AcDbPolyline")
                    (cons 90 (length rslt))
                    (cons 70 1))
              (mapcar (function (lambda (x) (cons 10 x))) rslt))))

  (princ (strcat "\nPolyline Length: " (rtos (vlax-curve-getDistatParam ply
                                               (vlax-curve-getEndParam ply)) 2 4) " mm."))
  (princ))

Code: [Select]
lst-a  Polyline Length: 968.1675 mm.

lst-b Polyline Length: 1019.6264 mm.

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: (Challenge) To draw the shortest lwpolyline
« Reply #11 on: September 25, 2009, 12:48:34 PM »
Hello Ron.
I liked your code!
My code, much more long...
Stay home. Stay safe. Save lives.

It's Alive!

  • BricsCAD
  • Needs a day job
  • Posts: 7028
  • AKA Daniel
Re: (Challenge) To draw the shortest lwpolyline
« Reply #12 on: September 25, 2009, 12:49:29 PM »
heres mine ... am I even close?


ronjonp

  • Needs a day job
  • Posts: 7138
Re: (Challenge) To draw the shortest lwpolyline
« Reply #13 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 2020

Custom Build PC

It's Alive!

  • BricsCAD
  • Needs a day job
  • Posts: 7028
  • AKA Daniel
Re: (Challenge) To draw the shortest lwpolyline
« Reply #14 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 »