0 1 1 633638060608906250 0 5 98 true true Shaded voronoi2D.ghx Does Vornoi2D for a given input of sites and a given boundary polygon. Dimitrie Stefanescu 2008 633635069525781250 0 119 76 1 0 6 fbac3e32-f100-4292-8692-77240a42fd1a Point InputPoints e02af7a5-e2de-417d-b597-8a8f5969bd86 false false 0 0 27 154 30.75 73 20 154 30.75 73 20 154 30.75 false true false 34e8d475-def9-4231-ab6f-d0f904ad43ef -1 0 0 point_object 1096de72-ba75-4826-97bb-8b540062f54f -1 0 0 point_object 2b4e7251-066d-4a3a-8f66-964b27cc9863 -1 0 0 point_object 6e865f10-1391-428b-b0c0-7c9083e4fd05 -1 0 0 point_object 527d87db-4d22-4375-8f11-e379d62a35b3 -1 0 0 point_object 074a47b7-6b1b-498f-8c28-7d76d9763f6e -1 0 0 point_object 53c1e361-3cfd-4688-a547-6e2db4c9c717 -1 0 0 point_object 9d3eb434-928f-4466-a106-b6592236d024 -1 0 0 point_object e29cc760-833a-43b3-a065-1189b4ecf0b0 -1 0 0 point_object 7ebb8df0-a1ca-4492-a6ca-c45904a1b07f -1 0 0 point_object 30231f5f-32c3-4128-ae7c-14a25278b35c -1 0 0 point_object 17a8c79c-71bc-4ed3-8d75-c20c974c2d5e -1 0 0 point_object a9ab054f-ba50-419d-b5ef-0792cbc1d751 -1 0 0 point_object 5fad6196-3a3d-4d06-85e7-a6dc0bc873c0 -1 0 0 point_object 9efec801-48a7-4806-8c5e-b0082a14aa5c -1 0 0 point_object 8086f0d1-bc3f-41ea-af85-8b65e8692c90 -1 0 0 point_object 7262cd47-9fd9-418d-88cf-7aaed0a1fc60 -1 0 0 point_object 211092ed-5281-4a9e-82ba-7d552d6cb9bf -1 0 0 point_object 04df9ab7-d7fa-4c62-95f0-ed7d2de1a3ba -1 0 0 point_object b96abb6c-b8b5-4b19-a422-5cc00790c68e -1 0 0 point_object 1972a830-7d21-4062-8bef-3fd6343ab5f2 -1 0 0 point_object b55003cd-04c6-40ab-b0b5-9231ad86e17c -1 0 0 point_object d790d83d-c196-4e14-ad77-502c011440da -1 0 0 point_object c6648aa0-00f3-41dd-9f5e-6224cbd0d627 -1 0 0 point_object 78764e1c-d2a6-4ae4-8616-6b3ea8d6aaff -1 0 0 point_object 7e862091-cc3c-49bd-913f-da657830a4db -1 0 0 point_object b5256a87-0de2-4b9d-8593-c7753b7e3f0b -1 0 0 point_object fbac3e32-f100-4292-8692-77240a42fd1a Point BoundaryPoints 188255c5-b9ac-4286-8841-48ecbda6b394 true false 0 0 4 131.6 98.95 98 20 131.6 98.95 98 20 131.6 98.95 false true false b20a29ce-5bc0-4d5f-880a-83dc4d8b2758 -1 0 0 point_object 08b74d8f-8983-4625-8071-16977522f0ee -1 0 0 point_object b5fcd3b8-ef66-46a5-b45c-d77dfd906313 -1 0 0 point_object 145cfc32-603a-4c9a-8ccc-eb666fbd917c -1 0 0 point_object fb6aba99-fead-4e42-b5d8-c6de5ff90ea6 VB.NET Script ''' <your code> ' 'Script by Dimitrie Stefanescu <www.improved.ro/blog> ' 'Based on David Rutten's algorithm <www.reconstructivism.net> ' 'Released under 'Creative Commons Attribution-Noncommercial-Share Alike 3.0 Licence. 'http://creativecommons.org/licenses/by-nc-sa/3.0/us/ ' ' 'Version .9f - code ain't clean A = New List (Of OnLine) B = New List (Of onLine) Dim _A As New List (Of onLine) Dim __A As New List (Of on3dPoint) Dim _C As New List (Of onPolyline) 'Dim ptarr() As Double 'ptarr = New Double() Dim k As Int16 : k = 0 Dim i As On3dPoint Dim j As On3dPoint For Each i In pointset Dim vvv As vCell vvv = New vCell(i, boundary) For Each j In pointset If i <> j Then vvv.slice(j) End If Next __A = vvv.getVertices() For k = 1 To __A.count - 1 _A.Add(New OnLine(__A.item(k - 1), __A.item(k))) Next _A.Add(New OnLine(__A.item(0), __A.item(__A.count - 1))) Next 'B = drawBoundary(boundary) A = _A ''' </your code> 'GENERAL USE FUNCTIONS' 'Draws the boundary rectangle Function drawBoundary(ByVal pts As List (Of on3dPoint)) As List(Of onLine) Dim l As New List (Of onLine) Dim p As int16 : p = 0 For p = 1 To pts.count - 1 Step 1 l.Add(New OnLine(pts.item(p), pts.item(p - 1))) Next l.add(New OnLine(pts.item(0), pts.item(pts.count - 1))) Return l End Function 'VORONOI VERTEX CLASS' Public Class vVertex Public loc As On3dPoint Public isNew As Boolean Public deleteme As Boolean Public Sub New(ByVal _loc As on3dPoint) loc = _loc isNew = True deleteme = False End Sub Public Sub New(ByVal _loc As on3dPoint, ByVal _isNew As Boolean) loc = _loc isNew = _isNew deleteme = False End Sub Public Function distance(ByVal pt As on3dPoint) As Double 'modifiy to return just the square of the distance, makes it faster Return loc.DistanceTo(pt) End Function End Class 'VORONOI CELL CLASS' Public Class vCell Public vertices As New List (Of vVertex) Public origin As On3dPoint 'constructor; Public Sub New(ByVal _origin As on3dPoint) origin = _origin End Sub Public Sub New(ByVal _origin As on3dPoint, ByVal _b As List (Of on3dPoint)) origin = _origin Dim pt As On3dPoint Dim vert As vVertex For Each pt In _b vert = New vVertex(pt, False) vertices.Add(vert) Next End Sub 'calculates teh perpendicular bisector between two points Public Function bisectorAt(ByVal a As on3dPoint, ByVal b As on3dPoint) As OnLine Dim le As On3dPoint, ls As on3dPoint ls = (a + b) / 2 le = New On3dPoint(0, 0, 0) le.x = ls.x - (b.y - a.y) le.y = ls.y + (b.x - a.x) Return (New OnLine(ls, le)) End Function 'Intersects two lines 9th grade math style Public Function intersectL(ByVal l1 As OnLine, ByVal l2 As OnLine) As Double Dim p As Double : p = 0 Dim denom, enom As Double Dim x1, x2, x3, x4 As Double Dim y1, y2, y3, y4 As Double x1 = l1.from.x x2 = l1.To.x x3 = l2.from.x x4 = l2.To.x y1 = l1.from.y y2 = l1.To.y y3 = l2.from.y y4 = l2.To.y denom = (y4 - y3) * (x2 - x1) - (y2 - y1) * (x4 - x3) If(denom = 0) Then Return -1 End If enom = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3) p = enom / denom If((p < 0) Or (p >= 1)) Then Return -1 End If Return p End Function Public Sub addVertex(ByVal vertex As vVertex, ByVal index As int16) vertices.Insert(index, vertex) End Sub Public Sub purgeVList() Dim _vertices As New List (Of vVertex) Dim _v As vVertex For Each _v In vertices If(_v.deleteme = False) Then _vertices.add(_v) End If Next vertices = _vertices End Sub Public Sub slice(ByVal pttt As On3dPoint) Dim bis As OnLine bis = bisectorAt(origin, pttt) Dim i As int16, j As Int16, n As Int16 Dim p As Double i = -1 n = 0 Do i = i + 1 j = (i + 1) Mod vertices.Count p = intersectL(New OnLine(vertices.item(i).loc, vertices.Item(j).loc), bis) If p >= 0 Then n = n + 1 If p = 0 Then vertices.Item(i).isNew = True Else Dim nvert As vVertex Dim newpt As New On3dPoint(0, 0, 0) newpt.x = vertices.item(i).loc.x + p * (vertices.item(j).loc.x - vertices.item(i).loc.x) newpt.y = vertices.item(i).loc.y + p * (vertices.item(j).loc.y - vertices.item(i).loc.y) nvert = New vVertex(newpt, True) vertices.Insert(i + 1, nvert) i = i + 1 End If If n = 2 Then Exit Do End If End If Loop Until i >= vertices.Count - 1 Dim k As Int16 For k = 0 To vertices.Count - 1 If(vertices.Item(k).distance(origin) < vertices.Item(k).distance(pttt)) Then i = k Exit For End If Next Dim signal As Boolean signal = False For k = 0 To vertices.Count - 1 i = (i + 1) Mod vertices.Count If(vertices.Item(i).isnew = True) Then vertices.Item(i).isnew = False signal = Not signal Else If (signal = True) Then vertices.Item(i).deleteme = True End If End If Next purgeVList() End Sub Public Function getVertices() As List (Of On3dPoint) Dim ret As New List (Of on3dPoint) Dim vertex As vVertex For Each vertex In vertices ret.Add(vertex.loc) Next Return ret End Function End Class 0 Voronoi2D 09d38f9b-e0da-4431-883b-6f3365e20df3 true longest_list 2 pointSet boundary 4 A B C D 293.6797 14.1445 116 104 353.6797 16.1445 27 100 353.6797 16.1445 false true false pointSet 13c20bce-8e59-429c-a84c-44848fb4e1bd true true 1 e02af7a5-e2de-417d-b597-8a8f5969bd86 0 On3dPoint true 0 0 0 0 293.6797 16.1445 60 50 293.6797 16.1445 false true false boundary 71c6e2a7-4cb5-43c8-9861-c2ded311e6d2 true true 1 188255c5-b9ac-4286-8841-48ecbda6b394 0 On3dPoint true 0 0 0 0 293.6797 66.1445 60 50 293.6797 66.1445 false true false out 1ba37d14-d6f6-4600-b4b2-05e23dc7f3ca true false 0 0 0 0 0 0 0 380.6797 16.1445 29 20 380.6797 16.1445 false true false A 1ffa6f58-ef3b-4ae1-8a4a-8053443dd2b5 true false 0 0 0 0 0 0 380.6797 36.1445 29 20 380.6797 36.1445 false true false B 9277e746-4813-4266-ae47-33ccd51fb141 true false 0 0 0 0 0 0 380.6797 56.1445 29 20 380.6797 56.1445 false true false C 5a69e7d9-cba5-485b-bd01-d639c2b5e31f true false 0 0 0 0 0 0 380.6797 76.1445 29 20 380.6797 76.1445 false true false D eea8ad4d-b3df-4794-a8e1-2f8a56e9225d true false 0 0 0 0 0 0 380.6797 96.1445 29 20 380.6797 96.1445 false true false ac2bc2cb-70fb-4dd5-9c78-7e1ea97fe278 Geometry Geo cd38c9bf-6a0c-420b-b1a4-0c858e425843 true false 1 1ffa6f58-ef3b-4ae1-8a4a-8053443dd2b5 0 0 436.2 37.10001 60 20 436.2 37.10001 60 20 436.2 37.10001 false true false 59e0b89a-e487-49f8-bab8-b5bab16be14c Panel Panel a46eec69-b3c1-4ba0-9843-af331dd9a19f true false 0 0 must define a convex polygon. select in order (left to right or right to left). true 0 false 11 53 218 41 13 54 214 39 11 53 false true false Courier New 8 false false 59e0b89a-e487-49f8-bab8-b5bab16be14c Panel Panel debc4755-20ab-465d-add9-ff5591979c7a true false 0 0 select the vornoi sites. true 0 false 10 5 216 20 12 6 212 18 10 5 false true false Courier New 8 false false