Topic: 2d points triangulation attempt... too slow

[Brick_top]

Hi there

I'm trying to do 2d point triangulation, and I think I have succeeded the problem is that it is extremelly slow

What can I do to optimize it?

Code: [Select]

;;;; 2d point triangulation attempt;;;;

(defun rpg (a)
(* a (/ 180.0 pi))
);radianos para graus
(defun gpr (a)
  (* pi (/ a 180.0))
);graus para radianos
(defun c:tri () ;<- variables left undeclared for testing
  (prompt "\nSeleccionar os pontos (Select Points): ")
  (setq ssp (ssget '((0 . "POINT")))
ssent nil
plst nil
num 0
num1 0
num4 1
num6 1
  );setq

  (repeat (sslength ssp)
    (setq ssn (ssname ssp num)
  ssent (append (list ssn) ssent)
  num (+ 1 num)
    );setq
   );repeat
  (setq plst (mapcar
        '(lambda (x)
           (cdr (assoc 10 (entget x)))
          )ssent
       );mapcar
         );setq

   (repeat (length plst)
     (setq dlst (cdr (mapcar
  '(lambda (x)
     (list (car plst) x (list (distance (car plst) x))) ;lista das distâncias
   ) plst
  );mapcar
);cdr
   );setq
       
  (setq dlstmin (vl-sort dlst '(lambda (x1 x2)(< (car (caddr x1))(car (caddr x2)))));lista das distâncias entre pontos organizadas em função da menor
dlstmind (cons (car (car dlstmin))(mapcar '(lambda (x) (cadr x)) dlstmin));lista das coordenadas ao primeiro ponto para calculo
                                                                                          ;sem as distâncias entre eles
          );setq                                                                         
     
       (repeat (- (length dlstmind) 1)
          (setq el1 (car dlstmind)
el2 (nth num4 dlstmind)
dlstmind2 (vl-remove el2 dlstmind)
        ang1 (rpg (angle el1 el2))
          );setq
        (repeat (- (length dlstmind2) 1)
    (setq el1b (car dlstmind)
  el2b (nth num6 dlstmind2)
          ang2 (rpg (angle el1b el2b))
  ang1f (+ ang1 90.0)
  ang1f2 (- ang1 90.0)
  ang2f (+ ang2 90.0)
  ang2f2 (- ang2 90.0)
            );setq
         
  (setq l1 (list el1 el2)
l2 (list el1b el2b)
        l1m (list (/ (+ (car (car l1))(car (cadr l1))) 2)(/ (+ (cadr (car l1))(cadr (cadr l1))) 2));inicio linha para intersecção
l2m (list (/ (+ (car (car l2))(car (cadr l2))) 2)(/ (+ (cadr (car l2))(cadr (cadr l2))) 2));inicio linha para intersecção
l1mf (polar l1m (gpr ang1f) 500000000.0);fim de linha para intersecção num sentido
l1mf2 (polar l1m (gpr ang1f2) 500000000.0)
l2mf (polar l2m (gpr ang2f) 500000000.0);fim de linha para intersecção num sentido
l2mf2 (polar l2m (gpr ang2f2) 500000000.0)
          );setq
          ;(entmake (list (cons 0 "line")(cons 10 l1mf2)(cons 11 l1mf)))
          ;(entmake (list (cons 0 "line")(cons 10 l2mf2)(cons 11 l2mf)))
          (setq circ (inters l1mf2 l1mf l2mf2 l2mf);centro do circulo de teste
                dcf (distance circ el1);raio do primeiro circulo
          );setq
    (setq dlstmindn dlstmind2)
    (setq dlstmindn (vl-remove el1 dlstmindn))
            (setq dlstmindn (vl-remove el2 dlstmindn))
    (setq dlstmindn (vl-remove el2b dlstmindn))
   (setq dlstmind1 (apply 'min (mapcar '(lambda (x) (distance circ x)) dlstmindn));lista das distâncias entre o centro do primeiro circulo e todos os pontos
                                                            ;excepto os 3 primeiros do calculo
          );setq

          (if
           (< dcf dlstmind1)
            (progn
             (entmake
      (list
        (cons 0 "LINE")
        (cons 10 el1)
        (cons 11 el2)
       );list
      );entmake
             (entmake
      (list
        (cons 0 "LINE")
        (cons 10 el2)
        (cons 11 el2b)
       );list
      );entmake
              (entmake
      (list
        (cons 0 "LINE")
        (cons 10 el2b)
        (cons 11 el1)
       );list
      );entmake
             );progn
            );if
        (setq num6 (+ 1 num6))
      );repeat    
      (setq num6 1)
      (setq num4 (+ 1 num4))
     
     );repeat
     (setq plst (reverse (cons (car plst) (reverse (cdr plst)))));nova lista com inicio no ponto mais próximo do anterior
     (setq num4 1)
     (setq num6 1)
    );repeat
);defun
It took 11 seconds to make this example (55 points). It can take much longer depending on the number of points I guess

[ElpanovEvgeniy]

see: Triangulation (re-visited)

[Brick_top]

I can't belive this, I searched but didn't find your example

And then... just as I started this topic I found your lisp before you posted it!

oh well...

Mine looks like something from caveman compared to yours.

I don't know math 

[SOFITO_SOFT]

Hello all:
In a PC very normal and A2008 , less than 1 second with the triangulate from
 pbourke@swin.edu.au
Practically the same result, my points are located at a good eye on your photo

Greetings...

[dgorsman]

Mr. Bourke does an excellent job of laying out the algorithm.

I have found triangulation routines to be an excellent teacher of loop optimization for coding.

[Brick_top]

Hello all:
In a PC very normal and A2008 , less than 1 second with the triangulate from
 pbourke@swin.edu.au
Practically the same result, my points are located at a good eye on your photo

Greetings...

Yeah mine is very very slow 

At least its good to know that it is triangulating correctly...

I could have given you the dwg 

[ElpanovEvgeniy]

At least its good to know that it is triangulating correctly...

I think this is not true:

[Brick_top]

At least its good to know that it is triangulating correctly...

I think this is not true:

I guess I must study the delaunay triangulation and some math...

By the way could you give me some pointers about learning math?

[Brick_top]

I've managed to reduce the execution time to about 10%

albeit at the cost of not triangulating to a big distance

[SOFITO_SOFT]

Hello:
Evgeniy: You're right: there is something wrong.
Greetings...

[SOFITO_SOFT]

the drawing exemple for test it

[SOFITO_SOFT]

Hello all:
You're right: there is something wrong. >>> actually ... triangles are smaller than those drawn ... but the rest of the area causes a giant triangle, and for models of land probably less real. Maybe in some applications the problem is real, but for terrain and plots, it seems that the solution is valid. I think ...?¿

Greetings...

[ElpanovEvgeniy]

Hello all:
You're right: there is something wrong. >>> actually ... triangles are smaller than those drawn ... but the rest of the area causes a giant triangle, and for models of land probably less real. Maybe in some applications the problem is real, but for terrain and plots, it seems that the solution is valid. I think ...?¿

Greetings...

oops 
I checked your file - all right, it's my fault!
Delaunay condition holds ...

[SOFITO_SOFT]

Hello all:
Another added value of P. Bourke method is that the same calculation gives the maximum contour (reed-yellow fence). 

And also, with a small modification, can make a 3D model very quickly. I've checked against professional MDT programs (expensives) and go perfect results. Sometimes even better ... more realistic ... more similar to real terrain, even generating triangles that hit the eye ...
Greetings ...
PD: credits of version wath I use:

Code: [Select]

;******************************************************************************************;
;** Credit to Paul Bourke (pbourke@swin.edu.au) for the original Fortran 77 Program :))  **;
;** Converted to AutoLISP by Mihai Popescu (mihai.popescu@shareit.ro)                    **;
;** Check out: http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/index.html       **;
;** You can use this code however you like providing the above credits remain in tact    **;
;******************************************************************************************;