Non-Planar Delaunay Triangulation

As promised in my earlier post on adjusting point proximities in a set of points here’s my Rhino Script for creating a Delaunay Triangulation from a set of non-planar points.

There are a large number of scripts that create Delaunay Triangulations from points for Rhino and most use far more efficient algorithms than the one I use here. However,  most scripts (and Grasshopper definitions) that I found did not work very well with sets of points  on a complex surface. The obvious way to get around the issue of triangulating non-planar sets of points is to project them to a plane, triangulate the projected points and then project the triangulation back on to the surface. The problem with this method (apart from it being like very round about) is that the sides of the triangles projected back on the surface are no longer straight lines so that what you effectively get from this method is a connectivity diagram that shows which points need to be connected to create a Delaunay Triangulation (rather than the triangulation itself) and one has to find some way to then connect the points to create the triangulation.

Non-Planar Points on a Complex Surface
A Delaunay Triangulation On a Complex Surface
A Non-Planar Delaunay Triangulation Derived from a Complex Surface
Option Explicit
‘Script written by <Ayodh Kamath>
‘Script copyrighted by <Ayodh Kamath>
‘Script version Monday, December 14, 2009 1:48:51 PM
Call Main()
Sub Main()
Dim intPtCount, intCheck, intPolyCount
Dim arrPts, strPt
Dim i,j,k,l
Dim strCircle, arrSrf, strSrf
intPolyCount = 0
ReDim arrPolylines(intPolyCount)
Dim arrDelete, strDelete
Dim arrProjectPts, arrProjectPt, arrNormVect, arrCentrePt
ReDim arrPreSort(2)
Dim arrSort
arrPts = Rhino.GetObjects(“Select points”,1)
ReDim arrPtCoords(UBound(arrPts))
intPtCount = 0
For Each strPt In arrPts
arrPtCoords(intPtCount) = Rhino.PointCoordinates(strPt)
intPtCount = intPtCount+1
intPtCount = intPtCount-1
ReDim Preserve arrPtCoords(intPtCount)
For i = 0 To intPtCount
For j = 0 To intPtCount
For k = 0 To intPtCount
strCircle = Rhino.AddCircle3Pt(arrPtCoords(i), arrPtCoords(j), arrPtCoords(k))
If Not IsNull(strCircle)  Then
arrCentrePt = Rhino.CircleCenterPoint(strCircle)
arrSrf = Rhino.AddPlanarSrf(Array(strCircle))
strSrf = arrSrf(0)
arrNormVect = Rhino.SurfaceNormal(strSrf, Rhino.SurfaceClosestPoint(strSrf, arrCentrePt))
intCheck = 0
For l = 0 To intPtCount
arrProjectPts = Rhino.ProjectPointToSurface(arrPtCoords(l), strSrf, arrNormVect)
If Not IsNull(arrProjectPts) And Not Rhino.IsPointOnCurve(strCircle, arrPtCoords(l))Then
Rhino.DeleteObject strSrf
Rhino.DeleteObject strCircle
intCheck = 1
Exit For
End If
If intCheck = 0 Then
arrPreSort(0) = arrPtCoords(i)
arrPreSort(1) = arrPtCoords(j)
arrPreSort(2) = arrPtCoords(k)
arrSort = Rhino.SortPoints(arrPreSort)
ReDim Preserve arrSort(3)
arrSort(3) = arrSort(0)
arrPolylines(intPolyCount) = Rhino.AddPolyline(arrSort)
intPolyCount = intPolyCount+1
ReDim Preserve arrPolylines(intPolyCount)
End If
End If
Rhino.ObjectsByType 8, True
Rhino.Command “Delete”
arrDelete = Rhino.ObjectsByType(4)
For Each strDelete In arrDelete
If Rhino.IsCircle(strDelete) Then
Rhino.DeleteObject strDelete
End If
intPolyCount = intPolyCount-1
ReDim Preserve arrPolylines(intPolyCount)
Rhino.Command “SelDup”
Rhino.Command “Delete”
End Sub

One thought on “Non-Planar Delaunay Triangulation

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s