ymg, the point of my combined bigger code was to make sure triangulation will end with convex boundary... I've just tried my example with much bigger supertriangle on original Evgeniy's code - X sorting and the result was OK... But I don't think it's too much reliable approach if you only scale supertriangle - of course the speed will be good, but in my experience with dealing with point clouds I've only faced with small clouds with just few info gathered from real terrain field... In my opinion the best way to compensate this lack of info is to interpolate point data with triangulation and as you can conclude, this by my opinion must be correctly done enclosing point cloud with correct boundary triangles... Of course one can cut this triangulation to only segment that can be concave cross shaped terrain model or similar, but for my purposes I prefer circular and convex shapes describing terrain segment in wider area shape - zone... With such triangulation, you can successfully continue to gather data as you now have better approximation of terrain and you can make better and bigger sections and describe surface in its entirety with expected surroundings... If I can recall someone searched the way to create convex hull boundary from point cloud to prepare data for next process - triangulation... This is by my opinion unnecessary as triangulation by itself should create convex hull boundary... And if I may say speed gaining in triangulation should be less important than making result of computation correct... If I was to choose to wait and be sure I'll get what I want, I would wait - I for sure can't make manual corrections be better and faster than correct automatic computation of a machine... That's why we all search for good and reliable programming examples and if you can make it faster then it was in the past then success will be greater, but sometime this can't be afforded in compensation for unreliable results...
As for (getcircumcircle) function I think you may find this code also useful... It's not dealing with angles, but pure math - obtaining coordinates of circle circumscribing 3 points...
(defun circumcircle3d ( p1 p2 p3 / v^v circumcircleucs zucs p1ucs p2ucs p3ucs cr )
(defun v^v ( u v )
(list
(- (* (cadr u) (caddr v)) (* (cadr v) (caddr u)))
(+ (- (* (car u) (caddr v))) (* (car v) (caddr u)))
(- (* (car u) (cadr v)) (* (car v) (cadr u)))
)
)
(defun circumcircleucs ( p1 p2 p3 / D Dcx Dcy c r )
(setq D (* 4.0 (- (* (- (car p1) (car p2)) (- (cadr p1) (cadr p3))) (* (- (car p1) (car p3)) (- (cadr p1) (cadr p2))))))
(setq Dcx (* 2.0 (-
(* (- (cadr p1) (cadr p3)) (+ (expt (car p1) 2) (expt (cadr p1) 2) (- (expt (car p2) 2)) (- (expt (cadr p2) 2))))
(* (- (cadr p1) (cadr p2)) (+ (expt (car p1) 2) (expt (cadr p1) 2) (- (expt (car p3) 2)) (- (expt (cadr p3) 2))))
)
)
)
(setq Dcy (* 2.0 (-
(* (- (car p1) (car p2)) (+ (expt (car p1) 2) (expt (cadr p1) 2) (- (expt (car p3) 2)) (- (expt (cadr p3) 2))))
(* (- (car p1) (car p3)) (+ (expt (car p1) 2) (expt (cadr p1) 2) (- (expt (car p2) 2)) (- (expt (cadr p2) 2))))
)
)
)
(setq c (list (/ Dcx D) (/ Dcy D)))
(setq r (distance c p1))
(list c r)
)
(setq zucs (v^v (mapcar '- p2 p1) (mapcar '- p3 p1)))
(setq p1ucs (trans p1 0 zucs) p2ucs (trans p2 0 zucs) p3ucs (trans p3 0 zucs))
(setq cr (circumcircleucs p1ucs p2ucs p3ucs))
(list (trans (list (caar cr) (cadar cr) (caddr p1ucs)) zucs 0) (cadr cr))
)