Talk:Z-order curve

Cleanup

What about this page needs to be cleaned up? Hyacinth 10:43, 29 September 2006 (UTC)

The cleanup tag was put on a much earlier version. I will draw the tagger's attention to your query. Snottygobble 11:53, 29 September 2006 (UTC)

As the original tagger, I think that the clean-up tag could be removed. However, I would recommend that the figure on the right be reflected, so that the shape of the curves matches the example on the left. Perhaps a paragraph talking about "locality preservation" would be useful. Bluap 14:33, 29 September 2006 (UTC)

See note at <http://cap-lore.com/MathPhys/Zorder/>. The Z curve is discontinuous which would have disqualified it from the original category of space filling curves. Like those historical curves it is a function from the unit interval to the unit square and preserves Lebesgue measure. The connection is thus significant.

The .png file at <http://cap-lore.com/MathPhys/Zorder/155px-Zorder.png> may be suitable. I have not discovered how to send files to Wikipedia. Anyone may use it is they please; it is a modification of the current file. NormHardy 19:06, 26 December 2006 (UTC)

done Hermann.tropf 17:53, 2 February 2007 (UTC)

Sources

Article looks good overall. Needs sourcing, however. --Lendorien 15:54, 23 May 2007 (UTC)

More references provided as requested; facts in question can be found in Hanan Samet's book. I hope that's it. Tags removed. --Hermann.Tropf.

Hilbert curve difficult?

There is a claim in the article that position on the Hilbert curve is very hard to compute. Is that true? (That a patent does it in a complicated way doesn't necessarily imply that it really is hard, only that this is the best way the applicant came up with — and sometimes not even that!) My feeling is that it should suffice to

1. Gray-encode the x and y positions separately.
2. Interleave (i.e., Z-curve encode) the bit patterns of these two codewords.
3. Gray-decode the combined word.

At least this converges to a space-filling curve, and if binary-reflected Gray codes are used it should have the same locality properties as the Hilbert curve. Possibly there could be some problem with overflows (i.e., it being a nice curve, but only on a torus)… 81.231.34.61 (talk) 13:36, 20 July 2008 (UTC)

In multidimensions, special conditions must be met, see patent. What do you mean with „cray decode?“. What for?

"Difficult" applies specially to the BIGMIN calculation which is necessary for range searches in database applications. The patent is not cited to demonstrate the difficulty but to provide a detailed description and source code as well. --Hermann.tropf (talk) 16:32, 26 July 2008 (UTC).

Thinking about it a bit more: it works better to interleave the bits as yxxyyxxy... than as the Z-curve yxyxyxyx..., and at least the first steps comes out looking more like the Moore curve, but it all depends on which Gray codes one uses. 81.231.34.61 (talk) 15:40, 20 July 2008 (UTC)

Yes, of course bit interleaving can be done in various manners. The method described in Tropf/Herzog 81 applies to any interlacing scheme, see original text. What scheme to take may depend on the application (when data statistics depend on the dimension). In general the xyz xyz xyz… scheme is the right choice. --Hermann.tropf (talk) 16:32, 26 July 2008 (UTC).

What is the big O complexity of Hilbert curve computation? I mean the time to compute an index given (x, y, z) [random access to positions] and time to compute (x, y, z) given index - 1 [enumeration of positions]. Pathbuiltnow (talk) 07:32, 3 January 2011 (UTC)

"well reintrocuced"

Neither nearby z-values are always nearby in multidimensions, nor vice versa. With Hilbert curve, nearby Hilbert values are always nearby in multidimensions (but not vice versa, of course). So the Hilbert curve is better locality preserving (for example), so "well" is not extraneous. —Preceding unsigned comment added by Hermann.tropf (talk • contribs) 16:25, 26 July 2008 (UTC)

historical morton paper

I reintroduced the description of the 1966 Morton paper as it has given the curve its name and as it is very difficult to get (I had difficulties, I did even not get it from IBM directly). I tried it in a condensed manner, surely the description can be improved... --Hermann.tropf (talk) 16:42, 26 July 2008 (UTC).

reference to Lebesgue curve missing

Z-order leads to Z-curve, which is the Lebesgue space filling curve!

range searching

I'm having trouble understanding the "Use with one-dimensional data structures for range searching" section. It seems there should be a clear description of what the question is. It is clear that the author intends to be doing an axes-aligned rectangle search, but it's not clear what the search is supposed to report, nor what the data structure is (the first sentence assumes the existence of one, but doesn't define it). Finally, precisely what does locality preserving mean? Bhudson (talk) 06:12, 9 March 2009 (UTC)

• Locality preserving means that points that are near in the initial space are "near" to each other in the "in the z-curve" projection. I don't know much. — Preceding unsigned comment added by 2A01:E35:2EF3:D930:5CE4:7F:9DBF:8A90 (talk) 00:20, 22 September 2015 (UTC)

Compression

Does locality-preserving help with compression? I tried to gzip a z-order encoded 3d voxel image but it created a bigger file than a simple gzipped byte[,,]. Pathbuiltnow (talk) 07:51, 3 January 2011 (UTC)

I wouldn't expect locality-preserving to help compression, at least in the case of an image with many repeated identical patterns, since a translation by a few pixels of an image would significantly change the Z-order of the image data (same as a small translation of the Z-order data would mess up the image), but translation by a few pixels would completely preserve the "normal" order of the image data. Locality might be useful for compression, in the case that each "pixel" consisted of a lot of data, and nearby pixels consisted of similar data. Κσυπ Cyp   21:50, 12 March 2011 (UTC)

python code

Not sure how the python code in the article should work. What should be the input-format (bin or dec)?

So I write my own code to transfer a point to a position on z-curve:

def zorder(a, b):
  abin=str(bin(a)[2:].zfill(18))
  bbin=str(bin(b)[2:].zfill(18))
  print "abin: " + abin
  print "bbin: " + bbin
  y="0b"
  for k in range(18):
    y+=bbin[k] + abin[k]
  return int(y,2) 

zorder(2,3)

Result: 14

I hope this helps and perhaps somebode can include this to article. --Kolossos (talk) 22:10, 22 July 2011 (UTC)

Sorry, your code is even unclearer than that in the article. Where did you pull the 18 from, for example? Non-experts of Python won't know that the return format of bin(a) will have a 0b prefix. Note that Python is used here as pseudocode, so it's better to avoid assuming much knowledge of the Python standard library. Joachim Durchholz (talk) 07:16, 3 February 2012 (UTC)

---

The Python code in the article suffers from two problems:
1) It's unclear what kind of value each variable holds. The variables should either be renamed to something self-descriptive, or a comment should explain the role of each.
2) The code is slightly obscure because it tries to be smart about not recomputing an index expression. Now to explain the algorithm, we don't need optimized code (and an optimizing compiler, which we'd use if efficiency is of any concern, would spot this anyway, so there isn't any reason to even slightly complicate the code even in production).

The code from the ACM Sian article by Chan is much clearer; here's transcribed and commented pseudocode:

def z_order(p, q, d):
    "Returns true if p < q according to Z-order in d dimensions.
    p and q are supposed to be arrays of d coordinates."
    i = 0 # index of most significant dimension
    for j in range(1, d):
        # Use ^ (exclusive or) to eliminate equal bits.
        # msb_is_less will see ones where the coordinates differ.
        if msb_is_less (p[i]^q[i], p[j]^q[j]):
            i = j
    return p[i] < q[i]

def msb_is_less(l, r):
    "Returns true if the Most Significant Bit of l is less than that of r."
    return l <= r or l < l^r # Described as "neat trick" by Chan

Note that the algorithm in the article has "l < r" instead of "l <= r"; this changes the result of msb_is_less but I suspect it does not change the result of z_order.

Joachim Durchholz (talk) 07:16, 3 February 2012 (UTC)

this is NOT a space-filling curve!

The "Z-curve" is not a space-filling curve. It is not a curve (as opposed to just a function) in any mathematical sense, because it is not continuous: the points .011111111...1 (finite number of 1's) and .1 are aribtrarily close together but get mapped to the points (.0111...1,.111...1) and (.1,.0), respectively, which are separated by a distance >.1111...1 (in the y-coordinate alone). I aim to fix this in the article, but wanted to get any discussion out of the way here first. Wpegden (talk) 13:44, 4 April 2012 (UTC)

Yes, something is wrong with the article. It is talking about a map from the plane to the line (ignoring for the moment if that map is well defined). A curve would be a map from the line to the plane. — Carl (CBM · talk) 16:59, 4 April 2012 (UTC)

I don't think whether it's plane→line or line→plane matters so much because it's a bijection (ignoring the ambiguities in binary notation for numbers that end in repeating 1's vs repeating 0's). But as Wpegden says, a proper curve should be defined by a continuous function in the line→plane direction and this one is not continuous. —David Eppstein (talk) 21:08, 4 April 2012 (UTC)

Yep. — Carl (CBM · talk) 23:33, 4 April 2012 (UTC)

I've changed "space-filling curve" to function in the first sentence. That was actually the only place I saw that this was mentioned. Wpegden (talk) 15:36, 5 April 2012 (UTC)

Locality

I think that the claims of "locality" should be qualified, since the limit is not continuous. A comparison to a Peano curve, in both directions ($R\to R^{2}$ and $R^{2}\to R$) would clarify things. Bernardofpc (talk) 15:19, 11 February 2013 (UTC)

Lebesgue

What was the contribution of Lebesgue? Why is it also called the Lebesgue curve? Surely Lebesgue must have first introduced this curve if it is named after him. What did he say about the curve? — Preceding unsigned comment added by 145.94.130.134 (talk) 13:47, 19 July 2018 (UTC)

Please remove patent advertising

There is no "international patent" recognition, because it is a public domain algorithm. Morton used it in in the 1960's and 1970's for information-retrieval (today "database application").

About US-only "try to patent", Wikipedia is not a place to cite local-jurisdiction patent data. Even in US, there are no serious recognition, S2-geometry is free, is using Apache2 license since 2015. Krauss (talk) 22:51, 1 May 2021 (UTC)

Mirrored-Z is also Z

"Z" is like "2", when mirrored is like "5". This mirrored-Z is the most usual in maps, see Geohash.

Krauss (talk) 09:26, 6 September 2023 (UTC)