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