Skip to content

Instantly share code, notes, and snippets.

@object
Created October 28, 2026 07:45
Show Gist options
  • Select an option

  • Save object/bfafc2e9681a32b0387aa82173f8036d to your computer and use it in GitHub Desktop.

Select an option

Save object/bfafc2e9681a32b0387aa82173f8036d to your computer and use it in GitHub Desktop.
Claude port of Gilbert alrorithm
/// Generalized Hilbert ("gilbert") space-filling curve, which unlike a plain
/// Hilbert curve also covers rectangles whose sides are not powers of two.
/// Ported from the JavaScript reference implementation at
/// https://github.com/jakubcerveny/gilbert (BSD-2-Clause, Copyright (c) 2024 abetusk).
module Gilbert
type Point = { X: int; Y: int }
/// JavaScript divides by two with Math.floor, which rounds towards negative
/// infinity, while F# integer division truncates towards zero.
let private half value = int (floor (float value / 2.0))
let private inBounds (q: Point) (p: Point) (a: Point) (b: Point) =
let d = { X = a.X + b.X; Y = a.Y + b.Y }
let insideX =
if d.X < 0 then
q.X <= p.X && q.X > p.X + d.X
else
q.X >= p.X && q.X < p.X + d.X
let insideY =
if d.Y < 0 then
q.Y <= p.Y && q.Y > p.Y + d.Y
else
q.Y >= p.Y && q.Y < p.Y + d.Y
insideX && insideY
let rec private d2xyRec dstIdx curIdx (p: Point) (a: Point) (b: Point) =
let w = abs (a.X + a.Y)
let h = abs (b.X + b.Y)
let da = { X = sign a.X; Y = sign a.Y }
let db = { X = sign b.X; Y = sign b.Y }
let steps = dstIdx - curIdx
if h = 1 then
{
X = p.X + da.X * steps
Y = p.Y + da.Y * steps
}
elif w = 1 then
{
X = p.X + db.X * steps
Y = p.Y + db.Y * steps
}
else
let a2 = { X = half a.X; Y = half a.Y }
let b2 = { X = half b.X; Y = half b.Y }
let w2 = abs (a2.X + a2.Y)
let h2 = abs (b2.X + b2.Y)
if 2 * w > 3 * h then
// Wide rectangle: split along the long side only, preferring even steps.
let a2 =
if w2 % 2 <> 0 && w > 2 then
{ X = a2.X + da.X; Y = a2.Y + da.Y }
else
a2
let nextIdx = curIdx + abs ((a2.X + a2.Y) * (b.X + b.Y))
if dstIdx < nextIdx then
d2xyRec dstIdx curIdx p a2 b
else
d2xyRec dstIdx nextIdx { X = p.X + a2.X; Y = p.Y + a2.Y } { X = a.X - a2.X; Y = a.Y - a2.Y } b
else
// Standard case: one step up, along the long horizontal, one step down.
let b2 =
if h2 % 2 <> 0 && h > 2 then
{ X = b2.X + db.X; Y = b2.Y + db.Y }
else
b2
let afterFirst = curIdx + abs ((b2.X + b2.Y) * (a2.X + a2.Y))
if dstIdx < afterFirst then
d2xyRec dstIdx curIdx p b2 a2
else
let afterSecond = afterFirst + abs ((a.X + a.Y) * ((b.X - b2.X) + (b.Y - b2.Y)))
if dstIdx < afterSecond then
d2xyRec dstIdx afterFirst { X = p.X + b2.X; Y = p.Y + b2.Y } a { X = b.X - b2.X; Y = b.Y - b2.Y }
else
let origin =
{
X = p.X + (a.X - da.X) + (b2.X - db.X)
Y = p.Y + (a.Y - da.Y) + (b2.Y - db.Y)
}
d2xyRec dstIdx afterSecond origin { X = -b2.X; Y = -b2.Y } { X = -(a.X - a2.X); Y = -(a.Y - a2.Y) }
let rec private xy2dRec idx (q: Point) (p: Point) (a: Point) (b: Point) =
let w = abs (a.X + a.Y)
let h = abs (b.X + b.Y)
let da = { X = sign a.X; Y = sign a.Y }
let db = { X = sign b.X; Y = sign b.Y }
if h = 1 then
idx + da.X * (q.X - p.X) + da.Y * (q.Y - p.Y)
elif w = 1 then
idx + db.X * (q.X - p.X) + db.Y * (q.Y - p.Y)
else
let a2 = { X = half a.X; Y = half a.Y }
let b2 = { X = half b.X; Y = half b.Y }
let w2 = abs (a2.X + a2.Y)
let h2 = abs (b2.X + b2.Y)
if 2 * w > 3 * h then
let a2 =
if w2 % 2 <> 0 && w > 2 then
{ X = a2.X + da.X; Y = a2.Y + da.Y }
else
a2
if inBounds q p a2 b then
xy2dRec idx q p a2 b
else
let idx = idx + abs ((a2.X + a2.Y) * (b.X + b.Y))
xy2dRec idx q { X = p.X + a2.X; Y = p.Y + a2.Y } { X = a.X - a2.X; Y = a.Y - a2.Y } b
else
let b2 =
if h2 % 2 <> 0 && h > 2 then
{ X = b2.X + db.X; Y = b2.Y + db.Y }
else
b2
if inBounds q p b2 a2 then
xy2dRec idx q p b2 a2
else
let idx = idx + abs ((b2.X + b2.Y) * (a2.X + a2.Y))
let corner = { X = p.X + b2.X; Y = p.Y + b2.Y }
let rest = { X = b.X - b2.X; Y = b.Y - b2.Y }
if inBounds q corner a rest then
xy2dRec idx q corner a rest
else
let idx = idx + abs ((a.X + a.Y) * ((b.X - b2.X) + (b.Y - b2.Y)))
let origin =
{
X = p.X + (a.X - da.X) + (b2.X - db.X)
Y = p.Y + (a.Y - da.Y) + (b2.Y - db.Y)
}
xy2dRec idx q origin { X = -b2.X; Y = -b2.Y } { X = -(a.X - a2.X); Y = -(a.Y - a2.Y) }
let private axes width height =
if width >= height then
{ X = width; Y = 0 }, { X = 0; Y = height }
else
{ X = 0; Y = height }, { X = width; Y = 0 }
/// The point the curve visits at the given index.
let d2xy index width height =
let a, b = axes width height
d2xyRec index 0 { X = 0; Y = 0 } a b
/// The index at which the curve visits the given point.
let xy2d x y width height =
let a, b = axes width height
xy2dRec 0 { X = x; Y = y } { X = 0; Y = 0 } a b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment