Create concrete classes for O-RAN Nodes
[oam.git] / 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()