9

I'd suggesting googling for bounding volume hierarchies (BSP tree in particular). Given your point cloud, you can find a plane that splits it into two equal subclouds. Then when you need to find the collection of points that are within some radius R of a test point, you can first compare your test point to that plane, and if it's height above it is more than ...


7

There are several data structure for storing data that preserves information about position and proximity; there by allowing fast nearest neighbor(s) determination. In particular R-trees (and specialized forms like R*-trees) and X-trees. Lots of choices that are optimized for slightly different uses. Choosing a R*-tree rather than a naive nearest neighbor ...


5

This is very similar to one of the biggest challenges in the field of molecular dynamics—computing all of the pairwise interactions between nonbonded particles. There, we use cell lists (or neighbor lists) to help us figure out what's nearby; for this application, the cell list is probably the easier algorithm to use: Divide the box into a series of cells....


4

What you are asking is not possible, because you cannot order all cells in such a way that neighbors are always in a continuous range. Suppose we try to construct continuous neighbor lists in 3D. Each interior cell $C_i$ has six neighbors, so it should appear six times in a neighbor list. The only way to construct six continuous neighbor list is as follows: ...


4

You should definitely check K-D trees and octrees which are the methods of choice for point sets (while BSPs are for general objects, and grids for more or less uniform densities). They can be very compact and fast, minimizing overhead in both memory and computation, and are simple to implement. When your points are more or less uniformly distributed (even ...


3

You should probably consider building the Delaunay triangulation (well, its 3D analogue). In 2D, that's a special triangulation of the data points that always contains the nearest neighbor. The same holds in 3D, but with tetrahedra. You can build once and for all the triangulation, and then search for the nearest neighbor directly in the triangulation. I ...


3

The Haversine formula is really the best way to calculate distances on the Earth unless you have outstanding accuracy concerns. The next step passed the Haversine involves taking into account that the Earth is not a sphere but ellipsoidal and which involves a much more expensive computation. There's a good page with some embedded javascript at http://www....


3

I will summarize a couple of possibilities: As a baseline, I would begin with a Hough transform kind of approach: Iterative Hough Transform for Line Detection in 3D Point Clouds Christoph Dalitz, Tilman Schramke, Manuel Jeltsch There is also an online demo as well as source code. Here is another paper of the same Hough-approach: Hough Parameter ...


2

You may interpret both images as individual clustering problems: You can then calculate an a posteriori probability of beeing marked/ blood vessels. In case both images are properly aligned, you may now calculate a distance measure between the two matrices of a posteriori probabilities. A common distance measure is the Kullback-Leibler divergence.


1

When the points belong to more than one curve, it will first be necessary to cluster them into curves. A possible approach is described together with a reference implementation in Dalitz, Wilberg, Aymans: TriplClust: An Algorithm for Curve Detection in 3D Point Clouds. IPOL 2019.234 (2019) When your points have an implicit parameter representing an ...


1

If your data is indexed, I'm not sure if a 3rd party algorithm would perform much faster than the ones already included in mongoDB. According to your link, Changed in version 2.2.3: Applications can use $box without having a geospatial index. However, geospatial indexes support much faster queries than the unindexed equivalents. Before 2.2.3, a geospatial ...


1

I don't know much about using databases but it seems that a k-d tree would be a good way to do it. Look at the following link http://web.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf


Only top voted, non community-wiki answers of a minimum length are eligible