Author Topic: ={ Challenge }=NP-hard problem= moving trajectory  (Read 4513 times)

0 Members and 1 Guest are viewing this topic.

Q1241274614

  • Guest
={ Challenge }=NP-hard problem= moving trajectory
« on: March 15, 2014, 11:39:09 AM »
1- object B always in object A;
2- object B does not rotate;
3- objects B moving , along the object A boundary;
4- B-Ymin :The lowest point;
5-  Calculation of the lowest point of the trajectory:Results the trajectory.


« Last Edit: March 16, 2014, 04:05:18 AM by Q1241274614 »

chlh_jd

  • Guest
Re: ==={ Challenge }=== moving trajectory
« Reply #1 on: March 15, 2014, 12:17:02 PM »
Cutting problem is NP-hard problem, is a very large program, it is recommended to use third-party software to complete . Enjoy !

snownut2

  • Swamp Rat
  • Posts: 971
  • Bricscad 22 Ultimate
Re: ==={ Challenge }=== moving trajectory
« Reply #2 on: March 15, 2014, 12:25:46 PM »
help!help!help! whats next.

Q1241274614

  • Guest
Re: ==={ Challenge }=== moving trajectory
« Reply #3 on: March 16, 2014, 04:02:47 AM »
Friend, don't you have any means?

Q1241274614

  • Guest
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #4 on: March 17, 2014, 11:54:49 AM »
Friend, don't you have any means?

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #5 on: March 17, 2014, 05:57:07 PM »
What have you tried ?
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

Q1241274614

  • Guest
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #6 on: March 20, 2014, 04:37:09 AM »
To complete a simple convex polygon!



Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #7 on: March 20, 2014, 04:44:45 AM »

Great.
What does the code look like ?
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

ribarm

  • Gator
  • Posts: 3180
  • Marko Ribar, architect
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #8 on: March 20, 2014, 07:29:51 AM »
We don't see on GIF you are actually drawing these convex polygons... Can you show us complete animation?
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Gator
  • Posts: 3180
  • Marko Ribar, architect
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #9 on: March 20, 2014, 04:15:48 PM »
It may work with convex polygons, but it may not, you have to test it... And it's only scatter, trajectory polyline you can draw manually according to desired point orientation on smaller polygons after scatter... Better something than nothing - so for start it's not bad...

Code - Auto/Visual Lisp: [Select]
  1. (defun c:scatterpolygonpolygon ( / *error* unit rlw ListClockwise-p osm pea msp polmin polmax cmin cmax regmin regmax ptlst k pt intpt intpar par ptmin poll ptt ptt1 ptt2 pttpar parptl ptl ptll pollptlst prevpt prevprevpt nextpt nextnextpt ptper vec ptn prevptpol nextptpol vecp vecn ptnn )
  2.  
  3.   (setq osm (getvar 'osmode))
  4.   (setq pea (getvar 'peditaccept))
  5.   (setvar 'osmode 0)
  6.   (setvar 'peditaccept 1)
  7.  
  8.   (defun *error* ( msg )
  9.     (if osm (setvar 'osmode osm))
  10.     (if pea (setvar 'peditaccept pea))
  11.     (if msg (prompt msg))
  12.     (princ)
  13.   )
  14.  
  15.   (defun unit ( v )
  16.     (mapcar '(lambda ( x ) (/ x (distance '(0.0 0.0 0.0) v))) v)
  17.   )
  18.  
  19.   (defun rlw ( LW / E X1 X2 X3 X4 X5 X6 )
  20.     ;; by ElpanovEvgeniy
  21.     ;; reverse lwpolyline
  22.     (if (= (cdr (assoc 0 (setq e (entget lw)))) "LWPOLYLINE")
  23.       (progn (foreach a1 e
  24.                (cond ((= (car a1) 10) (setq x2 (cons a1 x2)))
  25.                      ((= (car a1) 40) (setq x4 (cons (cons 41 (cdr a1)) x4)))
  26.                      ((= (car a1) 41) (setq x3 (cons (cons 40 (cdr a1)) x3)))
  27.                      ((= (car a1) 42) (setq x5 (cons (cons 42 (- (cdr a1))) x5)))
  28.                      ((= (car a1) 210) (setq x6 (cons a1 x6)))
  29.                      (t (setq x1 (cons a1 x1)))
  30.                )
  31.              )
  32.              (entmod (append (reverse x1)
  33.                              (append (apply (function append)
  34.                                             (apply (function mapcar)
  35.                                                    (cons 'list
  36.                                                          (list x2
  37.                                                                (cdr (reverse (cons (car x3) (reverse x3))))
  38.                                                                (cdr (reverse (cons (car x4) (reverse x4))))
  39.                                                                (cdr (reverse (cons (car x5) (reverse x5))))
  40.                                                          )
  41.                                                    )
  42.                                             )
  43.                                      )
  44.                                      x6
  45.                              )
  46.                      )
  47.              )
  48.              (entupd lw)
  49.       )
  50.     )
  51.   )
  52.  
  53.   (defun ListClockwise-p ( lst / z vlst )
  54.     (vl-catch-all-apply 'minusp
  55.       (list
  56.         (if
  57.           (not
  58.             (equal 0.0
  59.               (setq z
  60.                 (apply '+
  61.                   (mapcar
  62.                     (function
  63.                       (lambda (u v)
  64.                         (- (* (car  u) (cadr  v)) (* (car  v) (cadr  u)))
  65.                       )
  66.                     )
  67.                     (setq vlst
  68.                       (mapcar
  69.                         (function
  70.                           (lambda (a b) (mapcar '- b a))
  71.                         )
  72.                         (mapcar (function (lambda (x) (car lst))) lst)
  73.                         (cdr (reverse (cons (car lst) (reverse lst))))
  74.                       )
  75.                     )
  76.                     (cdr (reverse (cons (car vlst) (reverse vlst))))
  77.                   )
  78.                 )
  79.               ) 1e-6
  80.             )
  81.           )
  82.           z
  83.           (progn
  84.             (prompt "\n\nChecked vectors are colinear - unable to determine clockwise-p of list")
  85.             nil
  86.           )
  87.         )
  88.       )
  89.     )
  90.   )  
  91.  
  92.   (setq polmin (car (entsel "\nPick smaller polygon for scattering it inside bigger polygon - LWPOLYLINE")))
  93.   (if (not (eq (cdr (assoc 0 (entget polmin))) "LWPOLYLINE"))
  94.     (progn
  95.       (alert "Picked entity isn't LWPOLYLINE, quitting... Restart routine and pick correct entity...")
  96.       (exit)
  97.     )
  98.   )
  99.   (if (not (eq (logand (cdr (assoc 70 (entget polmin))) 1) 1))
  100.     (progn
  101.       (alert "Picked entity isn't CLOSED polygon, quitting... Restart routine and pick correct entity...")
  102.       (exit)
  103.     )
  104.   )
  105.   (if (not (vl-every '(lambda ( x ) (eq (cdr x) 0.0)) (acet-list-m-assoc 42 (entget polmin))))
  106.     (progn
  107.       (alert "Picked entity has ARCED segment(s), quitting... Restart routine and pick correct entity...")
  108.       (exit)
  109.     )
  110.   )
  111.   (setq polmax (car (entsel "\nPick bigger polygon around which vertices routine scatters smaller polygon - LWPOLYLINE")))
  112.   (if (not (eq (cdr (assoc 0 (entget polmax))) "LWPOLYLINE"))
  113.     (progn
  114.       (alert "Picked entity isn't LWPOLYLINE, quitting... Restart routine and pick correct entity...")
  115.       (exit)
  116.     )
  117.   )
  118.   (if (not (eq (logand (cdr (assoc 70 (entget polmax))) 1) 1))
  119.     (progn
  120.       (alert "Picked entity isn't CLOSED polygon, quitting... Restart routine and pick correct entity...")
  121.       (exit)
  122.     )
  123.   )
  124.   (if (not (vl-every '(lambda ( x ) (eq (cdr x) 0.0)) (acet-list-m-assoc 42 (entget polmax))))
  125.     (progn
  126.       (alert "Picked entity has ARCED segment(s), quitting... Restart routine and pick correct entity...")
  127.       (exit)
  128.     )
  129.   )
  130.   (setq cmin (vlax-safearray->list (vlax-variant-value (vla-get-centroid (setq regmin (car (vlax-invoke msp 'addregion (list (vlax-ename->vla-object polmin)))))))))
  131.   (setq cmax (vlax-safearray->list (vlax-variant-value (vla-get-centroid (setq regmax (car (vlax-invoke msp 'addregion (list (vlax-ename->vla-object polmax)))))))))
  132.   (command "_.explode" (vlax-vla-object->ename regmin))
  133.   (while (> (getvar 'cmdactive) 0) (command ""))
  134.   (command "_.pedit" "_M" "_P" "" "_J" "")
  135.   (while (> (getvar 'cmdactive) 0) (command ""))
  136.   (entdel polmin)
  137.   (setq polmin (entlast))
  138.   (command "_.explode" (vlax-vla-object->ename regmax))
  139.   (while (> (getvar 'cmdactive) 0) (command ""))
  140.   (command "_.pedit" "_M" "_P" "" "_J" "")
  141.   (while (> (getvar 'cmdactive) 0) (command ""))
  142.   (entdel polmax)
  143.   (setq polmax (entlast))
  144.   (if (ListClockwise-p (mapcar 'cdr (acet-list-m-assoc 10 (entget polmin)))) (rlw polmin))
  145.   (if (ListClockwise-p (mapcar 'cdr (acet-list-m-assoc 10 (entget polmax)))) (rlw polmax))
  146.   (command "_.move" polmin "" cmin cmax)
  147.   (setq ptlst (mapcar 'cdr (acet-list-m-assoc 10 (entget polmax))))
  148.   (setq k -1)
  149.   (repeat (length ptlst)
  150.     (setq pt (nth (setq k (1+ k)) ptlst))
  151.     (command "_.LINE" cmax pt "")
  152.     (setq intpt (vlax-invoke (vlax-ename->vla-object (entlast)) 'intersectwith (vlax-ename->vla-object polmin) acextendnone))
  153.     (entdel (entlast))
  154.     (setq intpar (vlax-curve-getparamatpoint polmin intpt))
  155.     (setq par (if (< (- intpar (fix intpar)) 0.5) (fix intpar) (1+ (fix intpar))))
  156.     (setq ptmin (vlax-curve-getpointatparam polmin par))
  157.     (command "_.COPY" polmin "" ptmin pt)
  158.     (setq poll (entlast))
  159.     (if (not (equal (list (car pt) (cadr pt) 0.0) (setq ptt (vlax-invoke (vlax-ename->vla-object polmax) 'intersectwith (vlax-ename->vla-object poll) acextendnone)) 1e-3))
  160.       (progn
  161.         (if (eq (length ptt) 6) (setq ptt (list (list (nth 0 ptt) (nth 1 ptt) (nth 2 ptt)) (list (nth 3 ptt) (nth 4 ptt) (nth 5 ptt)))))
  162.         (if (eq (length ptt) 9) (setq ptt (list (list (nth 0 ptt) (nth 1 ptt) (nth 2 ptt)) (list (nth 3 ptt) (nth 4 ptt) (nth 5 ptt)) (list (nth 6 ptt) (nth 7 ptt) (nth 8 ptt)))))
  163.         (setq ptt (acet-list-remove-duplicates ptt 1e-3))
  164.         (if (eq (length ptt) 2)
  165.           (progn
  166.             (if (equal (list (car pt) (cadr pt) 0.0) (car ptt) 1e-3) (setq ptt (cadr ptt)) (setq ptt (car ptt)))
  167.             (setq pttpar (vlax-curve-getparamatpoint poll ptt))
  168.             (setq parptl (if (< (- pttpar (fix pttpar)) 0.5) (fix pttpar) (1+ (fix pttpar))))
  169.             (setq ptl (vlax-curve-getpointatparam poll parptl))
  170.             (setq ptl (list (car ptl) (cadr ptl)))
  171.             (setq pollptlst (mapcar 'cdr (acet-list-m-assoc 10 (entget poll))))
  172.             (setq prevpt (if (equal pt (car pollptlst) 1e-3) (last pollptlst) (cadr (member pt (reverse pollptlst)))))
  173.             (setq nextpt (if (equal pt (last pollptlst) 1e-3) (car pollptlst) (cadr (member pt pollptlst))))
  174.             (setq prevprevpt (if (equal prevpt (car pollptlst) 1e-3) (last pollptlst) (cadr (member prevpt (reverse pollptlst)))))
  175.             (setq nextnextpt (if (equal nextpt (last pollptlst) 1e-3) (car pollptlst) (cadr (member nextpt pollptlst))))
  176.             (if (or (equal prevpt ptl 1e-3) (equal prevprevpt ptl 1e-3)) (setq ptl prevpt))
  177.             (if (or (equal nextpt ptl 1e-3) (equal nextnextpt ptl 1e-3)) (setq ptl nextpt))
  178.             (setq ptper (vlax-curve-getclosestpointto polmax ptl))
  179.             (setq ptper (list (car ptper) (cadr ptper)))
  180.             (setq vec (mapcar '- pt ptper))
  181.             (setq ptn (mapcar '+ pt (mapcar '- ptper ptl)))
  182.             (command "_.move" poll "" ptl ptper)
  183.             (setq prevptpol (if (equal pt (car ptlst) 1e-3) (last ptlst) (cadr (member pt (reverse ptlst)))))
  184.             (setq nextptpol (if (equal pt (last ptlst) 1e-3) (car ptlst) (cadr (member pt ptlst))))
  185.             (setq vecp (mapcar '- pt prevptpol))
  186.             (setq vecn (mapcar '- pt nextptpol))
  187.             (if (equal (unit vec) (unit vecp) 1e-3)
  188.               (progn
  189.                 (setq ptnn (inters ptn (mapcar '+ ptn vec) pt nextptpol nil))
  190.                 (command "_.move" poll "" ptn ptnn)
  191.               )
  192.               (progn
  193.                 (setq ptnn (inters ptn (mapcar '+ ptn vec) pt prevptpol nil))
  194.                 (command "_.move" poll "" ptn ptnn)
  195.               )
  196.             )
  197.           )
  198.           (progn
  199.             (foreach p ptlst
  200.               (if (vl-member-if '(lambda ( x ) (equal x (list (car p) (cadr p) 0.0) 1e-3)) ptt)
  201.                 (setq ptt (vl-remove-if '(lambda ( x ) (equal x (list (car p) (cadr p) 0.0) 1e-3)) ptt))
  202.               )
  203.             )
  204.             (setq ptt1 (car ptt))
  205.             (setq ptt2 (cadr ptt))
  206.  
  207.             (setq pttpar (vlax-curve-getparamatpoint poll ptt1))
  208.             (setq parptl (if (< (- pttpar (fix pttpar)) 0.5) (fix pttpar) (1+ (fix pttpar))))
  209.             (setq ptl (vlax-curve-getpointatparam poll parptl))
  210.             (setq ptl (list (car ptl) (cadr ptl)))
  211.             (setq pollptlst (mapcar 'cdr (acet-list-m-assoc 10 (entget poll))))
  212.             (setq prevpt (if (equal pt (car pollptlst) 1e-3) (last pollptlst) (cadr (member pt (reverse pollptlst)))))
  213.             (setq nextpt (if (equal pt (last pollptlst) 1e-3) (car pollptlst) (cadr (member pt pollptlst))))
  214.             (setq prevprevpt (if (equal prevpt (car pollptlst) 1e-3) (last pollptlst) (cadr (member prevpt (reverse pollptlst)))))
  215.             (setq nextnextpt (if (equal nextpt (last pollptlst) 1e-3) (car pollptlst) (cadr (member nextpt pollptlst))))
  216.             (if (or (equal prevpt ptl 1e-3) (equal prevprevpt ptl 1e-3)) (setq ptl prevpt))
  217.             (if (or (equal nextpt ptl 1e-3) (equal nextnextpt ptl 1e-3)) (setq ptl nextpt))
  218.             (setq ptper (vlax-curve-getclosestpointto polmax ptl))
  219.             (setq ptper (list (car ptper) (cadr ptper)))
  220.             (setq vec (mapcar '- pt ptper))
  221.  
  222.             (setq pttpar (vlax-curve-getparamatpoint poll ptt2))
  223.             (setq parptl (if (< (- pttpar (fix pttpar)) 0.5) (fix pttpar) (1+ (fix pttpar))))
  224.             (setq ptll (vlax-curve-getpointatparam poll parptl))
  225.             (setq ptll (list (car ptll) (cadr ptll)))
  226.             (setq pollptlst (mapcar 'cdr (acet-list-m-assoc 10 (entget poll))))
  227.             (setq prevpt (if (equal pt (car pollptlst) 1e-3) (last pollptlst) (cadr (member pt (reverse pollptlst)))))
  228.             (setq nextpt (if (equal pt (last pollptlst) 1e-3) (car pollptlst) (cadr (member pt pollptlst))))
  229.             (setq prevprevpt (if (equal prevpt (car pollptlst) 1e-3) (last pollptlst) (cadr (member prevpt (reverse pollptlst)))))
  230.             (setq nextnextpt (if (equal nextpt (last pollptlst) 1e-3) (car pollptlst) (cadr (member nextpt pollptlst))))
  231.             (if (or (equal prevpt ptll 1e-3) (equal prevprevpt ptll 1e-3)) (setq ptll prevpt))
  232.             (if (or (equal nextpt ptll 1e-3) (equal nextnextpt ptll 1e-3)) (setq ptll nextpt))
  233.  
  234.             (setq ptn (mapcar '+ ptll (mapcar '- ptper ptl)))
  235.             (command "_.move" poll "" ptl ptper)
  236.             (setq prevptpol (if (equal pt (car ptlst) 1e-3) (last ptlst) (cadr (member pt (reverse ptlst)))))
  237.             (setq nextptpol (if (equal pt (last ptlst) 1e-3) (car ptlst) (cadr (member pt ptlst))))
  238.             (setq vecp (mapcar '- pt prevptpol))
  239.             (setq vecn (mapcar '- pt nextptpol))
  240.             (if (equal (unit vec) (unit vecp) 1e-3)
  241.               (progn
  242.                 (setq ptnn (inters ptn (mapcar '+ ptn vec) pt nextptpol nil))
  243.                 (command "_.move" poll "" ptn ptnn)
  244.               )
  245.               (progn
  246.                 (setq ptnn (inters ptn (mapcar '+ ptn vec) pt prevptpol nil))
  247.                 (command "_.move" poll "" ptn ptnn)
  248.               )
  249.             )
  250.           )
  251.         )
  252.       )
  253.     )
  254.   )
  255.  
  256.   (*error* nil)
  257.   (princ)
  258. )
  259.  
  260. (defun c:spp nil (c:scatterpolygonpolygon))
  261. (prompt "\nInvoke with 'SPP' command")
  262.  
« Last Edit: March 21, 2014, 08:14:44 AM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Gator
  • Posts: 3180
  • Marko Ribar, architect
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #10 on: March 21, 2014, 03:53:49 AM »
Fixed some minor bugs, code updated... It should scatter all small polygons along vertices of big polygon, but result can be also undesired - it depends from case to case... Make sure you draw convex polygons... Waiting for your reply Q1241274614...

Regards, M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Q1241274614

  • Guest
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #11 on: March 21, 2014, 04:23:46 AM »
The best results are arbitrary structure, concave edge shape is also possible.


Do not know how to copy your files, because there are a lot of digital.

thank!

ribarm

  • Gator
  • Posts: 3180
  • Marko Ribar, architect
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #12 on: March 21, 2014, 04:32:54 AM »
The best results are arbitrary structure, concave edge shape is also possible.

I designed this to work with convex polygons... Maybe some case with concave can actually succeed, but I didn't try...

Do not know how to copy your files, because there are a lot of digital.

You can use [Select] button beside code heading to quickly select code, then use ctrl+c (copy), open notepad or some other text editor and use ctrl+v (paste), and then save file as SPP.lsp... If you don't succeed I'll upload my version of *.lsp, so you can download it...

thank!

You're welcome...
« Last Edit: March 21, 2014, 08:15:21 AM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Q1241274614

  • Guest
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #13 on: March 21, 2014, 05:52:39 AM »
thank ribarm !
At night I try.


ribarm

  • Gator
  • Posts: 3180
  • Marko Ribar, architect
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #14 on: March 21, 2014, 07:17:45 AM »
A little mistake, now fixed, try download now... Thanks for your patience, M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: ={ Challenge }=NP-hard problem= moving trajectory
« Reply #15 on: March 31, 2014, 01:11:35 PM »
help!!!!!!!!!!1

Q1241274614,
It would be really helpful to us if you made an effort to provide enough information so that your posts made sense.

I hope that message can be translated correctly to express my request.

kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.