Author Topic: [Challenge] Point set inscribed the max area triangle  (Read 14543 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
函数:EE:PITP运行10000次测试结果00:00:00:108函数:SS-PITP运行10000次测试结果00:00:00:061函数:SS-PITP0运行10000次测试结果00:00:00:921函数:SS-PITP1运行10000次测试结果00:00:00:360
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: 12906
  • 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: 12906
  • 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

_$
函数:AREA_GERON运行10000次测试结果00:00:00:171函数:LM:TRIANGLEAREA运行10000次测试结果00:00:00:281函数:SS-AAT运行10000次测试结果00:00:00:297
"00:00:00:297"
_$

Lee Mac

  • Seagull
  • Posts: 12906
  • 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
函数:EE:PITP运行10000次测试结果00:00:00:108函数:SS-PITP运行10000次测试结果00:00:00:061函数:SS-PITP0运行10000次测试结果00:00:00:921函数:SS-PITP1运行10000次测试结果00:00:00:360
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)
  )
)



In your program ss-pitp error