It’s days that I’m trying to implement a constrained Delaunay triangulation in Grasshopper via Python scripting without success.
What I need to do is creating a triangulated mesh from a point cloud but sometimes I need to give the exact position of edges as input, not only the vertices.
On the contrary, normal Delaunay triangulation creates the shortest edge possible.
Since importing libraries that do that from pip in Rhino Python didn’t give me any result (I’m not expert in python scripting I must say maybe you have suggestions for that), so I think I’m going to try implementing it manually but it requires heavy loops, and I worry this effort would result in a very inefficient algorithm.
one way could be dividing your input edges into points and add these points into the pointcloud you feed in the delaunay mesh (with N of the divide component high enough to make delaunay work properly) mesh form pointcloud + edges.gh (8.0 KB)
It’s a 2D planar cloud that has at most some thousands of points, but it’s variable it might have one order of magnitude more or less, depending on the case.
If you post a sample point cloud in a rhino file I am sure someone will give you better ideas. This will involve manipulating the data tree using some logic to access specific points needed easily. Data tree manipulation is important to understand in GH.
Thanks for the idea, I already tried this workaround and it works most of the times, but in some specific cases it does not when special simmetries occur and when I need to reduce as much as possible the density of the mesh.
I sure will as soon as I reach a laptop, but the method I’m trying to implement should work with any case with very dense and very coarse point clouds that’s why I didn’t post any before. I’ve already tried many workarounds but in the end I think the only solution robust enough for me is the CDT method, but it’s very complex to implement in grasshopper :(.
CDT.3dm (826.9 KB)
Here’s an example file to play with.
This is the logic I’d like to implement, I think it’s the most robust and simple that exists for now, but as you can see it requires a lot of loop and topology tracking which is not really comfortable for grasshopper.
Ok, this is something my skill sets will not help with. I would be looking to re-organize the points using his git hub code, but I am sure one of the guru’s will dig into this. You could include that in python code in GH.
hey wait a second! Looking at my image I might have had an idea which I don’t see why it shouldn’t work…I maybe can replicate something similar to a CDT in grasshopper by simply making a normal dealunay triangulation and erase the faces that collide with the edges I want to constrain and extrude the hole boundary to one of the two end points of the edge!
Maybe I’m missing something important But if this works looks doable!
Anyway this wouldn’t have worked, in some case faces might have overlapped. and loops would be necessary anyway in order to address cases where multiple constrained edges ended in the same vertex.
I got a weird error, when I use polylines that are instanced from rhino geometry it works perfectly, when I use lines and polylines that comes from a script it outputs an invalid mesh, and the weird thing is that if I bake the same exact polylines from the script and I reinput them as rhino referenced polylines it works again. Any ideas why this happens?
Never mind, with an easier algorithm it works, so there might be some weird stuff happening in the bigger algorithm, I guess I’ll need to redo it all from scratch. Thank you very much to all of you!
Sorry in this last case I could not, the algorithm is part of a broader research and it is very very big and chunky and many people worked on it, and it was very hard to extract only a subpart for testing. But I rewrote it from scratch and it works now! your contribution was super helpful thanks a lot!
about your last question
I think the CDT method always find the least narrow triangles possible, if you want to avoid that just add a new edge to constrain it wherever you want.
But if this works looks doable!
