### 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
##### 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)

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

#### 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)

#### 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)

#### 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 »
Marko Ribar, d.i.a. (graduated engineer of architecture)

#### 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,