hexUtil.py (10557B)
1 #Embedded file name: C:\BuildAgent\work\20d73f1b24eed06e\eve\release\V24.01\eve\client\script\ui\shared\mapView\hexagonal\hexUtil.py 2 from __future__ import print_function 3 __author__ = 'fridrik' 4 import geo2 5 import math 6 HEX_NEIGHBORS_AXIAL = [[1, 0], 7 [1, -1], 8 [0, -1], 9 [-1, 0], 10 [0, 1], 11 [1, 1]] 12 HEX_NEIGHBORS_AXIAL_FLATTOP = [[1, -1], 13 [0, -1], 14 [-1, -1], 15 [-1, 0], 16 [0, 1], 17 [1, 0]] 18 neighbors = [[[+1, 0], 19 [0, -1], 20 [-1, -1], 21 [-1, 0], 22 [-1, +1], 23 [0, +1]], [[+1, 0], 24 [+1, -1], 25 [0, -1], 26 [-1, 0], 27 [0, +1], 28 [+1, +1]]] 29 HEX_NEIGHBORS_CUBE = [[+1, -1, 0], 30 [+1, 0, -1], 31 [0, +1, -1], 32 [-1, +1, 0], 33 [-1, 0, +1], 34 [0, -1, +1]] 35 36 def neighbour_cube(xyz, i): 37 x, y, z = xyz 38 nx, ny, nz = HEX_NEIGHBORS_CUBE[i] 39 return (x + nx, y + ny, z + nz) 40 41 42 def neighbours_from_pos(column_row, startRange, endRange, isFlatTop): 43 startpos = column_row 44 for i in xrange(startRange): 45 startpos = neighbour_axial(startpos, 4, isFlatTop) 46 47 ret = [] 48 for i in xrange(startRange, endRange): 49 startpos = neighbour_axial(startpos, 4, isFlatTop) 50 cr = startpos 51 for direction in xrange(6): 52 for length in xrange(i + 1): 53 cr = neighbour_axial(cr, direction, isFlatTop) 54 ret.append(cr) 55 56 return ret 57 58 59 def neighbour_axial(cr, direction, isFlatTop): 60 c, r = cr 61 if isFlatTop: 62 parity = c & 1 63 neighbors = [[[1, -1], 64 [0, -1], 65 [-1, -1], 66 [-1, 0], 67 [0, 1], 68 [1, 0]], [[1, 0], 69 [0, -1], 70 [-1, 0], 71 [-1, 1], 72 [0, 1], 73 [1, 1]]] 74 c1, r1 = neighbors[parity][direction] 75 else: 76 parity = r & 1 77 neighbors = [[[1, 0], 78 [0, -1], 79 [-1, -1], 80 [-1, 0], 81 [-1, 1], 82 [0, 1]], [[1, 0], 83 [1, -1], 84 [0, -1], 85 [-1, 0], 86 [0, 1], 87 [1, 1]]] 88 c1, r1 = neighbors[parity][direction] 89 return (c + c1, r + r1) 90 91 92 def line_intersection(line1, line2): 93 xdiff = (line1[0][0] - line1[1][0], line2[0][0] - line2[1][0]) 94 ydiff = (line1[0][1] - line1[1][1], line2[0][1] - line2[1][1]) 95 96 def det(a, b): 97 return a[0] * b[1] - a[1] * b[0] 98 99 div = det(xdiff, ydiff) 100 if div == 0: 101 return None 102 d = (det(*line1), det(*line2)) 103 x = det(d, xdiff) / div 104 y = det(d, ydiff) / div 105 return (x, y) 106 107 108 def line(p1, p2): 109 A = p1[1] - p2[1] 110 B = p2[0] - p1[0] 111 C = p1[0] * p2[1] - p2[0] * p1[1] 112 return (A, B, -C) 113 114 115 def perp(a): 116 b = empty_like(a) 117 b[0] = -a[1] 118 b[1] = a[0] 119 return b 120 121 122 def seg_intersect(line1, line2): 123 a1, a2 = line1 124 b1, b2 = line2 125 da = geo2.Vec2Subtract(a2, a1) 126 db = geo2.Vec2Subtract(b2, b1) 127 dp = geo2.Vec2Subtract(a1, b1) 128 dap = (-da[1], da[0]) 129 denom = geo2.Vec2Dot(dap, db) 130 if not denom: 131 return False 132 num = geo2.Vec2Dot(dap, dp) 133 return geo2.Vec2Scale(geo2.Vec2Add(db, b1), num / denom) 134 135 136 def intersection(L1, L2): 137 L1 = line(*L1) 138 L2 = line(*L2) 139 D = L1[0] * L2[1] - L1[1] * L2[0] 140 Dx = L1[2] * L2[1] - L1[1] * L2[2] 141 Dy = L1[0] * L2[2] - L1[2] * L2[0] 142 if D != 0: 143 x = Dx / D 144 y = Dy / D 145 return (x, y) 146 else: 147 return False 148 149 150 def intersect_line_segments(seg1, seg2): 151 A, B = seg1 152 C, D = seg2 153 if seg1 == seg2: 154 return geo2.Vec2Lerp(A, B, 0.5) 155 cV = segment_circle(A, B, C) 156 cL = geo2.Vec2Length(cV) 157 dV = segment_circle(A, B, D) 158 dL = geo2.Vec2Length(dV) 159 aV = segment_circle(C, D, A) 160 aL = geo2.Vec2Length(aV) 161 bV = segment_circle(C, D, B) 162 bL = geo2.Vec2Length(bV) 163 Ax, Ay = A 164 Bx, By = B 165 Cx, Cy = C 166 Dx, Dy = D 167 X = Y = 0.0 168 if Ax == Bx and Ay == By or Cx == Dx and Cy == Dy: 169 print('False1') 170 return False 171 if Ax == Cx and Ay == Cy or Bx == Cx and By == Cy or Ax == Dx and Ay == Dy or Bx == Dx and By == Dy: 172 return False 173 Bx -= Ax 174 By -= Ay 175 Cx -= Ax 176 Cy -= Ay 177 Dx -= Ax 178 Dy -= Ay 179 distAB = math.sqrt(Bx * Bx + By * By) 180 theCos = Bx / distAB 181 theSin = By / distAB 182 newX = Cx * theCos + Cy * theSin 183 Cy = Cy * theCos - Cx * theSin 184 Cx = newX 185 newX = Dx * theCos + Dy * theSin 186 Dy = Dy * theCos - Dx * theSin 187 Dx = newX 188 if Cy < 0 and Dy < 0 or Cy >= 0 and Dy >= 0: 189 return False 190 ABpos = Dx + (Cx - Dx) * Dy / (Dy - Cy) 191 if ABpos < 0 or ABpos > distAB: 192 return False 193 X = Ax + ABpos * theCos 194 Y = Ay + ABpos * theSin 195 return (X, Y) 196 197 198 def closest_point_on_seg(seg_a, seg_b, circ_pos): 199 seg_v = geo2.Vec2Subtract(seg_b, seg_a) 200 pt_v = geo2.Vec2Subtract(circ_pos, seg_a) 201 if geo2.Vec2Length(seg_v) <= 0: 202 raise ValueError('Invalid segment length') 203 seg_v_unit = geo2.Vec2Normalize(seg_v) 204 proj = geo2.Vec2Dot(seg_v_unit, pt_v) 205 if proj <= 0: 206 return seg_a 207 if proj >= geo2.Vec2Length(seg_v): 208 return seg_b 209 proj_v = geo2.Vec2Scale(seg_v_unit, proj) 210 closest = geo2.Vec2Add(proj_v, seg_a) 211 return closest 212 213 214 def segment_circle(seg_a, seg_b, circ_pos, circ_rad = 1): 215 closest = closest_point_on_seg(seg_a, seg_b, circ_pos) 216 dist_v = geo2.Vec2Subtract(circ_pos, closest) 217 return dist_v 218 219 220 def hex_distance(cr1, cr2): 221 r1, c1 = cr1 222 r2, c2 = cr2 223 return (abs(c1 - c2) + abs(r1 - r2) + abs(c1 + r1 - c2 - r2)) / 2 224 225 226 def hex_path_between(cr1, cr2): 227 dist = hex_distance(cr1, cr2) 228 c1, r1 = cr1 229 c2, r2 = cr2 230 ret = [] 231 for i in xrange(dist): 232 ret.append((c1 * (1 - float(i) / dist) + c2 * float(i) / dist, r1 * (1 - float(i) / dist) + r2 * float(i) / dist)) 233 234 return ret 235 236 237 def hex_slot_size(isFlatTop, hexSize): 238 if isFlatTop: 239 width = hexSize * 2 240 height = math.sqrt(3.0) / 2.0 * width 241 else: 242 height = hexSize * 2 243 width = math.sqrt(3.0) / 2.0 * height 244 return (width, height) 245 246 247 def ccw(A, B, C): 248 return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0]) 249 250 251 def intersect(A, B, C, D): 252 return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D) 253 254 255 def hex_slot_center_position(column, row, isFlatTop, hexSize): 256 width, height = hex_slot_size(isFlatTop, hexSize) 257 x, y = column, row 258 if isFlatTop: 259 cX = 0.75 * width * x 260 cY = height * y + x % 2 * height * 0.5 261 else: 262 cX = width * x + y % 2 * width * 0.5 263 cY = 0.75 * height * y 264 return (cX, cY) 265 266 267 def hex_slot_position(column, row, isFlatTop, hexSize): 268 width, height = hex_slot_size(isFlatTop, hexSize) 269 x, y = column, row 270 if isFlatTop: 271 cX = 0.75 * width * x 272 cY = height * y + x % 2 * height * 0.5 273 else: 274 cX = width * x + y % 2 * width * 0.5 275 cY = 0.75 * height * y 276 return (cX, cY) 277 278 279 def hex_round(x, y, z): 280 rx = round(x) 281 ry = round(y) 282 rz = round(z) 283 x_diff = abs(rx - x) 284 y_diff = abs(ry - y) 285 z_diff = abs(rz - z) 286 if x_diff > y_diff and x_diff > z_diff: 287 rx = -ry - rz 288 elif y_diff > z_diff: 289 ry = -rx - rz 290 else: 291 rz = -rx - ry 292 return (int(rx), int(ry), int(rz)) 293 294 295 def axial_neighbours(column_row, isFlatTop): 296 ret = [] 297 for direction in xrange(6): 298 cr = neighbour_axial(column_row, direction, isFlatTop) 299 ret.append(cr) 300 301 return ret 302 303 304 def neighbours_amount_step(column_row, amount, step, isFlatTop, exact = False): 305 startpos = column_row 306 ret = [] 307 i = 0 308 while len(ret) < amount: 309 for s in xrange(step): 310 startpos = neighbour_axial(startpos, 4, isFlatTop) 311 312 cr = startpos 313 for direction in xrange(6): 314 for length in xrange(i + 1): 315 for s in xrange(step): 316 cr = neighbour_axial(cr, direction, isFlatTop) 317 318 ret.append(cr) 319 if exact and len(ret) == amount: 320 return ret 321 322 if len(ret) >= amount: 323 return ret 324 i += 1 325 326 return ret 327 328 329 def hex_round_float(x, y, z): 330 rx = round(x) 331 ry = round(y) 332 rz = round(z) 333 x_diff = abs(rx - x) 334 y_diff = abs(ry - y) 335 z_diff = abs(rz - z) 336 if x_diff > y_diff and x_diff > z_diff: 337 rx = -ry - rz 338 elif y_diff > z_diff: 339 ry = -rx - rz 340 else: 341 rz = -rx - ry 342 return (rx, ry, rz) 343 344 345 def pixel_to_hex(x, y, hexSize, isFlatTop): 346 if isFlatTop: 347 column = 2.0 / 3.0 * x / hexSize 348 row = (-1.0 / 3.0 * x + 1.0 / 3.0 * math.sqrt(3.0) * y) / hexSize 349 else: 350 column = (1.0 / 3.0 * math.sqrt(3.0) * x - 1.0 / 3.0 * y) / hexSize 351 row = 2.0 / 3.0 * y / hexSize 352 return (column, row) 353 354 355 def axial_to_cube_coordinate(column, row): 356 x = column 357 z = row 358 y = -x - z 359 return (x, y, z) 360 361 362 def cube_to_axial_coordinate(x, y, z): 363 column = x 364 row = z 365 return (column, row) 366 367 368 def cube_to_odd_r_axial_coordinate(x, y, z): 369 column = x + (z - (z & 1)) / 2 370 row = z 371 return (column, row) 372 373 374 def cube_to_odd_q_axial_coordinate(x, y, z): 375 column = x 376 row = z + (x - (x & 1)) / 2 377 return (column, row) 378 379 380 def sphere_line_intersection(l1, l2, sp, r): 381 x1, _, y1 = l1 382 x2, _, y2 = l2 383 x, _, y = sp 384 A = x - x1 385 B = y - y1 386 C = x2 - x1 387 D = y2 - y1 388 dot = A * C + B * D 389 len_sq = C * C + D * D 390 param = dot / len_sq 391 if param < 0: 392 xx = x1 393 yy = y1 394 elif param > 1: 395 xx = x2 396 yy = y2 397 else: 398 xx = x1 + param * C 399 yy = y1 + param * D 400 diffVec = geo2.Vec2Subtract((x, y), (xx, yy)) 401 return diffVec 402 403 def square(f): 404 return f * f 405 406 p1 = p2 = None 407 a = square(l2[0] - l1[0]) + square(l2[1] - l1[1]) + square(l2[2] - l1[2]) 408 b = 2.0 * ((l2[0] - l1[0]) * (l1[0] - sp[0]) + (l2[1] - l1[1]) * (l1[1] - sp[1]) + (l2[2] - l1[2]) * (l1[2] - sp[2])) 409 c = square(sp[0]) + square(sp[1]) + square(sp[2]) + square(l1[0]) + square(l1[1]) + square(l1[2]) - 2.0 * (sp[0] * l1[0] + sp[1] * l1[1] + sp[2] * l1[2]) - square(r) 410 i = b * b - 4.0 * a * c 411 from math import sqrt 412 if i < 0.0: 413 pass 414 elif i == 0.0: 415 p[0] = 1.0 416 mu = -b / (2.0 * a) 417 p1 = (l1[0] + mu * (l2[0] - l1[0]), l1[1] + mu * (l2[1] - l1[1]), l1[2] + mu * (l2[2] - l1[2])) 418 elif i > 0.0: 419 mu = (-b + sqrt(i)) / (2.0 * a) 420 p1 = (l1[0] + mu * (l2[0] - l1[0]), l1[1] + mu * (l2[1] - l1[1]), l1[2] + mu * (l2[2] - l1[2])) 421 mu = (-b - sqrt(i)) / (2.0 * a) 422 p2 = (l1[0] + mu * (l2[0] - l1[0]), l1[1] + mu * (l2[1] - l1[1]), l1[2] + mu * (l2[2] - l1[2])) 423 return (p1, p2)