Author Topic: Triangulation (re-visited)  (Read 79623 times)

0 Members and 1 Guest are viewing this topic.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10198
Re: Triangulation (re-visited)
« Reply #15 on: October 17, 2008, 06:15:21 pm »
Arthur,
I sent you an email.

Unfortunately I know little about Triangulation but am a very good debugger.  8-)
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.

XXL66

  • Guest
Re: Triangulation (re-visited)
« Reply #16 on: January 09, 2010, 08:48:36 am »
@ElpanovEvgeniy : respect...  a triangulation in lisp this fast is amazing ! To bad your site is in russian, seems to be VERY interesting. BTW: you should give it a try in BricsCAD v10, time is reduced 50% compared to ACAD !




ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #17 on: May 19, 2011, 12:43:13 pm »
I've been playing around with the triangulation written by Daniel Piazza and modified by Cab.

Sorry to report I found a few bugs.

Namely in certain case the supertriangle interfere with the triangulation on the convex hull of the points cloud.

Also the PURGETRIANGLELST function sometimes return J instead of trianglelst causing the triangulation to fail.

Find below the revised code:

Code: [Select]
;******************************************************************;
; TRIANGULATE - Lisp command to create a TIN from 3D points.       ;
; ===========                                                      ;
;                                                                  ;
; Written by Daniele Piazza, ADN member Mechanical Solution s.r.l. ;
; http://pdcode.com/code.htm                                       ;
;                                                                  ;
; Original C coding "Triangulate"  written by PAUL BOURKE          ;
; http://astronomy.swin.edu.au/~pbourke/modelling/triangulate/     ;
;                                                                  ;
; This program triangulates an irregular set of points.            ;
; You can replace some code (sorting, list manipulation,...) with  ;
; VLisp functions to reduce the execution time.                    ;
;                                                                  ;
; This code is not seriously tested, if you find a bug...sorry!!   ;
; Goodbye, Daniele                                                 ;
;*******************************************************************
;;
;;
;;  Changes by CAB 03/13/06
;;  replaced the GETCIRCIRCUMCIRCLE routine
;;
;; Change by ymg 05/19/2011
;;Modified FINDSUPERTRIANGLE and PURGETRIANGLELST
;;Remove recursion in NTH_SUBST
(defun C:TRIANGULATE (/ fuzzy   nulllist  ss1      
      nv ptlst     trianglelst    
      i j   k        circle
      pt flag   perc         edgelst
     )

   (setq OLDCMD (getvar "CMDECHO"))
   (setvar "CMDECHO" 0)
   (command ".UNDO" "GROUP")
   (setq OLDSNAP (getvar "OSMODE"))
   (setvar "OSMODE" 0)
   (setq fuzzy 1e-8) ; tolerance in equality test
   (setq nulllist nil)

   (princ "\nSelect points...")
   (setq ss1 (ssget '((0 . "POINT"))))
   (setq start (getvar "date")
THINK-CNT 0
   )                               
   (setq ptlst (getptlist ss1))
   (setq ptlst (xsort ptlst))
   (setq nv (length ptlst))
   
   (setq supertriangle (findsupertriangle ptlst)) ; find super triangle
   (setq ptlst (append ptlst supertriangle))   ; append coordinates to the end of vertex list
 
   (setq trianglelst (list (list supertriangle nil)))  ; add supertriangle to the triangle list
 

   (setq i 0) 
   
   (while (< i nv)
      (THINKING (strcat "Processing TIN - " (itoa (/ (* i 100) nv)) "%    "))
      (setq pt (nth i ptlst))
      (setq edgelst nil) ; initialize edge buffer
      (setq j 0)
      (while
(and trianglelst (setq triangle (car (nth j trianglelst))))
   (setq flag T)
   (if (not (cadr (nth j trianglelst)))
      (progn
(setq circle (getcircircumcircle triangle)) ; calculate circumcircle   
(if (< (+ (caar circle) (cadr circle)) (car pt)) ; test point x and (pt) location
    (setq trianglelst (nth_subst j (list (car (nth j trianglelst)) T) trianglelst))
)
(if (isinside pt circle)
    (setq edgelst     (addtriangleedges triangle edgelst)
  trianglelst (nth_del j trianglelst)
  flag       nil
    )
)
      ) ; end progn
   ) ; end if
   (if flag
      (setq j (1+ j))
   )
      )
      (setq edgelst (removedoublyedges edgelst fuzzy nulllist))
      (setq trianglelst (addnewtriangles pt edgelst trianglelst))
      (setq i (1+ i))
   )
   
   (setq trianglelst (purgetrianglelst trianglelst supertriangle fuzzy)) ; remove triangles with supertriangles edges

   (foreach triangle (mapcar 'car trianglelst)
     (drawtriangle triangle)
   )


   (setvar "OSMODE" OLDSNAP)
   (setq OLDSNAP nil)
   (command ".UNDO" "END")
   (setq stop (getvar "date"))
   (princ (strcat "\r TIN Complete - Elapsed time: "
  (rtos (* 86400.0 (- stop start)) 2 2)
  " secs."
  )
   )
   (setvar "CMDECHO" OLDCMD)
   (princ)
)






; XSORT - Original Shell Sort function replaced with VLISP sort (much quicker :-)  ;
;                                                                                        ;
(defun XSORT ( PTLST /)
  (vl-sort PTLST (function (lambda (a b) (< (car a) (car b)))))
)

; NTH_DEL ;
; ;
; delete the n item in the list (by position, not by value!!) ;
; ;
; Elimina l'oggetto che si trova nella posizione N della lista LST. L'utilizzo di ;
; funzioni ricorsive,oltre a non assicurare maggiore velocitÓ, pu˛ creare problemi;
; di overflow dello stack in caso di liste molto lunghe. ;
(defun NTH_DEL (N LST / l)
(repeat n
  (setq l (cons (car lst) l)
lst (cdr lst)
  )
)
(append (reverse l)(cdr lst))
)

; NTH_SUBST ;
; ;
; Replace the index element in the list with new element. This function is ;
; recursive this is not a great solution with a large amount of data. ;
; ;
;(defun NTH_SUBST (index new Alist)
;   (cond
;      ((minusp index) Alist)
;      ((zerop index) (cons new (cdr Alist)))
;      (T
;       (cons (car Alist) (nth_subst (1- index) new (cdr Alist)))
;      )
;   )
;)
;;;Removed the recursion  ymg --------------------------
(defun NTH_SUBST (index new Alist / temp)
   (cond
      ((minusp index) Alist)
      ((zerop index)(cons new (cdr Alist)))
      ((> index 0)  (while (> index 0)
                       (setq temp  (cons (car alist) temp)
                     alist (cdr alist)
                     index (1- index)
                       )
                    )
                    (append (reverse temp) (list new) (cdr alist))
      )
   )
)
     

; GETPTLIST ;
; ;
; sset -> list (p1 p2 p3 ... pn) ;
; ;
(defun GETPTLIST (ss1 / i pt ptlst)
   (if (not (zerop (sslength ss1)))
      (progn
(setq i 0)
(while (setq pt (ssname ss1 i))
     (setq ptlst (cons (cdr (assoc 10 (entget pt))) ptlst))
     (setq i (1+ i))
)
      )
   )
   ptlst
)


; FINDSUPERTRIANGLE ;
; ;
; Search the supertriangle that contain all points in the data set ;
; ;
(defun FINDSUPERTRIANGLE (ptlst / xmax   xmin   ymax   ymin
  dx dy dmax   xmid   ymid   trx1
  trx2 trx3 try1   try2   try3   trz1
  trz2 trz3
)
   (setq xmax (apply 'max (mapcar 'car ptlst))
xmin (apply 'min (mapcar 'car ptlst))
ymax (apply 'max (mapcar 'cadr ptlst))
ymin (apply 'min (mapcar 'cadr ptlst))
dx   (- xmax xmin)
dy   (- ymax ymin)
dmax (max dx dy)
xmid (* (+ xmax xmin) 0.5)
ymid (* (+ ymax ymin) 0.5)
trx1 (- xmid (* dmax 20.0)) ;modified ymg
try1 (- ymid dmax)
trz1 0.0
trx2 xmid
try2 (+ ymid (* dmax 20.0)) ;modified ymg
trz2 0.0
trx3 (+ xmid (* dmax 20.0)) ;modified ymg
try3 (- ymid dmax)
trz3 0.0
   )
   (list (list trx1 try1 trz1)
(list trx2 try2 trz2)
(list trx3 try3 trz3)
   )
)








;;=============================================================
;;  Changes by CAB 03/13/06
;;  replaced the GETCIRCIRCUMCIRCLE routine
;;=============================================================

(defun getcircircumcircle (triangle / p1 p2 p3 pr1 pr2 cen rad bisector)
  ;;  return a pt list for a perpendicular bisector 20 units long
  (defun bisector (p1 p2 / perp_ang midpt)
    (setq p1       (list (car p1) (cadr p1)) ; make sure 2d point
          perp_ang (+ (angle p1 p2) (/ pi 2.0))) ; perpendicular angle
    (setq midpt (mapcar '(lambda (pa pb) (+ (/ (- pb pa) 2.0) pa)) p1 p2))
    (list (polar midpt perp_ang 10) (polar midpt (+ pi perp_ang) 10))
  )
  (setq p1  (car triangle)
        p2  (cadr triangle)
        p3  (caddr triangle)
        pr1 (bisector p1 p2)
        pr2 (bisector p1 p3)
        cen (inters (car pr1) (cadr pr1) (car pr2) (cadr pr2) nil)
        rad (distance cen p1)
  )
  (list cen rad)
)
;;=============================================================



; ISINSIDE ;
; ;
; test if pt is inside a circle ;
; ;
(defun ISINSIDE (pt circle)
(setq ctr (car circle)
       rad (cadr circle)
)
(< (distance pt ctr) rad)
)

; ADDTRIANGLEEDGES ;
; ;
; add triangle edges at the edge queue ;
; ;
(defun ADDTRIANGLEEDGES (triangle edgelst)
   (append edgelst (list (list (car triangle)  (cadr triangle))
                         (list (cadr triangle) (caddr triangle))
                         (list (caddr triangle)(car triangle))
                   )
   )
)

; DRAWTRIANGLE ;
; ;
; the fun side of the algorithm. Draw triangulation. ;
; ;
(defun DRAWTRIANGLE (triangle)
  (entmake (list (cons 0 "3DFACE") (cons 10 (car triangle))  (cons 11 (caddr triangle))
                                   (cons 12 (cadr triangle)) (cons 13 (cadr triangle))
   )
  )
)

; EQUALMEMBER ;
; ;
; Check if "item" is in "lista" or not by equality test. With real number the ;
; standard fuction "member" not work correctly. ;
; ;
(defun EQUALMEMBER (item lista fuzzy /)
(apply 'or (mapcar '(lambda (x) (equal x item fuzzy)) lista))
)         

; REMOVEDOUBLYEDGES ;
; ;
; Test the edge queue to remove duplicates (warning CW & CCW!) ;
; ;
(defun REMOVEDOUBLYEDGES (edgelst fuzzy nulllist /)
(setq j 0)
(while (< j (length edgelst))
  (setq k (1+ j))
  (while (< k (length edgelst))
   (if
    (or (and (equal (car  (nth j edgelst)) (car  (nth k edgelst)) fuzzy)
             (equal (cadr (nth j edgelst)) (cadr (nth k edgelst)) fuzzy)
        )
        (and (equal (car  (nth j edgelst)) (cadr (nth k edgelst)) fuzzy)
             (equal (cadr (nth j edgelst)) (car  (nth k edgelst)) fuzzy)
        )
    )
    (setq edgelst (nth_subst j nulllist edgelst)
          edgelst (nth_subst k nulllist edgelst)
    )
   )
   (setq k (1+ k))
  )
  (setq j (1+ j))
)
edgelst
)

; ADDNEWTRIANGLES ;
; ;
; Add new triangle generated by pt to triangle list. ;
; ;
(defun ADDNEWTRIANGLES (pt edgelst trianglelst / j triangle)
   (setq j 0)
   (while (< j (length edgelst))
      (if (nth j edgelst)
(setq triangle    (cons pt (nth j edgelst))
       trianglelst (cons (list triangle nil) trianglelst)
)
      )
      (setq j (1+ j))
   )
   trianglelst
)


; PURGETRIANGLELST ;
; ;
; replace all triangles that share a vertex with supertriangle ;
; ;
(defun PURGETRIANGLELST (trianglelst supertriangle fuzzy /)
   (setq j 0)
   (while (and trianglelst (setq triangle (car (nth j trianglelst))))
      (if
(apply 'or
(mapcar '(lambda (x) (equalmember x supertriangle fuzzy))
triangle
)
)
   (setq trianglelst (nth_del j trianglelst))
   (setq j (1+ j))
      )
   )
   (setq trianglelst trianglelst); modified to return trianglelst was returning J in certain case ymg
   
)






;                                       ;
; THINKING - STANDARD PROGRESS SPINNER  ;
;                                       ;
(defun THINKING (prmpt)
  (setq THINK-CNT (1+ THINK-CNT))
  (princ (strcat "\r" (nth (rem THINK-CNT 4) '("\|" "\/" "\-" "\\")) prmpt))
)


; ********************************* END OF CODING *******************************************
(princ "\n'TRIANGULATE' Loaded \n")
(princ)

The triangulation still fail on large data set.  I have removed the recursion in the NTH_SUBST as an attempt
to cure this problem.  I'll look at it some more.

Also played with Elpanov triangulation.  It also suffers from problem on the convex hull.
On a small set of 25 points, it missed to triangulate one of the point and 4 triangles on the hull
are missing.

Here is the point set:
     
Code: [Select]
((1652.17 356.759 446.623) (1666.15 431.163 -353.053) (1688.64 379.861 -372.616) (1708.17 888.849 489.959)
 (1763.96 799.643 117.206) (1811.9 678.149 -387.295) (1818.56 140.657 -256.432) (1883.13 226.078 -79.1498)
 (1888.23 124.665 122.761) (1900.26 864.281 -41.0016) (1950.15 730.671 -164.785) (1979.73 671.496 -19.8523)
 (2031.64 260.656 -497.925) (2069.42 69.732 -278.069) (2071.19 123.139 -183.401) (2096.73 383.737 -280.053)
 (2173.55 135.927 283.044) (2241.51 1048.67 47.7767) (2298.4 460.399 211.447) (2304.6 871.301 -156.27)
 (2441.41 517.957 -411.649) (2455.6 695.636 -390.896) (2462.35 249.15 99.3225) (2585.43 387.857 201.498)
 (2591.77 477.032 100.238) (-17456.9 -419.739 0.0) (2121.97 20138.0 0.0) (21700.8 -419.739 0.0))

So far I have made no attempt to find what is wrong in this code.

ymg

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #18 on: May 19, 2011, 03:32:16 pm »
Hello:
With the algorithm of P. Bourke, employs a few seconds.
That may solve your problem?
Best Regards

PD:
;;;Credit to Paul Bourke (pbourke@swin.edu.au) for the original Fortran 77 Program :))
;;;Converted to AutoLISP by Pedro Ferreira (pwp.netcabo.pt/pedro_ferreira)
;;;Check out: http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/
;;;You can use this code however you like providing the above credits remain in tact

CAB

  • Global Moderator
  • Seagull
  • Posts: 10198
Re: Triangulation (re-visited)
« Reply #19 on: May 19, 2011, 03:43:17 pm »
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.

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #20 on: May 19, 2011, 06:35:10 pm »
I have tried also those two implementations of the Bourke algorithm and can report that they are OK.

Triangulator the one by Ferreira suffers from the fact that It uses global variables all over the place and could
therefore leave you stranded.

The one by Mihai Popescu is a nicer one.  I have not look in it to analyze the data structure.

Triangulate by Daniele Piazza is also nicely written and works provided that we modify it as per above.

Now the Fast one by Elpanov would certainly be interesting as long as we can fix the problem along the
convex hull.   Also I have not looked at the data structure.

All this to say that we have all kind of triangulation.

However Triangulation are created to ease further treatment of the data like contouring and
creating profiles on the TIN.  In other word we need to create more than just the 3dface.

Look at the following paper http://research.engineering.wustl.edu/~pless/506/l5.html
for the kind of data structure we should be creating, namely a DCEL (Short for Doubly Connected Edge List)

With such a structure it becomes easy to walk on the TIN, go to the neighbor of a 3dface , contour etc.

So far none of the triangulation that we  have do it well.

ymg

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1534
  • Moscow (Russia)
Re: Triangulation (re-visited)
« Reply #21 on: May 20, 2011, 07:36:59 am »
Surprisingly, in my program there is a small error - a typo, but for many years, nobody has corrected the ...
It really is such a complicated program?
 :wink:
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1534
  • Moscow (Russia)
Re: Triangulation (re-visited)
« Reply #22 on: May 20, 2011, 08:07:43 am »
Now, especially checked - Playing a random mistake. I accidentally deleted a few lines. The code is similar to the line and the code is understandable, what is missing! If, indeed, no one can understand this program, I promise next week to lay out the full code! But I will be sorry that such a code just copy and do not try to understand...
 :-o
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1534
  • Moscow (Russia)
Re: Triangulation (re-visited)
« Reply #23 on: May 20, 2011, 08:15:37 am »
Corrected code faster!  :-D
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #24 on: May 20, 2011, 09:20:59 am »
Hi Elpanov,

The code is understandable.  But the fact is that you write very tight code and consequentlly
It is a little bit hard to follow.

However yours is fast, very fast for something written in Autolisp.  I would not have though that
such speed was attainable.  Therefore Hat's off to you !

What I am really interested in is that the triangulation should create a doubly connected edge list
in order to be ready to contour and or profile afterward. Could even be used to create toolpath
on a surface if we contour along the x or y axis then generate gcode.

Also why autolisp? when there is all kind of C++  and arx solutions.  My reason is that autolisp
can be used on any version of autocad without having to worry about recompilation and all.
I have code wich dates back to be before release 12 that still get some use.

Again congratulations on attaining such speed.

ymg

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #25 on: May 20, 2011, 09:49:48 am »

In other word we need to create more than just the 3dface.

With such a structure it becomes easy to walk on the TIN, go to the neighbor of a 3dface , contour etc.

So far none of the triangulation that we  have do it well.

ymg
Hello :
if you have 3DFACEs you can converted to sliced-3dsolid, to unite all, and you can easily apply Boolean operations or sections. Usually I do and areas of some hectares with resolution of 2 or 5 meters work very well.
Greetings.
PD.: I attached a small example .... final solid (zip) and previous steps (dwg)

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #26 on: May 20, 2011, 09:58:27 am »
oops... :-) a little picture...

Greetings  :-)

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #27 on: May 20, 2011, 10:01:30 am »
Here is something I originally posted in general programming on the subject of contouring.
With some corrections...!

If you look at the following link http://paulbourke.net/papers/conrec/ there are some explanation
on what is involved for determining a contour through a single triangle.

Here I have crudely translated the C routine proposed in that page to Autolisp (Tested and No attempt at Optimization)

Code: [Select]
;Create a contour slice through a 3 vertex facet pa, pb, pc
;The contour "level" is a horizontal plane perpendicular to the z axis,
;ie: The equation of the contour plane Ax + By + Cz + D = 0
;has A = 0, B = 0, C = 1, D = -level
;   Return:
;           ((nil nil nil) (nil nil nil)  0)   if the contour plane doesn't cut the facet
;           (  (x y z)       (x y z)      2)   if it does cut the facet
;           ((nil nil nil) (nil nil nil) -1)   for an unexpected occurrence
;If a vertex touches the contour plane nothing need to be drawn

(defun contourfacet (triangle level / pa pb pc sidea sideb sidec p1x p1y p1z p2x p2y p2z)
   (setq pa (car triangle)
         pb (cadr triangle)
         pc (caddr triangle)
   )
   (setq sidea (-(caddr pa)level)
sideb (-(caddr pb)level)
sidec (-(caddr pc)level)
   )
   (cond
      ;---Are all the vertices on one side----------
      ((and (>= sidea 0)  (>= sideb 0) (>= sidec 0))
       (setq ret 0)
      )
      
      ((and (<= sidea 0)  (<= sideb 0) (<= sidec 0))
       (setq ret 0)
      )
      ;---Is pa the only point on a side by itself---
      ((and (/=(sign sidea) (sign sideb))  (/=(sign sidea) (sign sidec)))

          (setq p1x (- (car pa) (* sidea (/ (- (car pc) (car pa)) (- sidec sidea)))))
          (setq p1y (- (cadr pa) (* sidea (/ (- (cadr pc) (cadr pa)) (- sidec sidea)))))
          (setq p1z (- (caddr pa) (* sidea (/ (- (caddr pc) (caddr pa)) (- sidec sidea)))))
          (setq p2x (- (car pa) (* sidea (/ (- (car pb) (car pa)) (- sideb sidea)))))
          (setq p2y (- (cadr pa) (* sidea (/ (- (cadr pb) (cadr pa)) (- sideb sidea)))))
          (setq p2z (- (caddr pa) (* sidea (/ (- (caddr pb) (caddr pa)) (- sideb sidea)))))
          (setq ret 2)
      )
      ;---Is pb the only point on a side by itself---
      ((and (/=(sign sideb) (sign sidea))  (/=(sign sideb) (sign sidec)))

          (setq p1x (- (car pb) (* sideb (/ (- (car pc) (car pb)) (- sidec sideb)))))
          (setq p1y (- (cadr pb) (* sideb (/ (- (cadr pc) (cadr pb)) (- sidec sideb)))))
          (setq p1z (- (caddr pb) (* sideb (/ (- (caddr pc) (caddr pb)) (- sidec sideb)))))
          (setq p2x (- (car pb) (* sideb (/ (- (car pa) (car pb)) (- sidea sideb)))))
          (setq p2y (- (cadr pb) (* sideb (/ (- (cadr pa) (cadr pb)) (- sidea sideb)))))
          (setq p2z (- (caddr pb) (* sideb (/ (- (caddr pa) (caddr pb)) (- sidea sideb)))))
          (setq ret 2)
      )
      ;---Is pc the only point on a side by itself---
      ((and (/=(sign sidec) (sign sidea))  (/=(sign sidec) (sign sideb)))

          (setq p1x (- (car pc) (* sidec (/ (- (car pa) (car pc)) (- sidea sidec)))))
          (setq p1y (- (cadr pc) (* sidec (/ (- (cadr pa) (cadr pc)) (- sidea sidec)))))
          (setq p1z (- (caddr pc) (* sidec (/ (- (caddr pa) (caddr pc)) (- sidea sidec)))))
          (setq p2x (- (car pc) (* sidec (/ (- (car pb) (car pc)) (- sideb sidec)))))
          (setq p2y (- (cadr pc) (* sidec (/ (- (cadr pb) (cadr pc)) (- sideb sidec)))))
          (setq p2z (- (caddr pc) (* sidec (/ (- (caddr pb) (caddr pc)) (- sideb sidec)))))
          (setq ret 2)
      )
      (t (setq ret -1))
   )
   (list (list p1x p1y p1z) (list p2x p2y p2z) ret)
)


;--Define the Signum function-----
(defun sign (x)
   ( cond
      (( minusp x ) -1 )
      (( zerop x)    0 )
      ( t            1 )
   )
)

Now in this next link http://www.originlab.com/www/helponline/Origin/en/UserGuide/Creating_Contour_Graphs.html#Drawing_of_contour_lines
there is a nice explanation on how you should follow a contour on the TIN.

Basically you find a triangle which has a crossing for the level under consideration, calculate the two points p1 and p2 that intersect the triangle
with above routine. The first point is saved as the starting point of a polyline.  This triangle is marked as traversed.

You then move to the neighboring triangle (The one which  has a reversed edge called a twin), calculate the two points again, mark as traversed until you reach the outside of the TIN (You are sitting on  an edge that has no twin) or you reach your starting point.

We  now check if any other triangle still has a crossing for that level, If it is the case we start a new polyline on the same level.


We then repeat the previous steps for the next level.

Now who is up to come up with an efficient way to do this ?
I am quite rusty with my Autolisp and I am just starting with the visual stuff.

Now you know why I am after a DCEL connected structure from the triangulation.

ymg

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #28 on: May 20, 2011, 10:06:34 am »
Sofito_Soft,

That's an interesting way to do it.

How fast would it be if we wanted to generate a contour map from it ?

I will look at it.

Thanks,

ymg

VovKa

  • Swamp Rat
  • Posts: 761
  • Ukraine
Re: Triangulation (re-visited)
« Reply #29 on: May 20, 2011, 12:14:54 pm »
Now, especially checked - Playing a random mistake. I accidentally deleted a few lines. The code is similar to the line and the code is understandable, what is missing! If, indeed, no one can understand this program, I promise next week to lay out the full code! But I will be sorry that such a code just copy and do not try to understand...
 :-o
hmmm, your variables naming style scares us off, Evgeniy :)
once i tested your code and i had to change
this
Code: [Select]
(vl-remove-if-not
    (function (lambda (a) (and (< mi (caadr a) ma) (< mi (caaddr a) ma))))
    l2
)
to this
Code: [Select]
(vl-remove-if
    (function
        (lambda (a)
            (or (vl-some (function (lambda (c) (vl-position c s))) a) (null a))
        )
    )
    l2
)
to make it work

by i don't really remember why i've done that...