Negative coordinates

[normen662]

Hi David,

I think the acceptable ranges for coordinates are 0..2^bits (for point to Hilbert value conversions). Unfortunately, I have to deal with full java longs -2^63 ... 2^63-1. I was thinking of preprocessing these numbers (by shifting them into the positive (adding 2^63 to each) and then doing the conversion to a Hilbert value in code specifically adopted to use BigInteger to also support higher numbers of bits (64 in my cases) at the expense of worse performance). Short question: Do you see an easier/better way to do this? Ideally I would still like to call methods in this library.

(Note that I kind of can do this in a better way for 2 dimensions; however, it eludes me how to generalize that to n dimensions).

[davidmoten]

~~I don't understand why you "have to deal with full java longs". Why is that? You already have Hilbert index values from some other product? How will this extra resolution on the Hilbert index help you? Can you describe your use case?~~

Sorry, I've read your question wrongly. Coordinates are in range -2^63..2^63-1. Your use case is still useful but I'll make some guesses. If your coordinates are (x, y) then construct a hilbert index that maps (x/2+2^62, y/2+2^62) to a Hilbert index using 63 bits. When you conversely get a coordinate from the index then you multiply the ordinates by 2 and subtract 2^63 to get your original range. Then use appropriate criteria on the returned coordinates to filter them (as though you had an index of 64 bits). Does that help?

[normen662]

Thanks for the answer! My use case in fact uses coordinates in range -2^63..2^63-1. What I ended up doing which I think does work is the following:

1. shift the coordinates to a range that is between 0..2^64-1. Even though I still use java long the bits correspond to an unsigned long.
2. I extracted the code in HilbertCurve that participates in mapping the coordinates to Hilbert value to essentially be able to work over unsigned long coordinates (sorry for the C terminology) (toIndex() and transposedIndex()). Effectively I made these functions support 64 bit resolution without making them slower by making everything BigInteger operations. The changes are minute as only very little of the logic depends on the regular 2-complement representation thus the coordinates are fully treated as a 64-bit number (which is unsigned). I am not sure if it would be desirable to support 64 bit resolution in general (and in such a weird way) and if the other code in HilbertCurve can be adapted as well.

Here is the adapted code: https://gist.github.com/normen662/0d312d1424adb70f274d95bb16734aac

I am not sure if that does the same as what you were suggesting. Maybe you find the angle interesting. I would certainly rather like to call your library methods instead of creating a Frankenstein out of your code.

[normen662]

Oh right: The code to shift the coordinates:

static long shiftCoordinate(long coordinate) {
        return coordinate < 0
               ? (Long.MAX_VALUE - (-coordinate - 1L))
               : (coordinate | (1L << 63));
    }

[davidmoten]

I'm still in the dark about why don't just divide your coordinates by two before mapping to the hilbert index and the reverse when mapping hilbert index value to the coordinates. If necessary at that point you can do a further filter appropriate to your search (the nature of which I'm curious about too).

[normen662]

By dividing the coordinate by two I would lose resolution, unless there is a misunderstanding on my part. I need a bijective function f:(java long, java long) --> BigInteger with Hilbert curve-like properties. As far as I can tell the code (when using a bit resolution of 63 bits) can only do so correctly from 0..2^63-1. There is currently no way to use a bit resolution of 64 bits which I would need to map each point consisting of java long coordinates to a Hilbert value bijectively.

Maybe I am gettin wrong what you are suggesting, but by dividing them by two I would assign e.g. (0, 0), (0, 1), (1, 0), and (1, 1) the same Hilbert value which would not be reversible.

[davidmoten]

Yes but it depends on how you are using the Hilbert index. If you are using it for a proximity search for instance then you just do the refinement on the results by checking with the proximity criterion all the coordinates that correspond to the divided-by-2 result (combinations (2x, 2y), (2x +1,2y),(2x, 2y+1), (2x+1, 2y+1) in 2d for example).

[normen662]

Hi David, thank you for all the suggestions! I don't think I can avoid having those 64 bits of resolution. Since my adapted code can deal with that case I will use that for the time being. Please feel free to close.