# [SciPy-User] Triangulate point cloud

10 messages
Open this post in threaded view
|
Report Content as Inappropriate

## [SciPy-User] Triangulate point cloud

 Hi all,I am looking for a way to traingulate a point cloud, in other words nodes to triangular.I tried scipy.spatial.Delaunay and ConvexHull, but for some reason it tends to connect nodes that are very far away.At this address you can find a good example of what I am looking for: https://paste.ee/p/RBank.As you can see I gave some points around the lateral face of a cylinder, the problems are- it connects nodes that are on the opposite side of the cylinder- if alseo connect nodes that are on the two front face of the cylinderThis is just a simple example, I am trying to triangulate a more complex point cloud.So in my opinion the perfect solution would be to define the max distance between nodes that can be connected. Best regards _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 Hi Vasco,Another possible option is vtk's Delaunay3D method. I used this a long time ago when it was one of the only options I could find that could reliably triangulate points on the surface of a sphere. It has a couple of parameters you can fiddle with to affect its behaviour:http://docs.enthought.com/mayavi/mayavi/auto/example_delaunay_graph.htmlGaryOn 12 February 2016 at 06:23, Vasco Gervasi wrote:Hi all,I am looking for a way to traingulate a point cloud, in other words nodes to triangular.I tried scipy.spatial.Delaunay and ConvexHull, but for some reason it tends to connect nodes that are very far away.At this address you can find a good example of what I am looking for: https://paste.ee/p/RBank.As you can see I gave some points around the lateral face of a cylinder, the problems are- it connects nodes that are on the opposite side of the cylinder- if alseo connect nodes that are on the two front face of the cylinderThis is just a simple example, I am trying to triangulate a more complex point cloud.So in my opinion the perfect solution would be to define the max distance between nodes that can be connected. Best regards _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 HelloIn addition to the already suggested ways of doing this:1) If you don't have a prohibitively large dataset (a few hundred thousand points), you can evaluate their inter-point distance and then use that one to establish a threshold. If you do a histogram on point distance you will see clearly the bunches of points that are closely to each other and the bunches, or clusters, of points that are further apart. You can then determine the distance threshold that will exclude surfaces across the cylinder.2) Another way I have found to do this is to use this plugin: http://blenderartists.org/forum/showthread.php?241950-A-Script-to-Skin-a-Point-Cloud-(for-Blender-2-6x-or-Later) for blender. It is really doing a good job and once your point cloud in in Blender you can use other tools to improve your mesh. In my case, I wrote a very simple script in Python to package my point cloud into a VRML pointset (http://www.c3.hu/cryptogram/vrmltut/part5.html) which was the easiest way in to import it to Blender.Hope this helps.All the bestAAOn Thu, Feb 11, 2016 at 11:35 PM, gary ruben wrote:Hi Vasco,Another possible option is vtk's Delaunay3D method. I used this a long time ago when it was one of the only options I could find that could reliably triangulate points on the surface of a sphere. It has a couple of parameters you can fiddle with to affect its behaviour:http://docs.enthought.com/mayavi/mayavi/auto/example_delaunay_graph.htmlGaryOn 12 February 2016 at 06:23, Vasco Gervasi wrote:Hi all,I am looking for a way to traingulate a point cloud, in other words nodes to triangular.I tried scipy.spatial.Delaunay and ConvexHull, but for some reason it tends to connect nodes that are very far away.At this address you can find a good example of what I am looking for: https://paste.ee/p/RBank.As you can see I gave some points around the lateral face of a cylinder, the problems are- it connects nodes that are on the opposite side of the cylinder- if alseo connect nodes that are on the two front face of the cylinderThis is just a simple example, I am trying to triangulate a more complex point cloud.So in my opinion the perfect solution would be to define the max distance between nodes that can be connected. Best regards _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 Thanks. I will try mayavi and blender. Regarding the suggestione number 1 of AA do you have an example. _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 Off the top of my head:from scipy.spatial import distancefrom scipy.stats import histogramfrom scipy import nan`#p is your data structures that holds all of your data points, it can be n-dimensional of course.``#Here, it is a list of tuples, suggesting a simple 2D problem.``p=[(2,2),(5,5),(1,7),(2,3)]``#Get the unique distances``#If you have a huge amount of points, this is the point where the program might take a little bit of time until it comes back with the results.``d = distance.pdist(p)``#Get the distance matrix, this is always a square kxk matrix, where k is the index of a point in p``#If you have a huge amount of points, this is the bit where the program a) takes a long time to finish, b) crashes because of memory issues. For very large problems, you can upload your points to a database server and run a query for it to calculate your distance matrix. So, you can hire a powerful EC2 (for example) instance and run your query there or run the query over a distributed configuration. Both options aiming to improve speed and capacity.``Q = distance.squareform(d)``#The d matrix are the unique values of the upper (or lower) diagonal part of Q. Q is much easier to work with (in terms of referencing), if you want the distance between any two point m,n you just Q[m,n].``#Here is the Euclidean Q for the above p.````#array([[ 0. , 4.24264069, 5.09901951, 1. ], # [ 4.24264069, 0. , 4.47213595, 3.60555128], # [ 5.09901951, 4.47213595, 0. , 4.12310563], # [ 1. , 3.60555128, 4.12310563, 0. ]])#Get the histogram of thatH = histogram(d); #This could also be done on Q, by reshaping it to a 1 x (M*N) vector but if you have a huge number of points it is not advisable. You can see how quickly this eats up memory.#This can also be done with matplotlib.pyplot.hist(d) which will also draw the histogram for you besides returning it.If you want to free up some memory to fit even more data to your problem, you can round everything to a few decimal places and use integers. So, for example, int(round(5.678928527817364 * 10000))==56789, which is a nice little unsigned integer of 2 bytes instead of a double of 8 bytes. Of course this assumes that 4 decimals is accurate enough. To get back to your data range, just divide by 10000 and assign to (float or double).Hope this helps.All the bestAA```On Fri, Feb 12, 2016 at 1:24 PM, Vasco Gervasi wrote:Thanks. I will try mayavi and blender. Regarding the suggestione number 1 of AA do you have an example. _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 Sorry but i didn't understand how to use the histogram [H] to find the connectivity. Thank you very much. _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 Ah, the above code will not help you connect the right points, this is still a triangulation problem. The above code will help you determine the distance threshold you need to use (in other tools or algorithms, including the surface plugin of blender) to avoid artifacts such as those that you are describing in your original question (i.e. surfaces across a cylinder). Otherwise, you would have to estimate this with trial and error.All the bestAAOn Fri, Feb 12, 2016 at 3:00 PM, Vasco Gervasi wrote:Sorry but i didn't understand how to use the histogram [H] to find the connectivity. Thank you very much. _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 You also have this code : https://github.com/pearu/pyvtkThe doc has weaknesses, but I could make it work for my problem. Best, -- François Boulogne. http://www.sciunto.orgGPG: 32D5F22F _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Triangulate point cloud

 François could you share an example for pyvtk, because examples in https://github.com/pearu/pyvtk/tree/master/examples do not work.Thanks _______________________________________________ SciPy-User mailing list [hidden email] https://mail.scipy.org/mailman/listinfo/scipy-user