4 ms·

> a vehicle with a Hilbert Curve position of 0.34 is really close to one with 0.35 and really far from one with 0.89 But points with a large difference in thei

by tromp 3y ago

> a vehicle with a Hilbert Curve position of 0.34 is really close to one with 0.35 and really far from one with 0.89 But points with a large difference in their single curve coordinate can be either far apart or close together. E.g. on this 16 point Hilbert curve __. .__ __| |__ | __ | |__| |__| the '.' marked points at 1/16th and 15/16th along the curve are adjacent.

wolframhempel 3y ago
It's an important point. We've ended up using two Hilbert curves, rotated by 90 degrees to tackle this problem. If it is close on either, it is close in 2D space
- tromp 3y ago
  Interesting. So one might think that being close together in 2D space corresponds to being close on BOTH cartesian coordinates / EITHER Hilbert coordinate And that being far apart in 2D space corresponds to being far apart on EITHER cartesian coordinate / BOTH Hilbert coordinates But if we consider the two commas below which are close together in 2D space, we see they are far apart in any rotation of this Hilbert curve?! __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| ;__ __| | |__ __,__ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__|
- sp332 3y ago
  So you converted your 2D space into another 2D space?
- dwallin 3y ago
  As mentioned in other replies, this doesn't fully solve a lot of the cases. I think z order curves might actually be better here, they are slightly less accurate individually, but in a way that would seemingly minimize the worst case results when taking the minimum of the two. But at that point you are probably better off using a single z-order curve and using the coordinates to check the manhattan or Chebyshev distance using bitwise operations.
  - jandrewrogers 3y ago
    I would second the use of Z-order curves. Hilbert curves were famously known as more optimal on spinning disk in a specific context a few decades ago. Inertia has kept them top-of-mind even though modern systems do not have the problems Hilbert curves were better at solving and those curves are more complex to use than e.g. Z-order curves.

by tromp 3y ago

wolframhempel 3y ago

It's an important point. We've ended up using two Hilbert curves, rotated by 90 degrees to tackle this problem. If it is close on either, it is close in 2D space

tromp 3y ago
Interesting. So one might think that being close together in 2D space corresponds to being close on BOTH cartesian coordinates / EITHER Hilbert coordinate And that being far apart in 2D space corresponds to being far apart on EITHER cartesian coordinate / BOTH Hilbert coordinates But if we consider the two commas below which are close together in 2D space, we see they are far apart in any rotation of this Hilbert curve?! __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| ;__ __| | |__ __,__ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__|
sp332 3y ago
So you converted your 2D space into another 2D space?
dwallin 3y ago
As mentioned in other replies, this doesn't fully solve a lot of the cases. I think z order curves might actually be better here, they are slightly less accurate individually, but in a way that would seemingly minimize the worst case results when taking the minimum of the two. But at that point you are probably better off using a single z-order curve and using the coordinates to check the manhattan or Chebyshev distance using bitwise operations.
- jandrewrogers 3y ago
  I would second the use of Z-order curves. Hilbert curves were famously known as more optimal on spinning disk in a specific context a few decades ago. Inertia has kept them top-of-mind even though modern systems do not have the problems Hilbert curves were better at solving and those curves are more complex to use than e.g. Z-order curves.