Stack Overflow
Stack Overflow

Questions tagged [hilbert-curve]

The Hilbert curve is a space-filling curve that preserves locality better than most mappings from one to many dimensions. Originally conceived in two dimensions, it can be generalized to any number of dimensions. Hilbert curves are useful in optimizing database range queries over multiple attributes, such as geospatial queries, and have many other uses.

67 questions
55
votes
7 answers

Mapping N-dimensional value to a point on Hilbert curve

I have a huge set of N-dimensional points (tens of millions; N is close to 100). I need to map these points to a single dimension while preserving spatial locality. I want to use Hilbert space-filling curve to do it. For each point I want to pick…
Alexander Gladysh
  • 39,865
  • 32
  • 103
  • 160
22
votes
3 answers

Hilbert sort by divide and conquer algorithm?

I'm trying to sort d-dimensional data vectors by their Hilbert order, for bulk-loading a spatial index. However, I do not want to compute the Hilbert value for each point explicitly, which in particular requires setting a particular precision. In…
Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194
19
votes
3 answers

Algorithm for generating a 3D Hilbert space-filling curve in Python

I'd like to map points in a RGB color cube to a one-dimensional list in Python, in a way that makes the list of colors look nice and continuous. I believe using a 3D Hilbert space-filling curve would be a good way to do this, but I've searched and…
user2010460
  • 193
  • 1
  • 1
  • 4
18
votes
3 answers

Implementing a Hilbert map of the Internet

In the XKCD comic 195 a design for a map of the Internet address space is suggested using a Hilbert curve so that items from a similar IP adresses will be clustered together. Given an IP address, how would I calculate its 2D coordinates (in the…
Martin
  • 12,469
  • 13
  • 64
  • 128
8
votes
4 answers

What is the most efficient algorithm/data structure for finding the smallest range containing a point?

Given a data set of a few millions of price ranges, we need to find the smallest range that contains a given price. The following rules apply: Ranges can be fully nested (ie, 1-10 and 5-10 is valid) Ranges cannot be partially nested (ie, 1-10 and…
user1102018
  • 4,369
  • 6
  • 26
  • 33
8
votes
2 answers

Mapping Hilbert values to 3D points

I have a set of Hilbert values (length from the start of the Hilbert curve to the given point). What is the best way to convert these values to 3D points? Original Hilbert curve was not in 3D, so I guess I have to pick by myself the Hilbert curve…
Alexander Gladysh
  • 39,865
  • 32
  • 103
  • 160
6
votes
8 answers

"Absolute" string metric

I have a huge (but finite) set of natural language strings. I need a way to convert each string to a numeric value. For any given string the value must be the same every time. The more "different" two given strings are, the more different two…
Alexander Gladysh
  • 39,865
  • 32
  • 103
  • 160
5
votes
1 answer

How can I improve perfomace of Hilbert scan of image?

This method of image scanning based on Hilbert Curve. Curve looks like (from 1 to 6 order): It can be used for image scan. So, for example, my code for 3-order curve is: Hilbert=[C(1,1) C(1,2) C(2,2) C(2,1) C(3,1) C(4,1) C(4,2) C(3,2) C(3,3) C(4,3)…
Golovach Grach
  • 158
  • 2
  • 2
  • 16
4
votes
2 answers

How to flatten 2d matrix (n x n) into 1d array in order of Hilbert Curve?

I want to flatten a 2d (n x n) matrix in python into a 1d array, but instead of row major order, I want it to follow the ordering of hilbert curve? For example, if my input data is 2x2 --> data[[a b] [c d]] I want the output to be 1x4 --> …
Penny Xu
  • 49
  • 2
4
votes
2 answers

Indexing based on Peano-hilbert curve?

I have a x,y,z 3D points stored in MySQL, I would like to ask the regions, slices or point neighbours. Are there way to index the points using Peano-Hilbert curves to accelerate the queries? Or are there more efficient way to store the 3D data in…
Arman
  • 4,566
  • 10
  • 45
  • 66
3
votes
1 answer

Use of Hilvert Curve to query a rectangular area and see if it overlaps other rectangles

I am looking for a method that can help me in project I am working on. The idea is that there are some rectangles in 2d space, I want to query a rectangular area and see if it overlaps any rectangle in that area. If it does, it fails. If it doesn't,…
nico.user
  • 483
  • 2
  • 5
  • 15
3
votes
2 answers

3d Hilbert Curve for a sparse geometry

I have a 3d array containing the non-cubic bounding box of a sparse geometry. The array geometry[x][y][z] contains the value 0 if (x,y,z) is part of the computational domain and otherwise 1. In an attempt to reorder computations I would like to…
kyrre
  • 626
  • 2
  • 9
  • 24
3
votes
1 answer

How to convert between Hilbert Curve QuadTree and S2 Geometry CellId

Problem Let's say I know the Hilbert Curve Face and Quadtree, such as 4/032212303102122 (face 4, level 15). Or perhaps I know the S2 Geometry CellId, such as 9749618424903892992. How can I convert from the one to the other? Application (this is the…
coolaj86
  • 74,004
  • 20
  • 105
  • 125
3
votes
1 answer

How to represent image or audio through vectors for cosine similarity?

I know that cosine similarity can be used to measure how two images or audios are similar. But I don't understand how an image can be represented as a N-dimensions vector. For a text document d, each i-th dimension represents the term t_i, and it's…
justHelloWorld
  • 6,478
  • 8
  • 58
  • 138
3
votes
0 answers

Convert a rectangle to ranges of Hilbert numbers

When spatial data is represented using Hilbert numbers, a rectangular range is mapped to multiple ranges of Hilbert numbers. Is there any quick way to find this mapping without going through every cell the given rectangle, R, overlaps with? I can…
user1922346
  • 31
  • 2
1
2 3 4 5