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

0 Members and 1 Guest are viewing this topic.

gile

  • Water Moccasin
  • Posts: 2261
  • Marseille, France
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

Lee Mac

  • Seagull
  • Posts: 12390
  • London, England
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

gile

  • Water Moccasin
  • Posts: 2261
  • Marseille, France
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 »

gile

  • Water Moccasin
  • Posts: 2261
  • Marseille, France
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

gile

  • Water Moccasin
  • Posts: 2261
  • Marseille, France
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)
  )
)