Topic: [Challenge] Point set inscribed the max area triangle

[chlh_jd]

There's no require unless the title .
And here's your pretty codes ...

[chlh_jd]

here's picture to express

[pkohut]

Problem needs a clear definition. The example picture doesn't help convey that.

[Kerry]

agreed Paul.
Looks to me like a MINIMUM triangle inside a collection of entities ??
... or perhaps not 

[SOFITO_SOFT]

Hello swamp people:
The problem is so?:
Find the 3 points of a given set that form the largest triangle not containing any point?
Is the good question ?
This may be related to the algorithms of Delaunay?
Regards...

[SOFITO_SOFT]

Hello :

Could this be the solution to this problem?
I have a very ugly code  (brute force) , but if you want I'll post it.
Regards. 

[CAB]

Yes, that would be my guess too.

Find the 3 points of a given set that form the largest triangle not containing any point?

Pseudo Code
Iterate all points, comparing by 3 to get triangle
Test for size & if it is free of points inside

[alanjt]

Like this?


Clunky and probably really slow...

Code: [Select]

(defun c:Test (/ AT:TriangleArea _toList _lwpline _uTrans pointlist trianglelist triangle)

  (defun AT:TriangleArea (a b c)
    ;; Returns area of three provided points
    ;; If returned value is negative, last point (c) exists on right side of a-b vector
    ;; Alan J. Thompson, 06.09.10
    (/ (- (* (- (car b) (car a)) (- (cadr c) (cadr a)))
          (* (- (cadr b) (cadr a)) (- (car c) (car a)))
       )
       2.
    )
  )

  (defun _toList (ss / i l)
    (if (and (eq (type ss) 'PICKSET) (> (sslength ss) 2))
      (repeat (setq i (sslength ss))
        (setq l (cons (cdr (assoc 10 (entget (ssname ss (setq i (1- i)))))) l))
      )
    )
  )



  (defun _lwpline (lst)
    (if (> (length lst) 1)
      (entmakex (append
                  (list '(0 . "LWPOLYLINE")
                        '(100 . "AcDbEntity")
                        '(100 . "AcDbPolyline")
                        (cons 90 (length lst))
                        '(70 . 1)
                  )
                  (mapcar (function (lambda (p) (list 10 (car p) (cadr p)))) lst)
                )
      )
    )
  )

  (defun _uTrans (p) (trans p 0 1))

  (foreach a (setq pointlist (_toList (ssget '((0 . "POINT")))))
    (mapcar (function
              (lambda (b c)
                (if (not (ssget "_WP" (mapcar (function _uTrans) (list a b c))))
                  (setq trianglelist (cons (list (abs (AT:TriangleArea a b c)) a b c) trianglelist))
                )
              )
            )
            (cdr pointlist)
            (cddr pointlist)
    )
  )


  (_lwpline (cdr (car (vl-sort trianglelist (function (lambda (a b) (> (car a) (car b))))))))
  (princ)
)

[chlh_jd]

Sorry to ALL , my English would be too less yet , I think I must go abored to the English countary to inprove my simple Einglish .
Thanks SOFITO_SOFT a lot !
and thank Alan , I'll try your codes .

[chlh_jd]

Hi Alan , I mean that the points can be on the triangle , but not be in it .
Perhaps the 'ssget fun error , it take a not correct result ;

[SOFITO_SOFT]

My solution for the new exemple:
3 Points in corners but none inside or in border:

Regards. 

[ElpanovEvgeniy]

my version:

Code: [Select]

(defun c:test (/ A1 A2 L LST S)
 (defun ins (l p)
  ;; check is a point inside the triangle.
  ;; by ElpanovEvgeniy
  (not (if (< (sin (- (angle (last l) p) (angle (last l) (car l)))) -1e-14)
        (vl-every (function (lambda (a b) (< (sin (- (angle a p) (angle a b))) -1e-14)))
                  l
                  (cdr l)
        )
        (vl-every (function (lambda (a b) (> (sin (- (angle a p) (angle a b))) 1e-14)))
                  l
                  (cdr l)
        )
       )
  )
 )
 (defun area_geron (p1 p2 p3 / l p)
  ;; area triangle
  ;; Uses the formula of Heron
  (setq l (cons 0 (mapcar (function distance) (list p1 p2 p3) (list p2 p3 p1)))
        p (/ (apply (function +) l) 2.)
  )
  (sqrt (abs (apply (function *) (mapcar (function -) l (list p p p p)))))
 )
 (if (setq a1 0
           s  (ssget "_x" '((0 . "point")))
     )
  (foreach a (setq lst (mapcar (function (lambda (a) (cdr (assoc 10 (entget (cadr a))))))
                               (ssnamex s)
                       )
             )
   (foreach b lst
    (foreach c lst
     (if (and (> (setq a2 (area_geron a b c)) a1)
              (vl-every (function (lambda (p) (ins (list a b c) p))) lst)
         )
      (setq a1 a2
            l  (list a b c)
      )
     )
    )
   )
  )
 )
 (entmakex
  (append
   '((0 . "LWPOLYLINE") (100 . "AcDbEntity") (100 . "AcDbPolyline") (90 . 3) (70 . 1))
   (mapcar (function (lambda (a) (cons 10 a))) l)
  )
 )
 (princ)
)

[chlh_jd]

hi , SOFITO_SOFT , I didn't see your picture ...
hi, Evgeniy , yours run fast , but not often a corret result ,see the picture : red is corret , yellow is yours result
tested in the new dwg

[ElpanovEvgeniy]

hi, Evgeniy , yours run fast , but not often a corret result ,see the picture : red is corret , yellow is yours result
tested in the new dwg

This is easily solved in the code in my checks, are not allowed a point lying on the sides of the triangle.

[ElpanovEvgeniy]

new version:

Code: [Select]

(defun c:t1 (/ A1 A2 L LST S)
 (defun ins (l p)
  ;; check is a point inside the triangle.
  ;; by ElpanovEvgeniy
  (not (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)
        )
       )
  )
 )
 (defun area_geron (p1 p2 p3 / l p)
  ;; area triangle
  ;; Uses the formula of Heron
  (setq l (cons 0 (mapcar (function distance) (list p1 p2 p3) (list p2 p3 p1)))
        p (/ (apply (function +) l) 2.)
  )
  (sqrt (abs (apply (function *) (mapcar (function -) l (list p p p p)))))
 )
 (if (setq a1 0
           s  (ssget "_x" '((0 . "point")))
     )
  (foreach a (setq lst (mapcar (function (lambda (a) (cdr (assoc 10 (entget (cadr a))))))
                               (ssnamex s)
                       )
             )
   (foreach b lst
    (foreach c lst
     (if (and (> (setq a2 (area_geron a b c)) a1)
              (vl-every (function (lambda (p) (ins (list a b c) p))) lst)
         )
      (setq a1 a2
            l  (list a b c)
      )
     )
    )
   )
  )
 )
 (entmakex
  (append
   '((0 . "LWPOLYLINE") (100 . "AcDbEntity") (100 . "AcDbPolyline") (90 . 3) (70 . 1))
   (mapcar (function (lambda (a) (cons 10 a))) l)
  )
 )
 (princ)
)