code/network-generator/model/python/hexagon.py

   1 # Copyright 2023 highstreet technologies GmbH
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14 #
  15 # inspired by http://www.redblobgames.com/grids/hexagons/
  16
  17 #!/usr/bin/python
  18
  19 from __future__ import division
  20 from __future__ import print_function
  21 import collections
  22 import math
  23 from typing import NamedTuple
  24
  25
  26 class Point(NamedTuple):
  27     x: float
  28     y: float
  29
  30     def __str__(self):
  31         return f"{self.x},{self.y}"
  32
  33 class Hex:
  34     def __init__(self, q:int, r:int, s:int):
  35         if round(q + r + s) != 0:
  36             raise ValueError("The sum of q, r, and s must be 0.")
  37         self.q = q
  38         self.r = r
  39         self.s = s
  40
  41     def __str__(self):
  42         return f"q: {self.q}, r: {self.r}, s: {self.s}"
  43
  44
  45 def hex_add(a: Hex, b: Hex):
  46     return Hex(a.q + b.q, a.r + b.r, a.s + b.s)
  47
  48
  49 def hex_subtract(a: Hex, b: Hex):
  50     return Hex(a.q - b.q, a.r - b.r, a.s - b.s)
  51
  52
  53 def hex_scale(a: Hex, k: int):
  54     return Hex(a.q * k, a.r * k, a.s * k)
  55
  56
  57 def hex_rotate_left(a):
  58     return Hex(-a.s, -a.q, -a.r)
  59
  60
  61 def hex_rotate_right(a):
  62     return Hex(-a.r, -a.s, -a.q)
  63
  64
  65 hex_directions = [
  66     Hex(1, 0, -1),
  67     Hex(1, -1, 0),
  68     Hex(0, -1, 1),
  69     Hex(-1, 0, 1),
  70     Hex(-1, 1, 0),
  71     Hex(0, 1, -1),
  72 ]
  73
  74
  75 def hex_direction(direction):
  76     return hex_directions[direction]
  77
  78
  79 def hex_neighbor(hex: Hex, direction):
  80     return hex_add(hex, hex_direction(direction))
  81
  82
  83 hex_diagonals = [
  84     Hex(2, -1, -1),
  85     Hex(1, -2, 1),
  86     Hex(-1, -1, 2),
  87     Hex(-2, 1, 1),
  88     Hex(-1, 2, -1),
  89     Hex(1, 1, -2),
  90 ]
  91
  92
  93 def hex_diagonal_neighbor(hex: Hex, direction):
  94     return hex_add(hex, hex_diagonals[direction])
  95
  96
  97 def hex_length(hex: Hex):
  98     return (abs(hex.q) + abs(hex.r) + abs(hex.s)) // 2
  99
 100
 101 def hex_distance(a: Hex, b: Hex):
 102     return hex_length(hex_subtract(a, b))
 103
 104
 105 def hex_round(hex: Hex):
 106     qi = int(round(hex.q))
 107     ri = int(round(hex.r))
 108     si = int(round(hex.s))
 109     q_diff = abs(qi - hex.q)
 110     r_diff = abs(ri - hex.r)
 111     s_diff = abs(si - hex.s)
 112     if q_diff > r_diff and q_diff > s_diff:
 113         qi = -ri - si
 114     else:
 115         if r_diff > s_diff:
 116             ri = -qi - si
 117         else:
 118             si = -qi - ri
 119     return Hex(qi, ri, si)
 120
 121
 122 def hex_lerp(a: Hex, b: Hex, t: int):  # linearly interpolation
 123     return Hex(
 124         a.q * (1.0 - t) + b.q * t, a.r * (1.0 - t) + b.r * t, a.s * (1.0 - t) + b.s * t
 125     )
 126
 127
 128 def hex_linedraw(a: Hex, b: Hex):
 129     N = hex_distance(a, b)
 130     a_nudge = Hex(a.q + 1e-06, a.r + 1e-06, a.s - 2e-06)
 131     b_nudge = Hex(b.q + 1e-06, b.r + 1e-06, b.s - 2e-06)
 132     results = []
 133     step = 1.0 / max(N, 1)
 134     for i in range(0, N + 1):
 135         results.append(hex_round(hex_lerp(a_nudge, b_nudge, step * i)))
 136     return results
 137
 138
 139 OffsetCoord = collections.namedtuple("OffsetCoord", ["col", "row"])
 140
 141 EVEN = 1
 142 ODD = -1
 143
 144
 145 def qoffset_from_cube(offset: int, hex: Hex):
 146     col = hex.q
 147     row = hex.r + (hex.q + offset * (hex.q & 1)) // 2
 148     if offset != EVEN and offset != ODD:
 149         raise ValueError("offset must be EVEN (+1) or ODD (-1)")
 150     return OffsetCoord(col, row)
 151
 152
 153 def qoffset_to_cube(offset: int, hex: Hex):
 154     q = hex.col
 155     r = hex.row - (hex.col + offset * (hex.col & 1)) // 2
 156     s = -q - r
 157     if offset != EVEN and offset != ODD:
 158         raise ValueError("offset must be EVEN (+1) or ODD (-1)")
 159     return Hex(q, r, s)
 160
 161
 162 def roffset_from_cube(offset: int, hex: Hex):
 163     col = hex.q + (hex.r + offset * (hex.r & 1)) // 2
 164     row = hex.r
 165     if offset != EVEN and offset != ODD:
 166         raise ValueError("offset must be EVEN (+1) or ODD (-1)")
 167     return OffsetCoord(col, row)
 168
 169
 170 def roffset_to_cube(offset: int, hex: Hex):
 171     q = hex.col - (hex.row + offset * (hex.row & 1)) // 2
 172     r = hex.row
 173     s = -q - r
 174     if offset != EVEN and offset != ODD:
 175         raise ValueError("offset must be EVEN (+1) or ODD (-1)")
 176     return Hex(q, r, s)
 177
 178
 179 DoubledCoord = collections.namedtuple("DoubledCoord", ["col", "row"])
 180
 181
 182 def qdoubled_from_cube(hex: Hex):
 183     col = hex.q
 184     row = 2 * hex.r + hex.q
 185     return DoubledCoord(col, row)
 186
 187
 188 def qdoubled_to_cube(hex: Hex):
 189     q = hex.col
 190     r = (hex.row - hex.col) // 2
 191     s = -q - r
 192     return Hex(q, r, s)
 193
 194
 195 def rdoubled_from_cube(hex: Hex):
 196     col = 2 * hex.q + hex.r
 197     row = hex.r
 198     return DoubledCoord(col, row)
 199
 200
 201 def rdoubled_to_cube(hex: Hex):
 202     q = (hex.col - hex.row) // 2
 203     r = hex.row
 204     s = -q - r
 205     return Hex(q, r, s)
 206
 207
 208 Orientation = collections.namedtuple(
 209     "Orientation", ["f0", "f1", "f2", "f3", "b0", "b1", "b2", "b3", "start_angle"]
 210 )
 211
 212
 213 # Layout = collections.namedtuple("Layout", ["orientation", "size", "origin"])
 214 class Layout(NamedTuple):
 215     orientation: Orientation
 216     size: Point
 217     origin: Point
 218
 219
 220 layout_pointy = Orientation(
 221     math.sqrt(3.0),
 222     math.sqrt(3.0) / 2.0,
 223     0.0,
 224     3.0 / 2.0,
 225     math.sqrt(3.0) / 3.0,
 226     -1.0 / 3.0,
 227     0.0,
 228     2.0 / 3.0,
 229     0.5,
 230 )
 231 layout_flat = Orientation(
 232     3.0 / 2.0,
 233     0.0,
 234     math.sqrt(3.0) / 2.0,
 235     math.sqrt(3.0),
 236     2.0 / 3.0,
 237     0.0,
 238     -1.0 / 3.0,
 239     math.sqrt(3.0) / 3.0,
 240     0.0,
 241 )
 242
 243
 244 def hex_to_pixel(layout: Layout, hex: Hex):
 245     M = layout.orientation
 246     size = layout.size
 247     origin = layout.origin
 248     x = (M.f0 * hex.q + M.f1 * hex.r) * size.x
 249     y = (M.f2 * hex.q + M.f3 * hex.r) * size.y
 250     return Point(x + origin.x, y + origin.y)
 251
 252
 253 def pixel_to_hex(layout: Layout, p: Point):
 254     M = layout.orientation
 255     size = layout.size
 256     origin = layout.origin
 257     pt = Point((p.x - origin.x) / size.x, (p.y - origin.y) / size.y)
 258     q = M.b0 * pt.x + M.b1 * pt.y
 259     r = M.b2 * pt.x + M.b3 * pt.y
 260     return Hex(q, r, -q - r)
 261
 262
 263 def hex_corner_offset(layout: Layout, corner: int):
 264     M = layout.orientation
 265     size = layout.size
 266     angle = 2.0 * math.pi * (M.start_angle - corner) / 6.0
 267     return Point(size.x * math.cos(angle), size.y * math.sin(angle))
 268
 269
 270 def polygon_corners(layout: Layout, hex: Hex):
 271     corners: list[Point] = []
 272     center = hex_to_pixel(layout, hex)
 273     for i in range(0, 6):
 274         offset = hex_corner_offset(layout, i)
 275         corners.append(Point(center.x + offset.x, center.y + offset.y))
 276     return corners
 277
 278
 279 # Tests
 280
 281
 282 def complain(name):
 283     print("FAIL {0}".format(name))
 284
 285
 286 def equal_hex(name, a, b):
 287     if not (a.q == b.q and a.s == b.s and a.r == b.r):
 288         complain(name)
 289
 290
 291 def equal_offsetcoord(name, a, b):
 292     if not (a.col == b.col and a.row == b.row):
 293         complain(name)
 294
 295
 296 def equal_doubledcoord(name, a, b):
 297     if not (a.col == b.col and a.row == b.row):
 298         complain(name)
 299
 300
 301 def equal_int(name, a, b):
 302     if not (a == b):
 303         complain(name)
 304
 305
 306 def equal_hex_array(name, a, b):
 307     equal_int(name, len(a), len(b))
 308     for i in range(0, len(a)):
 309         equal_hex(name, a[i], b[i])
 310
 311
 312 def test_hex_arithmetic():
 313     equal_hex("hex_add", Hex(4, -10, 6), hex_add(Hex(1, -3, 2), Hex(3, -7, 4)))
 314     equal_hex(
 315         "hex_subtract", Hex(-2, 4, -2), hex_subtract(Hex(1, -3, 2), Hex(3, -7, 4))
 316     )
 317
 318
 319 def test_hex_direction():
 320     equal_hex("hex_direction", Hex(0, -1, 1), hex_direction(2))
 321
 322
 323 def test_hex_neighbor():
 324     equal_hex("hex_neighbor", Hex(1, -3, 2), hex_neighbor(Hex(1, -2, 1), 2))
 325
 326
 327 def test_hex_diagonal():
 328     equal_hex("hex_diagonal", Hex(-1, -1, 2), hex_diagonal_neighbor(Hex(1, -2, 1), 3))
 329
 330
 331 def test_hex_distance():
 332     equal_int("hex_distance", 7, hex_distance(Hex(3, -7, 4), Hex(0, 0, 0)))
 333
 334
 335 def test_hex_rotate_right():
 336     equal_hex("hex_rotate_right", hex_rotate_right(Hex(1, -3, 2)), Hex(3, -2, -1))
 337
 338
 339 def test_hex_rotate_left():
 340     equal_hex("hex_rotate_left", hex_rotate_left(Hex(1, -3, 2)), Hex(-2, -1, 3))
 341
 342
 343 def test_hex_round():
 344     a = Hex(0.0, 0.0, 0.0)
 345     b = Hex(1.0, -1.0, 0.0)
 346     c = Hex(0.0, -1.0, 1.0)
 347     equal_hex(
 348         "hex_round 1",
 349         Hex(5, -10, 5),
 350         hex_round(hex_lerp(Hex(0.0, 0.0, 0.0), Hex(10.0, -20.0, 10.0), 0.5)),
 351     )
 352     equal_hex("hex_round 2", hex_round(a), hex_round(hex_lerp(a, b, 0.499)))
 353     equal_hex("hex_round 3", hex_round(b), hex_round(hex_lerp(a, b, 0.501)))
 354     equal_hex(
 355         "hex_round 4",
 356         hex_round(a),
 357         hex_round(
 358             Hex(
 359                 a.q * 0.4 + b.q * 0.3 + c.q * 0.3,
 360                 a.r * 0.4 + b.r * 0.3 + c.r * 0.3,
 361                 a.s * 0.4 + b.s * 0.3 + c.s * 0.3,
 362             )
 363         ),
 364     )
 365     equal_hex(
 366         "hex_round 5",
 367         hex_round(c),
 368         hex_round(
 369             Hex(
 370                 a.q * 0.3 + b.q * 0.3 + c.q * 0.4,
 371                 a.r * 0.3 + b.r * 0.3 + c.r * 0.4,
 372                 a.s * 0.3 + b.s * 0.3 + c.s * 0.4,
 373             )
 374         ),
 375     )
 376
 377
 378 def test_hex_linedraw():
 379     equal_hex_array(
 380         "hex_linedraw",
 381         [
 382             Hex(0, 0, 0),
 383             Hex(0, -1, 1),
 384             Hex(0, -2, 2),
 385             Hex(1, -3, 2),
 386             Hex(1, -4, 3),
 387             Hex(1, -5, 4),
 388         ],
 389         hex_linedraw(Hex(0, 0, 0), Hex(1, -5, 4)),
 390     )
 391
 392
 393 def test_layout():
 394     h = Hex(3, 4, -7)
 395     flat = Layout(layout_flat, Point(10.0, 15.0), Point(35.0, 71.0))
 396     equal_hex("layout", h, hex_round(pixel_to_hex(flat, hex_to_pixel(flat, h))))
 397     pointy = Layout(layout_pointy, Point(10.0, 15.0), Point(35.0, 71.0))
 398     equal_hex("layout", h, hex_round(pixel_to_hex(pointy, hex_to_pixel(pointy, h))))
 399
 400
 401 def test_offset_roundtrip():
 402     a = Hex(3, 4, -7)
 403     b = OffsetCoord(1, -3)
 404     equal_hex(
 405         "conversion_roundtrip even-q",
 406         a,
 407         qoffset_to_cube(EVEN, qoffset_from_cube(EVEN, a)),
 408     )
 409     equal_offsetcoord(
 410         "conversion_roundtrip even-q",
 411         b,
 412         qoffset_from_cube(EVEN, qoffset_to_cube(EVEN, b)),
 413     )
 414     equal_hex(
 415         "conversion_roundtrip odd-q", a, qoffset_to_cube(ODD, qoffset_from_cube(ODD, a))
 416     )
 417     equal_offsetcoord(
 418         "conversion_roundtrip odd-q", b, qoffset_from_cube(ODD, qoffset_to_cube(ODD, b))
 419     )
 420     equal_hex(
 421         "conversion_roundtrip even-r",
 422         a,
 423         roffset_to_cube(EVEN, roffset_from_cube(EVEN, a)),
 424     )
 425     equal_offsetcoord(
 426         "conversion_roundtrip even-r",
 427         b,
 428         roffset_from_cube(EVEN, roffset_to_cube(EVEN, b)),
 429     )
 430     equal_hex(
 431         "conversion_roundtrip odd-r", a, roffset_to_cube(ODD, roffset_from_cube(ODD, a))
 432     )
 433     equal_offsetcoord(
 434         "conversion_roundtrip odd-r", b, roffset_from_cube(ODD, roffset_to_cube(ODD, b))
 435     )
 436
 437
 438 def test_offset_from_cube():
 439     equal_offsetcoord(
 440         "offset_from_cube even-q",
 441         OffsetCoord(1, 3),
 442         qoffset_from_cube(EVEN, Hex(1, 2, -3)),
 443     )
 444     equal_offsetcoord(
 445         "offset_from_cube odd-q",
 446         OffsetCoord(1, 2),
 447         qoffset_from_cube(ODD, Hex(1, 2, -3)),
 448     )
 449
 450
 451 def test_offset_to_cube():
 452     equal_hex(
 453         "offset_to_cube even-", Hex(1, 2, -3), qoffset_to_cube(EVEN, OffsetCoord(1, 3))
 454     )
 455     equal_hex(
 456         "offset_to_cube odd-q", Hex(1, 2, -3), qoffset_to_cube(ODD, OffsetCoord(1, 2))
 457     )
 458
 459
 460 def test_doubled_roundtrip():
 461     a = Hex(3, 4, -7)
 462     b = DoubledCoord(1, -3)
 463     equal_hex(
 464         "conversion_roundtrip doubled-q", a, qdoubled_to_cube(qdoubled_from_cube(a))
 465     )
 466     equal_doubledcoord(
 467         "conversion_roundtrip doubled-q", b, qdoubled_from_cube(qdoubled_to_cube(b))
 468     )
 469     equal_hex(
 470         "conversion_roundtrip doubled-r", a, rdoubled_to_cube(rdoubled_from_cube(a))
 471     )
 472     equal_doubledcoord(
 473         "conversion_roundtrip doubled-r", b, rdoubled_from_cube(rdoubled_to_cube(b))
 474     )
 475
 476
 477 def test_doubled_from_cube():
 478     equal_doubledcoord(
 479         "doubled_from_cube doubled-q",
 480         DoubledCoord(1, 5),
 481         qdoubled_from_cube(Hex(1, 2, -3)),
 482     )
 483     equal_doubledcoord(
 484         "doubled_from_cube doubled-r",
 485         DoubledCoord(4, 2),
 486         rdoubled_from_cube(Hex(1, 2, -3)),
 487     )
 488
 489
 490 def test_doubled_to_cube():
 491     equal_hex(
 492         "doubled_to_cube doubled-q", Hex(1, 2, -3), qdoubled_to_cube(DoubledCoord(1, 5))
 493     )
 494     equal_hex(
 495         "doubled_to_cube doubled-r", Hex(1, 2, -3), rdoubled_to_cube(DoubledCoord(4, 2))
 496     )
 497
 498
 499 def test_all():
 500     test_hex_arithmetic()
 501     test_hex_direction()
 502     test_hex_neighbor()
 503     test_hex_diagonal()
 504     test_hex_distance()
 505     test_hex_rotate_right()
 506     test_hex_rotate_left()
 507     test_hex_round()
 508     test_hex_linedraw()
 509     test_layout()
 510     test_offset_roundtrip()
 511     test_offset_from_cube()
 512     test_offset_to_cube()
 513     test_doubled_roundtrip()
 514     test_doubled_from_cube()
 515     test_doubled_to_cube()
 516     print("test finished")
 517
 518
 519 if __name__ == "__main__":
 520     test_all()