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