Created
October 28, 2026 07:45
-
-
Save object/bfafc2e9681a32b0387aa82173f8036d to your computer and use it in GitHub Desktop.
Claude port of Gilbert alrorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// 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