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

0 Members and 1 Guest are viewing this topic. ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #30 on: March 17, 2011, 02:45:44 PM »
Hi,

While using a function which returns the triangle algebraic area (signed area) as Alanjt's AT:TriangleArea or algeb-area for the triangle area, the same routine can be used to evaluate if a point is inside the triangle:

Code: [Select]
`(defun algeb-area (p1 p2 p3)  (/ (- (* (- (car p2) (car p1)) (- (cadr p3) (cadr p1))) (* (- (car p3) (car p1)) (- (cadr p2) (cadr p1)))     )     2.0  ))(defun isInside (pt p1 p2 p3)  ((lambda (a1 a2 a3)     (or       (and (<= 0.0 a1) (<= 0.0 a2) (<= 0.0 a3))       (and (<= a1 0.0) (<= a2 0.0) (<= a3 0.0))     )   )    (algeb-area pt p1 p2)    (algeb-area pt p2 p3)    (algeb-area pt p3 p1)  ))`
This will return T if the point is strictly inside or lies on the triangle.
Replacing '<=' with '<' will evaluate only strictly inside point.
Speaking English as a French Frog ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #31 on: March 17, 2011, 04:04:41 PM »
Or perhaps another method:

Code: [Select]
`(defun isInside ( pt p1 p2 p3 )  (    (lambda ( a1 a2 a3 )      (or        (and (<= 0.0 a1) (<= 0.0 a2) (<= 0.0 a3))        (and (<= a1 0.0) (<= a2 0.0) (<= a3 0.0))      )    )    (sin (- (angle p1 pt) (angle p1 p2)))    (sin (- (angle p2 pt) (angle p2 p3)))    (sin (- (angle p3 pt) (angle p3 p1)))  ))`
[ Used some of your code Gile ]

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #32 on: March 18, 2011, 04:23:50 AM »
hi Gile , Lee ,
to judge a point in or at triangle ofcause can use area method , but it take a lot cal , I think the intersetion method is fastest .
hi Evgeniy , in the routine it can be
Code: [Select]
`(defun ss-pitp (p l)    ;;check point inside triangle .    ;;by GSLS(SS)    (< ((lambda (a b c)   (+ (length (inters p a b c nil))      (length (inters p b a c nil))      (length (inters p c a b nil))   ) ) (car l) (cadr l) (caddr l)       )       9    )  )`however yours 'ins' is Excellent ! but the wholl routine is too slow if the points nums is more , e.g. 528 points in my often dwg .

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #33 on: March 18, 2011, 04:34:22 AM »
by the way , in this routine , the area cal is for Comparison , so it can be simplified like this
Code: [Select]
`(defun ss-aat (p1 p2 p3)  ;;area triangle  ;;Uses conventional formula.  (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)))       )       ))`

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #34 on: March 18, 2011, 05:45:59 AM »
is it possible to use Mesh method ?

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #35 on: March 18, 2011, 05:51:14 AM »
Perhaps , We can solve it from 2D first ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #36 on: March 18, 2011, 06:21:18 AM »
hi Gile , Lee ,
to judge a point in or at triangle ofcause can use area method , but it take a lot cal , I think the intersetion method is fastest .
hi Evgeniy , in the routine it can be
Code: [Select]
`(defun ss-pitp (p l)    ;;check point inside triangle .    ;;by GSLS(SS)    (< ((lambda (a b c)   (+ (length (inters p a b c nil))      (length (inters p b a c nil))      (length (inters p c a b nil))   ) ) (car l) (cadr l) (caddr l)       )       9    )  )`however yours 'ins' is Excellent ! but the wholl routine is too slow if the points nums is more , e.g. 528 points in my often dwg .
It seems to me that the ss-pitp routine do not return right results, for example:
(ss-pitp '(2. 1. 0.) '((0. 0. 0.) (5. 0. 0.) (3. 2. 0.))) returns nil even (2. 1. 0.) is inside the triangle.
Speaking English as a French Frog

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #37 on: March 18, 2011, 07:30:28 AM »
hi Gile
that's right result , because it change into the cond that whether point out of triangle , if to judge in or at it , use this
Code: [Select]
`(defun ss-pitp (p l)    ;;check point inside triangle .    ;;by GSLS(SS)    (= ;|if judge out of , ucs /= or < |; ((lambda (a b c)  (+ (length (inters p a b c nil))     (length (inters p b a c nil))     (length (inters p c a b nil))  ) ) (car l) (cadr l) (caddr l)       )       9    )  )`

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #38 on: March 18, 2011, 07:41:42 AM »
to sort point set by mesh , can use follow func , but not sure it's right
Code: [Select]
`;;;(defun sort-mesh       (pts n / minpt maxpt dvx fsx dvy fsy i dm a b mid ptm end)  ;;sort point set by mesh  ;;by GSLS(SS)  (setq minpt (apply 'mapcar (cons 'min pts)      ) maxpt      (apply 'mapcar (cons 'max pts)      ) dvx   (/ (- (car maxpt) (car minpt)) n) fsx   (car minpt) dvy   (/ (- (cadr maxpt) (cadr minpt)) n) fsy   (cadr minpt)  )  (setq pts (vl-sort pts  (function    (lambda (e1 e2)      (< (car e1) (car e2))    )  ) )  )  (setq i 1)  (while pts    (setq dm (+ fsx (* i dvx)))    (setq a (car pts))    (cond ((<= (- dm dvx) (car a) dm)   (setq mid (cons a mid) pts (cdr pts)   )  )  ((<= dm (car a) (+ dm dvx))   (setq ptn (cons mid ptn) mid nil mid (cons a mid) pts (cdr pts) i   (1+ i)   )  )  (t   (setq ptn (cons nil (cons mid ptn)) mid nil i   (1+ i)   )  )    )  )  (setq end nil)  (foreach b ptn    (if b      (progn (setq b  (vl-sort b   (function     (lambda (e1 e2)       (< (cadr e1) (cadr e2))     )   )  )      i  1      mid nil      ptm nil ) (while b  (setq dm (+ fsy (* i dvy)))  (setq a (car b))  (cond ((<= (- dm dvy) (cadr a) dm) (setq mid (cons a mid)       b   (cdr b) ) ) ((<= dm (cadr a) (+ dm dvy)) (setq ptm (cons mid ptm)       mid nil       mid (cons a mid)       b   (cdr b)       i   (1+ i) ) ) (t (setq ptm (cons nil (cons mid ptm))       mid nil       i   (1+ i) ) )  ) ) (setq end (cons (reverse ptm) end))      )      (setq end (cons (repeat n (setq b (cons nil b))) end))    )  )  end);;test (foreach a   (sort-mesh    (mapcar      (function (lambda (x) (cdr (assoc 10 (entget (cadr x)))))      )      (cdr (reverse (ssnamex (ssget '((0 . "point"))))))    )    20  )  (princ a))`
« Last Edit: March 18, 2011, 07:44:45 AM by chlh_jd » ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #39 on: March 18, 2011, 07:57:38 AM »
hi Gile
that's right result , because it change into the cond that whether point out of triangle , if to judge in or at it , use this
Code: [Select]
`(defun ss-pitp (p l)    ;;check point inside triangle .    ;;by GSLS(SS)    (= ;|if judge out of , ucs /= or < |; ((lambda (a b c)  (+ (length (inters p a b c nil))     (length (inters p b a c nil))     (length (inters p c a b nil))  ) ) (car l) (cadr l) (caddr l)       )       9    )  )`

Sorry, I can't understand what you mean.

Your new routine still return false result IMO.

The point (3. -2. 0.) is outside the triangle ((0. 0. 0.) (5. 0. 0.) (3. 2. 0.)) but
(ss-pitp '(3. -2. 0.) '((0. 0. 0.) (5. 0. 0.) (3. 2. 0.))) returns T
Speaking English as a French Frog

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #40 on: March 18, 2011, 08:03:38 AM »
hi Gile
that's right result , because it change into the cond that whether point out of triangle , if to judge in or at it , use this
Code: [Select]
`(defun ss-pitp (p l)    ;;check point inside triangle .    ;;by GSLS(SS)    (= ;|if judge out of , ucs /= or < |; ((lambda (a b c)  (+ (length (inters p a b c nil))     (length (inters p b a c nil))     (length (inters p c a b nil))  ) ) (car l) (cadr l) (caddr l)       )       9    )  )`

Sorry, I can't understand what you mean.

Your new routine still return false result IMO.

The point (3. -2. 0.) is outside the triangle ((0. 0. 0.) (5. 0. 0.) (3. 2. 0.)) but
(ss-pitp '(3. -2. 0.) '((0. 0. 0.) (5. 0. 0.) (3. 2. 0.))) returns T
hi gile , my test reulet return NIL ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #41 on: March 18, 2011, 08:20:18 AM »
Quote
hi gile , my test reulet return NIL

I do not know how you're making your tests, but :

(inters p a b c nil) returns (15.0 -10.0 0.0) => length = 3
(inters p b a c nil) returns (15.0 10.0 0.0) => lenght = 3
(inters p c a b nil) returns (3.0 0.0 0.0) => length = 3
Total lengthes = 9 => T

Try this little test command
Code: [Select]
`(defun c:test (/ l p)  (setq l '((0. 0. 0.) (5. 0. 0.) (3. 2. 0.)))  (command "_.pline")  (mapcar '(lambda (p) (command "_non" p)) l)  (command "_close")  (while (setq p (getpoint))    (alert      (if (ss-pitp p l) "Inside" "Outside"      )    )  )  (princ))`
Speaking English as a French Frog

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #42 on: March 18, 2011, 08:58:51 AM »
Nice gile !
thank you for often a nice test routine .
it really take a wrong result .

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #43 on: March 18, 2011, 09:04:47 AM »
by the cods , it'll return error result inside ,like the picture
Code: [Select]
`(defun ss-pitp (p l)    ;;check point inside triangle .       ((lambda (a b c)   (not (or (inters p a b c) (inters p b a c) (inters p c a b))) ) (car l) (cadr l) (caddr l)       )  )`

#### chlh_jd

• Guest ##### Re: [Challenge] Point set inscribed the max area triangle
« Reply #44 on: March 18, 2011, 09:26:34 AM »
by the way , angle & inters are use in 2D plan , in 3Dplan it can't return corret reslut .
if in 3D , do it can use this func , I can't sure it because less of  'trans .
Code: [Select]
`;;;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)  ))`