### Author Topic: [Challenge] Point set inscribed the max area triangle  (Read 14651 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: 483
##### 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.
New tread (not retired) - public repo at https://github.com/pkohut

#### 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
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

#### 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: 10401
##### 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

#### alanjt

• Needs a day job
• Posts: 5352
• 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: 1569
• 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))`

#### 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: 1569
• 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.

#### ElpanovEvgeniy

• Water Moccasin
• Posts: 1569
• 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))`