"3 closest neighbors" pyramids?
Does anyone have a script, possibly python, that:
- given an arbitrary point cloud (I'm assuming a lot of points, 1000+)
- for each point
- Find the 3 closest points to it
- Create a 4 sided polygon with those points
- output as stl or "Openscad polyhedron format"**
?
I worked out an algorithm that I think is Order (N^2)/2, but a friend
pointed me to a paper that says that in 2d, you can do this in Order N log N.
https://cp-algorithms.com/geometry/nearest_points.html
I'm not really following this proof, nor am I a python programmer.
** "Openscad polyhedron format" would be something like defining an array of the
points, and an array of the polygons in the correct rotation. This could
be included in an OpenSCAD project and looped through.
There is a function in the BOSL2 library that finds the k nearest points in
a cloud to a given set of points. See documentation at:
https://github.com/revarbat/BOSL2/wiki/vectors.scad#function-vector_nearest
I can't say what it's complexity is but it uses a search tree.
Em qua., 11 de mai. de 2022 10:56, Bryan Lee leebc11@acm.org escreveu:
Does anyone have a script, possibly python, that:
-
given an arbitrary point cloud (I'm assuming a lot of points,
1000+)
-
for each point * Find the 3 closest points to it * Create a 4 sided polygon with those points -
output as stl or "Openscad polyhedron format"**
?
I worked out an algorithm that I think is Order (N^2)/2, but a friend
pointed me to a paper that says that in 2d, you can do this in Order N log
N.
https://cp-algorithms.com/geometry/nearest_points.html
I'm not really following this proof, nor am I a python programmer.
** "Openscad polyhedron format" would be something like defining an array
of the
points, and an array of the polygons in the correct rotation. This could
be included in an OpenSCAD project and looped through.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
I took a cursory look at your reference. The algorithm it presents aim to
find just the nearest pair of points in the cloud. You need much more than
that and should expect a higher complexity.
Em qua., 11 de mai. de 2022 12:04, Ronaldo Persiano rcmpersiano@gmail.com
escreveu:
There is a function in the BOSL2 library that finds the k nearest points
in a cloud to a given set of points. See documentation at:
https://github.com/revarbat/BOSL2/wiki/vectors.scad#function-vector_nearest
I can't say what it's complexity is but it uses a search tree.
Em qua., 11 de mai. de 2022 10:56, Bryan Lee leebc11@acm.org escreveu:
Does anyone have a script, possibly python, that:
-
given an arbitrary point cloud (I'm assuming a lot of points,
1000+)
-
for each point * Find the 3 closest points to it * Create a 4 sided polygon with those points -
output as stl or "Openscad polyhedron format"**
?
I worked out an algorithm that I think is Order (N^2)/2, but a friend
pointed me to a paper that says that in 2d, you can do this in Order N
log N.
https://cp-algorithms.com/geometry/nearest_points.html
I'm not really following this proof, nor am I a python programmer.
** "Openscad polyhedron format" would be something like defining an array
of the
points, and an array of the polygons in the correct rotation. This could
be included in an OpenSCAD project and looped through.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
I have a problem with your description of the task.
A point cloud is a representation of points in 3d space. I guess
arbitrary point cloud means the points are not on a regularly spaced x/y
plane, and can be in any order. A polygon is a 2d object, the 3 closest
points to one of the cloud points means what? closest considering xy
plane only?
You will need to ensure that the four points form an area (if 2d-
volume if 3d) and are not in a straight line, depending on how the
points are derived, this may not be a problem.
stl and polyhedron are 3d object definitions, polygon is 2d.
On 11/05/2022 14:55, Bryan Lee wrote:
Does anyone have a script, possibly python, that:
- given an arbitrary point cloud (I'm assuming a lot of points, 1000+)
- for each point
- Find the 3 closest points to it
- Create a 4 sided polygon with those points
- output as stl or "Openscad polyhedron format"**
?
I worked out an algorithm that I think is Order (N^2)/2, but a friend
pointed me to a paper that says that in 2d, you can do this in Order N log N.
https://cp-algorithms.com/geometry/nearest_points.html
I'm not really following this proof, nor am I a python programmer.
** "Openscad polyhedron format" would be something like defining an array of the
points, and an array of the polygons in the correct rotation. This could
be included in an OpenSCAD project and looped through.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
On Wed, May 11, 2022 at 11:16 AM Raymond West raywest@raywest.com wrote:
I have a problem with your description of the task.
...
A polygon is a 2d object, the 3 closest
points to one of the cloud points means what?
I'm assuming they meant polyhedron (specifically a tetrahedron) since the
subject line mentions "pyramids".
Here is my solution using the aforementioned BOSL2 functions:
include <BOSL2/std.scad>
$fn=8;
num_points = 1000;
k_nearest = 4; // hull the nearest k points (including each point itself),
4 for tetrahedron. try larger numbers for more solid results
seed = 1000;
size = 10;
points = list_to_matrix(rands(-size,size, num_points*3, seed=seed), 3);
tree = vector_search_tree(points);
search_ind = [for(p=points) vector_nearest(p, k_nearest, tree)];
for(i=idx(points)) {
//%translate(points[i]) sphere(0.1);
// hull trick to create tetrahedron with correct face orientations
hull() polyhedron(select(points, search_ind[i]), faces=[[each
idx(search_ind[i])]]);
}
Not sure if you're expecting this method to produce a solid "skin" for a
point cloud from scanned data or something, but from my test on uniform
distribution of points, it seems to create a spiky sort of open celled foam
instead (which tends to not be 2-manifold either).
[image: tetras.png]
