### Author Topic: [Challenge] Point set inscribed the max area triangle  (Read 9583 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)
)
)
;;;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)
)
)
;;;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)
)
)

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

#### 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 (- (+
)
(+
)
)
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: 221
##### 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: 5327
• 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: 12313
• 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: 12313
• 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
)
)
« Last Edit: March 16, 2011, 09:28:44 AM by Lee Mac »

#### alanjt

• Needs a day job
• Posts: 5327
• 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: 12313
• 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: 1542
• 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: 1542
• 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)