I have updated the triangulation so that an adjacency list or neighbour list of triangle is generated.
Also modified so that we generate Voronoi Diagram plus the Delaunay triangulation.
The neigbour list now permits us to locate ourself efficiently in the tin via a new routine called Triloc.
This is actually Lawson's walk who invented the procedure. Since then many different scheme have been devised
to accelerate it when you have huge triangulation.
Here's a paper showing some of them:
Walking Location Algorithms by Roman Soukal.
Another paper
Walking in a triangulation by Olivier Devillers analyzes the speed of the various schemes.
Here are the added function to the triangulation:
;;****************************************************************************;
;; (getneighbour pl tl) ;
;; ;
;; Parameters: pl, Points List ;
;; tl, Triangle List (index into pl) ;
;; Returns: nl, List of neigbours for each edges of each triangles. ;
;; ;
;; Should be done by the triangulation. ;
;;****************************************************************************;
(defun getneighbour
(pl tl
/ nl pos tmp
)
)
)
(setq tmp
(cons (/ pos
3) tmp
)); Integer Division ; )
)
)
)
nl
)
;;****************************************************************************;
;; (triloc p) ;
;; ;
;; Locates triangle which encloses point p using Lawson's Walk. ;
;; ;
;; Given p a point, Returns Index in tl of triangle containing the point. ;
;; If outside the triangulation Return is nil. ;
;; ;
;; Point List pl and Neigbour List nl are defined outside this routine. ;
;; by ymg August 2013 ;
;;****************************************************************************;
(defun triloc
(p
/ v v1 v2 v3
)
; Negative return, point is on right of v1->v2 ;
; Positive return, point is on left of v1->v2 ;
; 0 return, point is smack on the vector. ;
(defun onside
(p v1 v2
/) )
)
(t
(setq found t
)) ; We are inside triangle tn ; )
(if (not tn
)(setq found t
)); We are outside the triangulation ; )
tn ;
)
The body of the triangulation has been modified to make use of the getneighbour function.
Note that contour has been removed from the attachment as I am currently doing a major
rewrite to make use of the neighbour list and hopefully gain some speed.
I have also put together a demoz routine to demonstrate what can be done with triloc and the neighbour list.
It is heavily inspired (leeched
) by LeeMac's
grtext.lsp Here is the code to that one followed by an animated gif showing it in action.
;;****************************************************************************;
;; Demoz ;
;; Demonstrate Lawson's Walk, to locate a triangle in a triangulation ;
;; As you hover around the screen, the triangle under the screen is ;
;; highlighted and the coordinates of the cursor position including Z, plus ;
;; the triangle number are written to the screen. ;
;; ;
;; Inspired by LeeMac's Grtext.lsp ;
;; ;
;; by ymg August 2013 ;
;;****************************************************************************;
(defun c:demoZ
( / *error* pnt str col ent etxt p prevtxt prevhatch
prevtn scl t1 t2 t3 tr txt txtp xof yof)
(toglay '("Points" "Voronoi"))
p (getz p t1 t2 t3)
)
; Built with MakeEntmake.lsp by Cab at TheSwamp ;
)
)
prevtn tn
)
)
)
)
)
; Leeched from LeeMac (LM:GrText) ;
; http://www.lee-mac.com/lisp/html/GrTextDemo.html ;
xof 30
yof -30
txtp
(list (+ (car p
) (* xof scl
)) (+ (cadr p
) (* yof scl
))) )
)
)
)
(toglay '("Points" "Voronoi"))
)
;;****************************************************************************;
;; (getz p t1 t2 t3) ;
;; Given point p and triangle defined by points t1, t2, t3 ;
;; Returns: (x y z) where z is on face of triangle. ;
;; ;
;; By ymg August 2013 ;
;;****************************************************************************;
(defun getz
(p t1 t2 t3
/ v1 v2
)
; Calculating a normal vector with gile's functions in line. ;
; Note that I do not calculate the unit vector for the normal n. ;
)
)
)
;; (toglay lst) ;
;; Toggles (on/off) a list of Layer names. ;
;; From a Fishing Story by Cab at TheSwamp >-=((((°> ;
;; ;
;; by ymg August 2013 ;
(defun toglay
(lst
/ entlist l
) entlist
)
)
)
)
)
To run the demo, load the attachment demoz.lsp, Issue command GEN and enter number of points desired
in the triangulation.
Isue command VOR, the Voronoi Diagram and the Delaunay Triangulation will generate.
Issue command DEMOZ, as you hover in the drawing, the triangle number plus coordinates X,Y and Z of point under cursor
is displayed and the currently occupied triangle is hatched in solid Red.
Sorry!, about the long post.
ymg