Topic: Triangulation (re-visited)

[ymg]

Here I modified ADDEDGE to take care of Anglada's precondition.

I elected to do it there, because prior to triangulation we cannot
know for sure if that edge will be present or not.

Code - Auto/Visual Lisp: [Select]

1. ;;****************************************************************************;
2. ;; addedge     by ymg                        May   2014                       ;
3. ;;                                                                            ;
4. ;; As per paper: An Improved Incremental Algorithm For Constructing           ;
5. ;;               Restricted Delaunay Triangulations. by Marc Vigo Anglada     ;
6. ;;                                                                            ;
7. ;; Arguments: a, Index of point in a triangulation.                           ;
8. ;;            b, Index second point, defining edge ab to be inserted          ;
9. ;;                                                                            ;
10. ;; External Variables tl and nl will be modified.                             ;
11. ;;                                                                            ;
12. ;; Will insert an edge in an existing triangulation.  Triangles crossed by    ;
13. ;; the edge will be deleted.  Cavity will  be re-triangulated to restore      ;
14. ;; Delaunay's condition. New triangle will be redrawn.                        ;
15. ;;                                                                            ;
16. ;;****************************************************************************;
17.  
18. (defun addedge (a b / 3df  pa pb poll polu topo tr v vopo vshr)
19.    (setq pa (nth a pl)
20.          pb (nth b pl)
21.          tn nil
22.          tn (triloc (polar pa (angle pa pb) 0.001) pl tl nl)
23.          tr (nth tn tl)
24.           v a
25.          dl nil polu nil poll nil newtri nil
26.    )
27.    (if (not (and (member a tr) (member b tr)))
28.       (progn
29.          (while (not (member b tr))
30.             (setq topo (topp tr v tl nl)
31.                   vopo (vopp topo tr)
32.                   vshr (vl-remove vopo topo)
33.             )
34.             (if (onleft_p vopo a b)
35.                (setq  v (if (onleft_p (car vshr) a b) (car vshr) (cadr vshr)) polu (cons v polu))
36.                (setq  v (if (not (onleft_p (car vshr) a b)) (car vshr) (cadr vshr)) poll (cons v poll))
37.             )
38.             (setq dl (cons tr dl) ; dl List of triangle to be modified              ;
39.                   tr topo
40.             )
41.          )
42.  
43.          (setq v (car (vl-remove v vshr)))
44.          (if (onleft_p v a b)
45.             (setq polu (cons v polu))
46.             (setq poll (cons v poll))
47.          )  
48.          (setq dl (cons tr dl))   ; Adding last triangle to be modified             ;
49.          (setq polu (reverse polu) poll (reverse poll))  
50.          
51.          (setq newtri nil)        ; New Triangles will be accumulated in newtri     ;
52.          (tripol polu a b   t)
53.          (tripol poll a b nil)
54.          (foreach tr dl
55.             (entdel (get_trname tr pl))
56.          )
57.          (mk_layer (list "TIN" 8))
58.          (setq 3df '(0 . "3DFACE"))
59.          (setq i -1)
60.          (foreach tr newtri
61.             (entmakex (list 3df                        
62.                            (cons 10 (nth (car tr)   pl))
63.                            (cons 11 (nth (car tr)   pl))
64.                            (cons 12 (nth (cadr tr)  pl))
65.                            (cons 13 (nth (caddr tr) pl))
66.                       )
67.             )
68.             (setq tl (subst tr (nth (setq i (1+ i)) dl) tl))
69.          )  
70.          (setq nl (get_neighbour tl))
71.       )
72.    )
73.    (princ)
74. )
75.  

ymg

[pedroantonio]

ymg.I still have the same problem .Is not working .......

[ymg]

topographer,

Did u remove the dcl from the temporary folder
as instructed by XXL66 ?

[smemo]

in row 116 of  TriangV0.5.8.LSP
(if (not (findfile fn)) (make_dcl)) 
add "fn" to generate dcl
(if (not (findfile fn)) (make_dcl fn))

great job, my compliments ymg

[pedroantonio]

Thank you smemo now works fine.....

I upload the correct code

[smemo]

in DCL when I select:
 [v] Generate Vonoroi Diagram
i get
Error: no function definition: GETNEIGHBOUR

[motee-z]

I got error in dcl dialogue at line 401 and 402
syntax error
symbol: "0
0.0
0.00"
 

[XXL66]

Maybe we should try another approuch for the edges, namely by adding Steiner vertices on the edges (Gabriel) before doing the triangulation (because the TIN computation is very fast).

page 18:
https://team.inria.fr/titane/files/2014/03/cgal-meshes.pdf

Whenever a segment is 'encroached' you middle it. You check this again for the 2 new edges and so on. When all points ar added just run trianulation.
Now just find a fast method to check if a point is inclosed in the circle.
However, i'm not sure if this would solve every edge. I guess so because "Encroached subsegments have priority over skinny triangles". What do you think ?




 

[csgoh]

tested using acad13.
triangles cut across breaklines.??
the layer ts represents top of slope edge whereas bs represents the bottom edge of a slope.
any solutions?

cs

[XXL66]

I think there is still a bug in the add edges function, might have to do with tolerance on the points.

The point position for each edge end point is searched in the pl list. I think it might fail here. You probably got the warning msgbox "missing endpoint" ?
Maybe it would be better to build the pl list from start based on edge vertices only + solitary points.

[csgoh]

I did not get any error messages when testing out.

cs

[XXL66]

i did (using your dwg), see attachment

[ymg]

smemo,


Thanks for the appreciation.

Voronoi will not work in a constrained triangulation.
Some of the region would overlap.

However it does work for a Delaunay triangulation.
So maye we should add the following in the triangulate
function. But the main bug is the function name is
get_neighour

Code: [Select]

((if (and (= govor "1")(not cdtl))
    (progn
               ; Generates the Neighbour List                                 ;
(setq  tv (car (_vl-times))    ; Timer for Voronoi            ;
                       nl (get_neighbour tl)
                )

[ymg]

I think there is still a bug in the add edges function

I believe you means in the get_constraints function.  It is possible
as searching for points is a little tempermental.  Something else that need
to be done in there is to exclude LWPOLYLINE.

As for Steiner points and Gabriel's graph, I know of the technique
but you are entering a different ball park which is  the Augmented Triangulation.

Right now the biggest time hog is the recomputig of the whole neighbour list
for each edge.  As told earlier, I intend to fix it.

ymg

[XXL66]

(setq a (vl-position (car e) pl)
          b (vl-position (cadr e) pl)
        flg (or (not a) (not b))
             lst (cons (list a b) lst)
)

in get_constraints yes, i think comparing vertices with point needs a tolerance, the vl-position will possible not found the according point in the list


I did some testing with steiner, it doesn't work in all cases, because when you add points it might be in a circumcle of a segment that already is processed.
This (terrible) code add's steiner points (only line segments)

Code: [Select]

(defun c:add_steiner (/ ss i e np newlist)
  (setq ss
(ssget '((0 . "LINE"))
)
  )
  (if ss
    (progn
      (repeat (setq i (sslength ss))
(setq e (ssname ss (setq i (1- i))))
(gabriel e)
;;; (setq newlist (append (gabriel e) newlist))
;;; (setq newlist (cons (cdr (assoc 10 (entget e))) newlist))
;;; (setq newlist (cons (cdr (assoc 11 (entget e))) newlist))
      )
    )
  )
;;;  (foreach np newlist
;;;    (entmake (list (cons 0 "POINT") (cons 10 np)))
;;;  )
)


(defun gabriel (e / entl bp ep mp r elist edge found i ss)
  (setq nplist nil)
  (setq entl (entget e))
  (setq bp (cdr (assoc 10 entl)))
  (setq ep (cdr (assoc 11 entl)))
  (setq mp (list (/ (+ (car bp) (car ep)) 2.0)
(/ (+ (cadr bp) (cadr ep)) 2.0)
(/ (+ (caddr bp) (caddr ep)) 2.0)
   )
  )
  ;; middle point
  (setq r (/ (distance bp (list (car ep) (cadr ep))) 2.0))
  ;; 2D radius
  (setq elist (list (list bp ep mp r)))
  (setq ss
(ssget "_w"
(list (- (car mp) r) (- (cadr mp) r))
(list (+ (car mp) r) (+ (cadr mp) r))
'((0 . "POINT"))
)
  )
  ;; selectionset of points around edge


  (while elist
    (setq edge (car elist))
    (setq bp (car edge))
    (setq ep (cadr edge))
    (setq mp (caddr edge))
    (setq r (cadddr edge))

    ;; (command "line" (list (- (car mp) r) (- (cadr mp) r)) (list (+ (car mp) r) (+ (cadr mp) r)) "")
    (if ss
      (progn
(setq found nil)
(repeat (setq i (sslength ss))
  (setq e (ssname ss (setq i (1- i))))
  (setq pt (cdr (assoc 10 (entget e))))
  (if (and (not found)
   (< (distance (list (car pt) (cadr pt)) mp) (- r 0.001)) ;;; 0.001 fuzz to avoid edge points bp ep
      )
    ;; point in circle, we have to split segment
    (progn
      (setq newmp_bp (list (/ (+ (car bp)
(car mp)
      )
      2.0
   )
   (/ (+ (cadr bp)
(cadr mp)
      )
      2.0
   )
   (/ (+ (caddr bp)
(caddr mp)
      )
      2.0
   )
     )
      )
      (setq newmp_ep (list (/ (+ (car ep)
(car mp)
      )
      2.0
   )
   (/ (+ (cadr ep)
(cadr mp)
      )
      2.0
   )
   (/ (+ (caddr ep)
(caddr mp)
      )
      2.0
   )
     )
      )
      (setq elist (cdr elist));;; remove current edge and add 2 new edge segments
      (setq elist (cons (list bp mp newmp_bp (/ r 2.0)) elist))
      (setq elist (cons (list ep mp newmp_ep (/ r 2.0)) elist))
      (entmake (list (cons 0 "POINT") (cons 10 mp)))
;     (setq nplist (cons mp nplist))
      (setq found t)
    )
  )
)
(if (not found)
  (setq elist (cdr elist))
)
;;; points do not meet criteria, remove the edge
      )
      (progn
(setq elist (cdr elist))
;;; no points, remove the edge
      )
    )
  )
 ; nplist
)