### Author Topic: [Challenge] Point set inscribed the max area triangle  (Read 14652 times)

0 Members and 1 Guest are viewing this topic.

#### chlh_jd

• Guest
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #15 on: March 16, 2011, 07:19:59 AM »
hi , all
hi , Evgeniy
about pt in or at the triangle , I tested result is

use cal number of intersections method is the fastest , is it a wrong test ?
Code: [Select]
`(defun EE:pitp (p l)  ;; check is a point inside the triangle.  ;; by ElpanovEvgeniy  (if (< (sin (- (angle (last l) p) (angle (last l) (car l)))) -1e-6      )    (vl-every      (function (lambda (a b) (< (sin (- (angle a p) (angle a b))) -1e-6))      )      l      (cdr l)    )    (vl-every      (function (lambda (a b) (> (sin (- (angle a p) (angle a b))) 1e-6))      )      l      (cdr l)    )  ));;;number of intersection;;;fastest(defun ss-pitp (p l)  ;;check point inside triangle .  ;;by GSLS(SS)  ((lambda (a b c)     (eq (+ (length (inters p a b c nil))    (length (inters p b a c nil))    (length (inters p c a b nil)) ) 9     )   )    (car l)    (cadr l)    (caddr l)  ));;;with the same direction method(defun ss-pitp0 (p l / foo)  ;;check point inside triangle .  ;;by GSLS(SS)  (defun foo (a b c p / ac ab ap)    (setq ac (mapcar '- c a)   ab (mapcar '- b a)   ap (mapcar '- p a)    )    (>= (vxv (v^v ab ac) (v^v ab ap)) 0.0)  )  ((lambda (a b c)     (and (foo a b c p) (foo b c a p) (foo c a b p))   )    (car l)    (cadr l)    (caddr l)  )  );;;with the same direction method;;;by trans(defun ss-pitp1 (p l)  ;;check point inside triangle .  ;;by GSLS(SS)  ((lambda (a b c)     (and (<= (* (car (trans (mapcar '- p a) 0 (mapcar '- b a)))        (car (trans (mapcar '- p a) 0 (mapcar '- c a)))     )     0 ) (<= (* (car (trans (mapcar '- p b) 0 (mapcar '- a b)))        (car (trans (mapcar '- p b) 0 (mapcar '- c b)))     )     0 )     )   )    (car l)    (cadr l)    (caddr l)  ))`

#### chlh_jd

• Guest
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #16 on: March 16, 2011, 07:22:21 AM »
forget func .
Code: [Select]
`;;; gile;;; vxv returns the dot product of 2 vectors;;; dot product(defun vxv (v1 v2)  (apply    '+    (mapcar      '*      v1      v2    )  ));;; gile ;;; cross product (defun v^v (v1 v2)  (list (- (* (cadr v1) (caddr v2)) (* (caddr v1) (cadr v2))) (- (* (caddr v1) (car v2)) (* (car v1) (caddr v2))) (- (* (car v1) (cadr v2)) (* (cadr v1) (car v2)))  )  )`

#### chlh_jd

• Guest
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #17 on: March 16, 2011, 08:38:48 AM »
to cal area of triangle ,
Uses conventional formula, but slower than Heron Formula.
is it no compile reason or the codes written to bad ?
Code: [Select]
`(defun ss-aat (p1 p2 p3)  ;;area triangle  ;;Uses conventional formula, but slower than Heron Formula.  (* 0.5     (sqrt       (apply (function +)      (mapcar (function (lambda (a b c)  (expt (- (+     (* (car a) (cadr b))     (* (car b) (cadr c))     (* (car c) (cadr a))   )   (+     (* (car a) (cadr c))     (* (car b) (cadr a))     (* (car c) (cadr b))   ) ) 2.  ) )      )      (list p1 (cdr p1) (list (caddr p1) (car p1)))      (list p2 (cdr p2) (list (caddr p2) (car p2)))      (list p3 (cdr p3) (list (caddr p3) (car p3)))      )       )     )  ))`

#### Stefan

• Bull Frog
• Posts: 319
• The most I miss IRL is the Undo button
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #18 on: March 16, 2011, 08:47:19 AM »
Area of triangle

Code: [Select]
`(defun ph:area (p1 p2 p3)  (* 0.5     (abs (+     (* (cadr p1) (- (car p2) (car p3)))     (* (cadr p2) (- (car p3) (car p1)))     (* (cadr p3) (- (car p1) (car p2)))     )   )     )  )`

#### alanjt

• Needs a day job
• Posts: 5352
• Standby for witty remark...
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #19 on: March 16, 2011, 08:53:02 AM »
Area of triangle

Code: [Select]
`(defun ph:area (p1 p2 p3)  (* 0.5     (abs (+    (* (cadr p1) (- (car p2) (car p3)))    (* (cadr p2) (- (car p3) (car p1)))    (* (cadr p3) (- (car p1) (car p2)))    )  )     )  )`
http://www.theswamp.org/index.php?topic=37455.msg424735#msg424735
Civil 3D 2019 ~ Windohz 7 64bit
Dropbox

#### Lee Mac

• Seagull
• Posts: 12913
• London, England
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #20 on: March 16, 2011, 09:17:14 AM »
Another...

Code: [Select]
`(defun LM:TriangleArea ( p1 p2 p3 )  (* 0.5 (distance p1 p2) (distance p2 p3) (abs (sin (- (angle p2 p1) (angle p2 p3))))))`

#### chlh_jd

• Guest
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #21 on: March 16, 2011, 09:21:57 AM »
hi All, to cal area of 3d points triangle, please test with it
Code: [Select]
`(ss-aat '(1 2 0) '(4 4 3) '(5 6 0))(ss-aat '(1 2 0) '(2 4 3) '(3 6 0))`
« Last Edit: March 16, 2011, 09:25:39 AM by chlh_jd »

#### Lee Mac

• Seagull
• Posts: 12913
• London, England
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #22 on: March 16, 2011, 09:23:18 AM »
hi All, to cal area of 3d points triangle, please test with it
Code: [Select]
`(ss-aat '(1 2 0) '(4 4 3) '(5 6 0))`

Oh yes - I would note that mine was for 2D purposes....

For 3D:

Code: [Select]
`(defun LM:TriangleArea ( p1 p2 p3 )  ( (lambda ( n ) (* 0.5 (sqrt (apply '+ (mapcar '* n n)))))    (v^v (mapcar '- p2 p1) (mapcar '- p3 p1))  ))(defun v^v ( u v )  (list    (- (* (cadr u) (caddr v)) (* (cadr v) (caddr u)))    (- (* (car  v) (caddr u)) (* (car  u) (caddr v)))    (- (* (car  u) (cadr  v)) (* (car  v) (cadr  u)))  ))`
« Last Edit: March 16, 2011, 09:28:44 AM by Lee Mac »

#### alanjt

• Needs a day job
• Posts: 5352
• Standby for witty remark...
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #23 on: March 16, 2011, 09:25:29 AM »
hi All, to cal area of 3d points triangle, please test with it
Code: [Select]
`(ss-aat '(1 2 0) '(4 4 3) '(5 6 0))`

Oh yes - I would note that mine was for 2D purposes....
Ditto.
Civil 3D 2019 ~ Windohz 7 64bit
Dropbox

#### chlh_jd

• Guest
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #24 on: March 16, 2011, 09:45:25 AM »
Point to judge whether in atriangle and the area of ​​the triangle  has a reasonable calculation function ,
And, ElpanovEvgeniy often the corret routine , however the overall complexity of the algorithm is O(n^3),
is it possible to let down ?

#### chlh_jd

• Guest
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #25 on: March 16, 2011, 10:06:04 AM »
hi , Lee ,
that's my test result

_\$

"00:00:00:297"
_\$

#### Lee Mac

• Seagull
• Posts: 12913
• London, England
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #26 on: March 16, 2011, 10:13:41 AM »
A quick test:

Code: [Select]
`_\$ (setq p1 '(1. 2. 0.) p2 '(4. 4. 3.) p3 '(5. 6. 0.))(5.0 6.0 0.0)_\$ (ss-aat p1 p2 p3)8.7178_\$ (LM:TriangleArea p1 p2 p3)8.7178_\$ (area_geron p1 p2 p3)8.7178`
Code: [Select]
`_\$ (Benchmark '((ss-aat p1 p2 p3) (LM:TriangleArea p1 p2 p3) (area_geron p1 p2 p3)))Benchmarking ..................Elapsed milliseconds / relative speed for 32768 iteration(s):    (AREA_GERON P1 P2 P3)..........1701 / 1.25 <fastest>    (LM:TRIANGLEAREA P1 P2 P3).....1857 / 1.14    (SS-AAT P1 P2 P3)..............2122 / 1.00 <slowest>`

#### chlh_jd

• Guest
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #27 on: March 16, 2011, 10:21:54 AM »
here's a new test dwg for total routine

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1569
• Moscow (Russia)
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #28 on: March 17, 2011, 06:05:52 AM »
new version
Code: [Select]
`(defun c:t1 (/ A1 A2 L LST S) (defun ins (p a b c)  (or (inters p a b c) (inters p b a c) (inters p c a b))) (defun area_geron (a b c / l p)  (setq l (cons 0 (mapcar (function distance) (list a b c) (list b c a)))        p (/ (apply (function +) l) 2.)  ) ;_  setq  (sqrt (abs (apply (function *) (mapcar (function -) l (list p p p p))))) ) ;_  defun (if (setq a1 0           s  (ssget "_x" '((0 . "point")))     ) ;_  setq  (foreach a (setq lst (mapcar (function (lambda (a) (cdr (assoc 10 (entget (cadr a))))))                               (ssnamex s)                       ) ;_  mapcar             ) ;_  setq   (foreach b lst    (foreach c lst     (if (and (> (setq a2 (area_geron a b c)) a1)              (vl-every (function (lambda (p) (ins p a b c))) lst)         ) ;_  and      (setq a1 a2            l  (list a b c)      ) ;_  setq     ) ;_  if    ) ;_  foreach   ) ;_  foreach  ) ;_  foreach ) ;_  if (entmakex  (append   '((0 . "LWPOLYLINE") (100 . "AcDbEntity") (100 . "AcDbPolyline") (90 . 3) (70 . 1))   (mapcar (function (lambda (a) (cons 10 a))) l)  ) ;_  append ) ;_  entmakex (princ))`
« Last Edit: March 17, 2011, 07:22:08 AM by ElpanovEvgeniy »

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1569
• Moscow (Russia)
##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #29 on: March 17, 2011, 06:53:03 AM »
hi , all
hi , Evgeniy
about pt in or at the triangle , I tested result is

use cal number of intersections method is the fastest , is it a wrong test ?
Code: [Select]
`;;;number of intersection;;;fastest(defun ss-pitp (p l)  ;;check point inside triangle .  ;;by GSLS(SS)  ((lambda (a b c)     (eq (+ (length (inters p a b c nil))    (length (inters p b a c nil))    (length (inters p c a b nil)) ) 9     )   )    (car l)    (cadr l)    (caddr l)  ))`