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

0 Members and 1 Guest are viewing this topic.

chlh_jd

  • Guest
[Challenge] Point set inscribed the max area triangle
« on: March 12, 2011, 12:07:59 PM »
There's no require unless the title .
And here's your pretty codes ...

chlh_jd

  • Guest
Re: [Challenge] Point set inscribed the max area triangle
« Reply #1 on: March 14, 2011, 01:13:37 AM »
here's picture to express

pkohut

  • Bull Frog
  • Posts: 431
Re: [Challenge] Point set inscribed the max area triangle
« Reply #2 on: March 14, 2011, 01:54:31 AM »
Problem needs a clear definition. The example picture doesn't help convey that.

Kerry

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: [Challenge] Point set inscribed the max area triangle
« Reply #3 on: March 14, 2011, 04:00:38 AM »
agreed Paul.
Looks to me like a MINIMUM triangle inside a collection of entities ??
... or perhaps not  :|
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

--> Donate to theSwamp<--

SOFITO_SOFT

  • Guest
Re: [Challenge] Point set inscribed the max area triangle
« Reply #4 on: March 14, 2011, 07:04:51 AM »
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

  • Guest
Re: [Challenge] Point set inscribed the max area triangle
« Reply #5 on: March 14, 2011, 08:22:24 AM »
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

  • Global Moderator
  • Seagull
  • Posts: 10376
Re: [Challenge] Point set inscribed the max area triangle
« Reply #6 on: March 14, 2011, 09:28:58 AM »
Yes, that would be my guess too.
Quote
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
I've reached the age where the happy hour is a nap. ()
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

alanjt

  • Needs a day job
  • Posts: 5327
  • Standby for witty remark...
Re: [Challenge] Point set inscribed the max area triangle
« Reply #7 on: March 14, 2011, 10:38:59 AM »
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)
)
Civil 3D 2019 ~ Windohz 7 64bit
Dropbox

chlh_jd

  • Guest
Re: [Challenge] Point set inscribed the max area triangle
« Reply #8 on: March 14, 2011, 12:11:46 PM »
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

  • Guest
Re: [Challenge] Point set inscribed the max area triangle
« Reply #9 on: March 14, 2011, 12:25:38 PM »
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

  • Guest
Re: [Challenge] Point set inscribed the max area triangle
« Reply #10 on: March 15, 2011, 12:20:44 AM »
My solution for the new exemple:
3 Points in corners but none inside or in border:

Regards.  :-)

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: [Challenge] Point set inscribed the max area triangle
« Reply #11 on: March 15, 2011, 09:33:58 AM »
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)
)
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

chlh_jd

  • Guest
Re: [Challenge] Point set inscribed the max area triangle
« Reply #12 on: March 16, 2011, 01:02:08 AM »
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
« Last Edit: March 16, 2011, 01:07:30 AM by chlh_jd »

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: [Challenge] Point set inscribed the max area triangle
« Reply #13 on: March 16, 2011, 01:19:19 AM »
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.
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1542
  • Moscow (Russia)
Re: [Challenge] Point set inscribed the max area triangle
« Reply #14 on: March 16, 2011, 01:27:02 AM »
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)
)
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/