jakubcerveny / gilbert Goto Github PK

Hi! This is a great little algorithm. I made my version a little friendlier by turning it into a generator, so that I could use it in other functions. Not sure if you'd be interested in doing that. The diff looks like this for the 2d script; same basic idea for the 3d script. I could put in a formal pull request if you're interested in the idea and prefer that way of working.

diff --git a/gilbert2d.py b/gilbert2d.py
index 15035b2..c402d3a 100755
--- a/gilbert2d.py
+++ b/gilbert2d.py
@@ -21,14 +21,14 @@ def gilbert2d(x, y, ax, ay, bx, by):
     if h == 1:
         # trivial row fill
         for i in range(0, w):
-            print(x, y)
+            yield(x, y)
             (x, y) = (x + dax, y + day)
         return

     if w == 1:
         # trivial column fill
         for i in range(0, h):
-            print(x, y)
+            yield(x, y)
             (x, y) = (x + dbx, y + dby)
         return

@@ -44,8 +44,8 @@ def gilbert2d(x, y, ax, ay, bx, by):
             (ax2, ay2) = (ax2 + dax, ay2 + day)

         # long case: split in two parts only
-        gilbert2d(x, y, ax2, ay2, bx, by)
-        gilbert2d(x+ax2, y+ay2, ax-ax2, ay-ay2, bx, by)
+        yield from gilbert2d(x, y, ax2, ay2, bx, by)
+        yield from gilbert2d(x+ax2, y+ay2, ax-ax2, ay-ay2, bx, by)

     else:
         if (h2 % 2) and (h > 2):
@@ -53,9 +53,9 @@ def gilbert2d(x, y, ax, ay, bx, by):
             (bx2, by2) = (bx2 + dbx, by2 + dby)

         # standard case: one step up, one long horizontal, one step down
-        gilbert2d(x, y, bx2, by2, ax2, ay2)
-        gilbert2d(x+bx2, y+by2, ax, ay, bx-bx2, by-by2)
-        gilbert2d(x+(ax-dax)+(bx2-dbx), y+(ay-day)+(by2-dby),
+        yield from gilbert2d(x, y, bx2, by2, ax2, ay2)
+        yield from gilbert2d(x+bx2, y+by2, ax, ay, bx-bx2, by-by2)
+        yield from gilbert2d(x+(ax-dax)+(bx2-dbx), y+(ay-day)+(by2-dby),
                  -bx2, -by2, -(ax-ax2), -(ay-ay2))


@@ -64,9 +64,11 @@ def main():
     height = int(sys.argv[2])

     if width >= height:
-        gilbert2d(0, 0, width, 0, 0, height)
+        for x, y in gilbert2d(0, 0, width, 0, 0, height):
+            print(x, y)
     else:
-        gilbert2d(0, 0, 0, height, width, 0)
+        for x, y in gilbert2d(0, 0, 0, height, width, 0):
+            print(x, y)

Would you be interested in this becoming an installable library on pypi.org so that others could easily use it? I am happy to do the work but thought I'd see whether it would be welcome before just raising a massive PR. Alternatively if it would distract too much from the core algorithm I'm happy to make a separate package which just refers back to this.

I think it is because of this line.
line 187 in gilbert.c

if (max_iter > 100000) { return -1; }

When this line is removed, the gilbert_d2xy appears to wrok fine with larger width and height. Otherwise it returns 0. As an example
gilbert_d2xy(&x, &y, 7861, 490, 490) sets x and y incorrectly to zero and returns -1.
Can you explain why you set a maxiter value in the c implementation, when it works fine beyond that?
(I know it is correct to guard against things like overflow, but dimensions like 490x490 are not that large and uncommon and overflow still does not seem to happen at these still relatively small width and height values)

It would be nice to have stand alone conversion functions that convert from spatial dimensions to position along the curve (xy2d, xyz2d) and vice versa (d2xy, d2xyz).

As mentioned in #6, this should be possible in $O( \ln N )$ time (and $O(1)$ ish space).

I'm working on this now (here) and hope to issue a PR in the near future when I'm confident enough about the results.

This is less of an issue and more of a question: What's your preferred citation if I use this in a project?

Thanks.

This is not an issue report, just letting you know that all the questions I asked you months ago have finally turned into something. I used a gilbert curve as a chromosome map in this very long (5 part, 42 hour) video series:

https://www.youtube.com/watch?v=6Ev2WgLk9Oc&list=PL0elTBjXjW_52wz-JBuRfFQIgrRUfONWR

It might not be your kind of thing, but I just wanted to say thanks for the code!

Even though there's prior work in this area, I suspect this algorithm is novel, so its worth writing a paper for it. Even if this is not new work, a paper would still be warranted as it could be a description of whats going on with this algorithm, could give a review of what's previously known and give the proper tools and context to understand this subject.

Though there is a README for this project, the description is light on the inner workings or other subtleties of the algorithm, especially for 3D.

If you don't mind sharing the glory, I would be happy to help.

Hey i just wanted to know if there was any research been done in achieving a closed form for this curve.
Is there a way to calculate the discrete value f(x) for a cell x in O(1)?