1
$\begingroup$

I have a (2D) point cloud of reasonable size (say some thousands of points) and a set of (2D) polylines also of a reasonable size. I want to assess the discrepancies between the two geometries and for this I want to find the nearest point to every segment.

This can be solved with the Voronoi diagram of the segments followed by a point location in the planar subdivision it defines. The first construction will take optimal time $O(s\log s)$, and the subsequent search, optimal time $O(p\log s)$.

Anyway, the Voronoi diagram of segments is not an easy construction, nor is the search in the subdivision. So I am after a simpler method, possibly with heuristics that lead to a similar complexity. Can you point me to such methods that would be known ?

In case there is a nice solution to the converse problem (nearest segment to every point), I can work with it as well.

Improve this question
$\endgroup$
4
  • $\begingroup$ Binary space partitioning and quad trees are options, but they are not trivial to implement. If the points and segments are well distributed I would recommend spatial hash grids, that is dividing the space into buckets, putting the points into the buckets and then look through all points in the buckets a given segment touches. If these buckets are empty one probably has to continue to search radially. $\endgroup$
    – plshelp
    Commented Jun 26, 2023 at 16:53
  • $\begingroup$ @plshelp: is a spatial hash grid the same as a kD-tree, or just an orthogonal grid ? $\endgroup$
    – user16034
    Commented Jun 26, 2023 at 16:58
  • $\begingroup$ Just an orthogonal grid; you divide the space into grid cells with size $\Delta x, \Delta y$ and use $i = x/\Delta x,j = y /\Delta y$ as indices into a hash-map. There are some videos about how game developers use it on youtube. $\endgroup$
    – plshelp
    Commented Jun 26, 2023 at 18:01
  • $\begingroup$ @plshelp: understood. $\endgroup$
    – user16034
    Commented Jun 26, 2023 at 18:49

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.