5a81c23d42a5cb9272d98bf6bdce89d4a0410b8a
[oam.git] / 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()