3

Is there an algorithm that for a given 2d position finds the closest point on a 2d polyline consisting of n - 1 line segments (n line vertices) in constant time? The naive solution is to traverse all segments, test the minimum distance of each segment to the given position and then for the closest segment, calculate the exact closest point to the given position, which has a complexity of O(n). Unfortunately, hardware constraints prevent me from using any type of loop or pointers, meaning also no optimizations like quadtrees for a hierarchical lookup of the closest segment in O(log n).

I have theoretically unlimited time to pre-calculate any datastructure that can be used for a lookup and this pre-calculation can be arbitrarily complex, only the lookup at runtime itself needs to be in O(1). However, the second constraint of the hardware is that I only have very limited memory, meaning that it is not feasible to find the closest point on the line for each numerically possible position of the domain and storing this in a huge array. In other words, the memory consumption should be in O(n^x).

So it comes down to the question how to find the closest segment of a polyline or its index given a 2d position without any loops. Is this possible?

Edit: About the given position … it can be quite arbitrary, but it is reasonable to consider only positions in the closer neighborhood of a line, given by a constant maximum distance.

mOfl
  • 478
  • 3
  • 14
  • Your "line" is more commonly referred to as a polyline, which reduces some confusion. – Jim Mischel Jan 14 '16 at 18:03
  • You say that memory consumption should be in O(n^x). I get that `n` is the number of vertices. What is `x`? What is a reasonable range for `n` and `x`? What's the range of your world's `x` and `y`? For example, do I need to support queries for position `[0,0]`, as well as for `[987654321,123456789]`? Let's get *all* the constraints defined. – Jim Mischel Jan 14 '16 at 18:19

3 Answers3

10

Create a single axis-aligned box that contains all of your line segments with some padding. Discretize it into a WxH grid of integer indexes. For each grid cell, compute the nearest line segment, and store its index in that grid cell.

To query a point, in O(1) time compute which grid cell it falls in. Lookup the index of the nearest line segment. Do the standard O(1) algorithm to compute exactly the nearest point on the line.

This is an O(1) almost-exact algorithm that will take O(WH) space, where WH is the number of cells in the grid.

For example, here is the subdivision of the space imposed by some line segments:

enter image description here

Here is a 9x7 tiling of the space, where each color corresponds to an edge index: red (0), green (1), blue (2), purple (3). Notice how the discretizing of the space introduces some error. You would of course use a much finer subdivision of the space to reduce that error to as much as you want, at the cost of having to store a larger grid. This coarse tiling is meant for illustration only.

enter image description here

You can keep your algorithm O(1) and make it even more almost-exact by taking your query point, identifying what cell it lies in, and then looking at the 8 neighboring cells in addition to that cell. Determine the set of edges that those 9 cells identify. (The set contains at most 9 edges.) Then for each edge find the closest point. Then keep the closest among those (at most 9) closest points.

In any case, this approach will always fail for some pathological case, so you'll have to factor that into deciding whether you want to use this.

Timothy Shields
  • 75,459
  • 18
  • 120
  • 173
  • You say to create axis-aligned boxes, but your image shows areas that aren't axis-aligned. Your proposed solution doesn't work with axis-aligned boxes, although it does reduce the actual amount of work needed in the average case. And if your boxes aren't axis-aligned, you still need to do point-in-polygon tests, which makes the solution not O(1). – Jim Mischel Jan 14 '16 at 18:09
  • @JimMischel You are misunderstanding my suggestion. The picture I drew is *not* discretized, it was just meant for illustration purposes. You would overlay a grid on my picture and in each cell of the grid write the edge index that overlaps most with it. I will update with an additional figure to make this clearer. – Timothy Shields Jan 14 '16 at 19:02
  • 2
    I see. Now I understand your "O(1) *almost-exact*" comment. Basically, you guarantee some level of accuracy, but not perfection. Accuracy increases with the amount of memory used. Seems reasonable, absent pathological data. – Jim Mischel Jan 14 '16 at 20:17
  • @JimMischel Definitely pathological data will destroy this approach. The key here is that it is a truly O(1) complexity algorithm with this data structure. – Timothy Shields Jan 14 '16 at 21:48
  • Might a layered approach with a quadtree (implemented as a n-dimensional array) be possible for a `O(log W + log H)` approach? Specifically you start with a 2x2, then mathematically (the dashed lines you drew work well for this) determine if all any point in each square is closer to a different line, if so, that square can be broken up into smaller squares, if not, then there's no need. Basically, you use binary grid coordinates. This way you can increase resolution of the grid only where it's really needed. Admittedly there are only about 9 areas in your example that would benefit from this. – Nuclearman Jan 15 '16 at 04:15
  • @Nuclearman Why would you not just use a normal spatial partition data structure for everything in that case? The only reason I presented this approach was because the asker specifically said he wanted O(1) complexity. – Timothy Shields Jan 15 '16 at 04:19
  • True, matter of a speed VS precision. Though the final question asked suggests that OP may have been more interested in *if* it can be done under those constraints (OP seems to think a quadtree requires pointers to work) than how fast. `O(1)` seemed more like an ideal for the OP, but it's only an ideal due to precision concerns. – Nuclearman Jan 15 '16 at 04:28
  • Thanks for elaborating this idea and discussing it. As mentioned in the question, the optimal solution would be a grid in which each cell corresponds to a numerically possible value of the given datatype. Having a coarser grid introduces misclassifications, especially when subsequent line segments can be arbitrarily short. I don't like that, but it seems like this is the only option. – mOfl Jan 15 '16 at 11:41
0

You can find the closest geometric point on a line in O(1) time, but that won't tell you which of the given vertices is closest to it. The best you can do for that is a binary search, which is O(log n), but of course requires a loop or recursion.

If you're designing VLSI or FPGA, you can evaluate all the vertices in parallel. Then, you can compare neighbors, and do a big wired-or to encode the index of the segment that straddles the closest geometric point. You'll technically get some sort of O(log n) delay based on the number of elements in the wired-or, but that kind of thing is usually treated as near-constant.

comingstorm
  • 25,557
  • 3
  • 43
  • 67
-1

You can optimize this type of search using an R-Tree which is a general purpose spatial data structure support fast searches. It's not a constant time algorithm; it's average case is O(log n).

You said that you can pre-calculate the data structure, but you could not use any loops. However is there some limitation that prevents any loops? Arbitrary searches are not likely to hit an existing datapoint so it must at least look left and right in a tree.

This SO answer contains some links to libraries:

Java commercial-friendly R-tree implementation?

Community
  • 1
  • 1
John Scattergood
  • 1,032
  • 8
  • 15
  • Thanks for the input, I know about R-Trees. Unfortunately, the traversal of an R-Tree is not possible in my case. Otherwise, it would be the tool of choice. – mOfl Jan 14 '16 at 17:39