Coverage for backpack/geometry.py: 99%

1''' 2D geometry primitives and implementation of some geometric algorithms. ''' 

2 

3from typing import List, Sequence, Tuple 

4import enum 

5import collections.abc 

6from dataclasses import dataclass 

7import math 

8from itertools import islice, cycle, groupby 

9from numbers import Number 

10import numpy as np 

11 

12from . import lazy_property 

13 

14def _issequence(value): 

15 ''' Returns True if value is a sequence but not a string. ''' 

16 return isinstance(value, collections.abc.Sequence) and not isinstance(value, str) 

17 

18def _issequence_or_numpy(value): 

19 return _issequence(value) or isinstance(value, np.ndarray) 

20 

21class PointMeta(type): 

22 @classmethod 

23 def __instancecheck__(cls, instance): 

24 ''' Any object that has 'x' and 'y' attributes might be considered a Point ''' 

25 return hasattr(instance, 'x') and hasattr(instance, 'y') 

26 

27@dataclass(frozen=True) 

28class Point(metaclass=PointMeta): 

29 ''' A point on the 2D plane. 

30 

31 Args: 

32 x (float): The x coordinate of the point 

33 y (float): The y coordinate of the point 

34 ''' 

35 x: float 

36 ''' The x coordinate of the point ''' 

37 

38 y: float 

39 ''' The y coordinate of the point ''' 

40 

41 @staticmethod 

42 def ccw(pt1: 'Point', pt2: 'Point', pt3: 'Point') -> bool: 

43 ''' Determines if the three points form a counterclockwise angle. If two points are 

44 equal, or the three points are collinear, this method returns `True`. 

45 

46 Args: 

47 pt1: The first point 

48 pt2: The second point 

49 pt3: The third point 

50 

51 Returns: 

52 `True` if the points form a counterclockwise angle 

53 ''' 

54 d21, d31 = pt2 - pt1, pt3 - pt1 

55 return d21.x * d31.y >= d31.x * d21.y 

56 

57 def distance(self, other: 'Point') -> float: 

58 ''' Calculates the distance between this and an other point. 

59 

60 Args: 

61 other: The other point 

62 

63 Returns: 

64 The distance between this and an other point. 

65 ''' 

66 d = self - other 

67 return math.sqrt(d.x * d.x + d.y * d.y) 

68 

69 @classmethod 

70 def _check_arg(cls, arg, method_name): 

71 if not isinstance(arg, cls): 

72 raise TypeError( 

73 f"unsupported operand type(s) for {method_name}: " 

74 f"'{cls.__name__}' and '{type(arg).__name__}'" 

75 ) 

76 

77 def __add__(self, other: 'Point') -> 'Point': 

78 ''' Adds two points as if they were vectors. 

79 

80 Arg: 

81 other: the other point 

82 

83 Returns: 

84 A new point, the sum of the two points as if they were vectors. 

85 ''' 

86 Point._check_arg(other, '+') 

87 return Point(self.x + other.x, self.y + other.y) 

88 

89 def __sub__(self, other: 'Point') -> 'Point': 

90 ''' Subtracts two points as if they were vectors. 

91 

92 Arg: 

93 other: the other point 

94 

95 Returns: 

96 A new point, the difference of the two points as if they were vectors. 

97 ''' 

98 Point._check_arg(other, '-') 

99 return Point(self.x - other.x, self.y - other.y) 

100 

101 def __truediv__(self, divisor: float) -> 'Point': 

102 ''' Interpret this point as a vector and divide it by a real number. 

103 

104 Args: 

105 divisor: a real number 

106 

107 Returns: 

108 The original point divided by the number as if it was a vector. 

109 ''' 

110 return Point(self.x / divisor, self.y / divisor) 

111 

112 

113 def __getitem__(self, key: int) -> float: 

114 ''' Returns the first or the second coordinate of this Point.''' 

115 if not isinstance(key, int): 

116 raise TypeError('Point indices must be integers.') 

117 if key == 0: 

118 return self.x 

119 elif key == 1: 

120 return self.y 

121 else: 

122 raise IndexError(str(key)) 

123 

124 @classmethod 

125 def from_value(cls, value): 

126 ''' Deserializes a Point from different formats. 

127 

128 Supported formats: 

129 

130 - sequence containing exactly two numbers 

131 - dictionary containing numbers under 'x' and 'y' keys 

132 - Point instance (returns the same instance) 

133 

134 Args: 

135 value: the value to be converted 

136 

137 Return: The new Point instance 

138 

139 Raises: 

140 ValueError: If the conversion was not successful. 

141 ''' 

142 if isinstance(value, Point): 

143 return value 

144 elif isinstance(value, collections.abc.Mapping) and 'x' in value and 'y' in value: 

145 return cls(x=value['x'], y=value['y']) 

146 elif ( 

147 _issequence(value) and 

148 len(value) == 2 and 

149 isinstance(value[0], Number) and 

150 isinstance(value[1], Number) 

151 ): 

152 return cls(x=value[0], y=value[1]) 

153 else: 

154 raise ValueError(f'Could not convert {value} to Point.') 

155 

156 

157@dataclass(frozen=True) 

158class Line: 

159 ''' A line segment. 

160 

161 Args: 

162 pt1 (float): The first point of the line segment 

163 pt2 (float): The second point of the line segment 

164 ''' 

165 

166 class Intersection(enum.Enum): 

167 ''' The intersection type of two line segments. ''' 

168 

169 LEFT = -1 

170 ''' The second segment intersects the first one in left direction. ''' 

171 

172 NONE = 0 

173 ''' The two segments do not intersect. ''' 

174 

175 RIGHT = 1 

176 ''' The second segment intersects the first one in right direction. ''' 

177 

178 def __bool__(self) -> bool: 

179 return bool(self.value) 

180 

181 pt1: Point 

182 ''' The first point of the line segment ''' 

183 

184 pt2: Point 

185 ''' The second point of the line segment ''' 

186 

187 def __post_init__(self): 

188 if not isinstance(self.pt1, Point) or not isinstance(self.pt2, Point): 

189 raise ValueError('Line arguments "pt1" and "pt2" must be Point objects.') 

190 

191 def intersects(self, other: 'Line') -> Intersection: 

192 ''' Determines if this line segment intersects an other one. 

193 

194 The direction of intersection is interpreted as follows. Place an observer to the first 

195 point of this line, looking to the second point of this line. If the second point of the 

196 other line is on the left side, the directions of the intersection is "left", otherwise 

197 it is "right". Attention: when considering the line intersection direction, keep in mind 

198 that the geometry module uses the screen coordinate system orientation, i.e. the origin 

199 can be found in the upper left corner of the screen. 

200 

201 Args: 

202 other (Line): The other line segment 

203 

204 Returns: 

205 The line intersection type. 

206 ''' 

207 if ( 

208 Point.ccw(self.pt1, other.pt1, other.pt2) == Point.ccw(self.pt2, other.pt1, other.pt2) or 

209 Point.ccw(self.pt1, self.pt2, other.pt1) == Point.ccw(self.pt1, self.pt2, other.pt2) 

210 ): 

211 return Line.Intersection.NONE 

212 else: 

213 return ( 

214 Line.Intersection.LEFT if Point.ccw(self.pt1, self.pt2, other.pt1) 

215 else Line.Intersection.RIGHT 

216 ) 

217 

218 @classmethod 

219 def from_value(cls, value): 

220 ''' Deserializes a Line from different formats. 

221 

222 Supported formats: 

223 

224 - sequence containing exactly two values that can be deserialized with Point.from_value 

225 - dictionary containing such Point values under 'pt1' and 'pt2' keys 

226 - Line instance (returns the same instance) 

227 

228 Args: 

229 value: the value to be converted 

230 

231 Returns: 

232 The Line instance 

233 

234 Raises: 

235 ValueError: If the value could not be converted to a Line. 

236 ''' 

237 if isinstance(value, Line): 

238 return value 

239 elif _issequence(value) and len(value) == 2: 

240 return cls(pt1=Point.from_value(value[0]), pt2=Point.from_value(value[1])) 

241 elif isinstance(value, collections.abc.Mapping) and 'pt1' in value and 'pt2' in value: 

242 return cls(pt1=Point.from_value(value['pt1']), pt2=Point.from_value(value['pt2'])) 

243 else: 

244 raise ValueError(f'Could not convert {value} to Line.') 

245 

246 def __getitem__(self, key: int) -> Point: 

247 ''' Returns the first or the second point of this Line. 

248 

249 Args: 

250 key: the index passed to the bracket operator, must be 0 or 1. 

251 

252 Returns: 

253 The first or the second point of this Line. 

254 ''' 

255 if not isinstance(key, int): 

256 raise TypeError('Line indices must be integers.') 

257 if key == 0: 

258 return self.pt1 

259 elif key == 1: 

260 return self.pt2 

261 else: 

262 raise IndexError(str(key)) 

263 

264 

265@dataclass(frozen=True) 

266class Rectangle: 

267 ''' An axis aligned rectangle. 

268 

269 Args: 

270 pt1 (Point): The first corner of the rectangle 

271 pt2 (Point): The second corner of the rectangle 

272 ''' 

273 

274 pt1: Point 

275 ''' The first corner of the rectangle ''' 

276 

277 pt2: Point 

278 ''' The second corner of the rectangle ''' 

279 

280 def __post_init__(self): 

281 if not isinstance(self.pt1, Point) or not isinstance(self.pt2, Point): 

282 raise ValueError('Rectangle arguments "pt1" and "pt2" must be Point objects.') 

283 

284 def has_inside(self, pt: Point) -> bool: 

285 ''' Determines if a point is inside this rectangle. 

286 

287 Args: 

288 pt: the point 

289 

290 Returns: 

291 `True` if the point lies inside this rectangle. 

292 ''' 

293 return ( 

294 pt.x >= self.pt_min.x and pt.y >= self.pt_min.y and 

295 pt.x <= self.pt_max.x and pt.y <= self.pt_max.y 

296 ) 

297 

298 @lazy_property 

299 def pt_min(self) -> Point: 

300 ''' The point with the minimum coordinates of this rectangle. ''' 

301 return Point(min(self.pt1.x, self.pt2.x), min(self.pt1.y, self.pt2.y)) 

302 

303 @lazy_property 

304 def pt_max(self) -> Point: 

305 ''' The point with the maximum coordinates of this rectangle. ''' 

306 return Point(max(self.pt1.x, self.pt2.x), max(self.pt1.y, self.pt2.y)) 

307 

308 @lazy_property 

309 def center(self) -> Point: 

310 ''' The center of the rectangle. ''' 

311 return Point((self.pt_min.x + self.pt_max.x) / 2, (self.pt_min.y + self.pt_max.y) / 2) 

312 

313 @lazy_property 

314 def base(self) -> Point: 

315 ''' Returns the center of the base of the rectangle. ''' 

316 return Point((self.pt_min.x + self.pt_max.x) / 2, self.pt_max.y) 

317 

318 @lazy_property 

319 def size(self) -> Tuple[float, float]: 

320 ''' The width and height of the rectangle. ''' 

321 return self.width, self.height 

322 

323 @lazy_property 

324 def width(self) -> float: 

325 ''' The width of the rectangle. ''' 

326 return self.pt_max.x - self.pt_min.x 

327 

328 @lazy_property 

329 def height(self) -> float: 

330 ''' The height of the rectangle. ''' 

331 return self.pt_max.y - self.pt_min.y 

332 

333 @lazy_property 

334 def area(self) -> float: 

335 ''' The area of the rectangle. ''' 

336 return self.width * self.height 

337 

338 @lazy_property 

339 def aspect_ratio(self) -> float: 

340 ''' The aspect ratio of the rectangle. ''' 

341 return self.width / self.height 

342 

343 @property 

344 def top(self) -> float: 

345 ''' The top edge of the rectangle. ''' 

346 return self.pt_min.y 

347 

348 @property 

349 def left(self) -> float: 

350 ''' The left edge of the rectangle. ''' 

351 return self.pt_min.x 

352 

353 @property 

354 def bottom(self) -> float: 

355 ''' The bottom edge of the rectangle. ''' 

356 return self.pt_max.y 

357 

358 @property 

359 def right(self) -> float: 

360 ''' The right edge of the rectangle. ''' 

361 return self.pt_max.x 

362 

363 @property 

364 def tlbr(self) -> Tuple[float, float, float, float]: 

365 ''' Returns this rectangles coordinates as a top-left-bottom-right tuple. ''' 

366 return self.top, self.left, self.bottom, self.right 

367 

368 @property 

369 def tlhw(self) -> Tuple[float, float, float, float]: 

370 ''' Returns this rectangles coordinates as a top-left-width-height tuple. ''' 

371 return self.top, self.left, self.height, self.width 

372 

373 @classmethod 

374 def from_value(cls, value): 

375 ''' Converts a tuple in the form of ((0.1, 0.2), (0.3, 0.4)) to a Rectangle. 

376 

377 Args: 

378 value: the tuple 

379 

380 Returns: 

381 The Rectangle instance 

382 

383 Raises: 

384 ValueError: If the tuple could not be converted to a Rectangle. 

385 ''' 

386 if isinstance(value, Rectangle): 

387 return value 

388 elif _issequence(value) and len(value) == 2: 

389 return cls(pt1=Point.from_value(value[0]), pt2=Point.from_value(value[1])) 

390 elif isinstance(value, collections.abc.Mapping) and 'pt1' in value and 'pt2' in value: 

391 return cls(pt1=Point.from_value(value['pt1']), pt2=Point.from_value(value['pt2'])) 

392 else: 

393 raise ValueError(f'Could not convert {value} to Rectangle.') 

394 

395 

396 @classmethod 

397 def from_tlbr(cls, tlbr: Tuple[float, float, float, float]) -> 'Rectangle': 

398 ''' Converts a top-left-bottom-right sequence of floats to a Rectangle. 

399 

400 Args: 

401 tlbr: A top-left-bottom-right sequence of floats. 

402 

403 Returns: 

404 The Rectangle instance 

405 

406 Raises: 

407 ValueError: If the sequence could not be converted to a Rectangle. 

408 ''' 

409 if _issequence_or_numpy(tlbr) and len(tlbr) == 4: 

410 return cls(pt1=Point(x=tlbr[1], y=tlbr[0]), pt2=Point(x=tlbr[3], y=tlbr[2])) 

411 else: 

412 raise ValueError(f'Could not use {tlbr} as top-left-bottom-right sequence.') 

413 

414 @classmethod 

415 def from_tlhw(cls, tlhw: Tuple[float, float, float, float]) -> 'Rectangle': 

416 ''' Converts a top-left-width-height sequence of floats to a Rectangle. 

417 

418 Args: 

419 tlbr: A top-left-width-height sequence of floats. 

420 

421 Returns: 

422 The Rectangle instance 

423 

424 Raises: 

425 ValueError: If the sequence could not be converted to a Rectangle. 

426 ''' 

427 if _issequence_or_numpy(tlhw) and len(tlhw) == 4: 

428 return cls( 

429 pt1=Point(x=tlhw[1], y=tlhw[0]), 

430 pt2=Point(x=tlhw[1]+tlhw[3], y=tlhw[0]+tlhw[2]) 

431 ) 

432 else: 

433 raise ValueError(f'Could not use {tlhw} as top-left-width-height sequence.') 

434 

435 def __getitem__(self, key: int) -> float: 

436 ''' Returns the first or the second point of this Rectangle. 

437 

438 Args: 

439 key: the index passed to the bracket operator, must be 0 or 1. 

440 

441 Returns: 

442 The first or the second point of this Rectangle. 

443 ''' 

444 if not isinstance(key, int): 

445 raise TypeError('Point.__getitem__ accepts only integer keys.') 

446 if key == 0: 

447 return self.pt_min 

448 elif key == 1: 

449 return self.pt_max 

450 else: 

451 raise IndexError(str(key)) 

452 

453 

454@dataclass(frozen=True) 

455class PolyLine: 

456 ''' A :class:`PolyLine` is a connected series of line segments. 

457 

458 Args: 

459 points: the list of the points of the polyline 

460 closed: `True` if the :class:`PolyLine` is closed 

461 ''' 

462 

463 points : Sequence[Point] 

464 ''' The list of the points of the :class:`PolyLine` ''' 

465 

466 closed : bool = True 

467 ''' `True` if the :class:`PolyLine` is closed. ''' 

468 

469 def __post_init__(self): 

470 if not isinstance(self.points, collections.abc.Sequence): 

471 raise ValueError('PolyLine points argument must be a Sequence.') 

472 if len(self.points) < 2: 

473 raise ValueError('PolyLine should contain at least two points.') 

474 for pt in self.points: 

475 if not isinstance(pt, Point): 

476 raise ValueError('The elements of PolyLine points argument must be Point objects.') 

477 

478 @lazy_property 

479 def lines(self) -> List[Line]: 

480 ''' The line segments of this :class:`PolyLine` ''' 

481 lines = [Line(start, end) for start, end in zip(self.points, self.points[1:])] 

482 if self.closed: 

483 lines.append(Line(self.points[-1], self.points[0])) 

484 return lines 

485 

486 @lazy_property 

487 def boundingbox(self) -> Rectangle: 

488 ''' The bounding box of this :class:`PolyLine` ''' 

489 minx = min(pt.x for pt in self.points) 

490 miny = min(pt.y for pt in self.points) 

491 maxx = max(pt.x for pt in self.points) 

492 maxy = max(pt.y for pt in self.points) 

493 return Rectangle(Point(minx, miny), Point(maxx, maxy)) 

494 

495 @lazy_property 

496 def self_intersects(self) -> bool: 

497 ''' Determines if this :class:`PolyLine` self-intersects. ''' 

498 return any( 

499 l1.intersects(l2) 

500 for idx, l1 in enumerate(self.lines) for l2 in self.lines[idx + 2:] 

501 ) 

502 

503 @lazy_property 

504 def is_convex(self) -> bool: 

505 ''' Determines if the polygon formed from this :class:`PolyLine` is convex. 

506 

507 The result of this method is undefined for complex (self-intersecting) polygons. 

508 

509 Returns: 

510 `True` if the polygon is convex, False otherwise. 

511 ''' 

512 if len(self.points) < 4: 

513 return True 

514 

515 # Iterate over consecutive point triplets 

516 it0 = self.points 

517 it1 = islice(cycle(self.points), 1, None) 

518 it2 = islice(cycle(self.points), 2, None) 

519 

520 # Check if all angles are ccw, see 

521 # https://docs.python.org/3/library/itertools.html#itertools-recipes 

522 group = groupby( 

523 Point.ccw(pt0, pt1, pt2) for pt0, pt1, pt2 in zip(it0, it1, it2) 

524 ) 

525 return next(group, True) and not next(group, False) 

526 

527 def has_inside(self, point: Point) -> bool: 

528 ''' Determines if a point is inside this closed :class:`PolyLine`. 

529 

530 This implementation uses the `ray casting algorithm`_. 

531 

532 .. _`ray casting algorithm`: 

533 https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm 

534 

535 Args: 

536 point: The point 

537 

538 Returns: 

539 `True` if the point is inside this closed :class:`PolyLine`. 

540 ''' 

541 if not self.closed: 

542 raise ValueError('PolyLine.has_inside works only for closed polylines.') 

543 if not self.boundingbox.has_inside(point): 

544 return False 

545 ray = Line(Point(self.boundingbox.pt_min.x - 0.01, self.boundingbox.pt_min.y), point) 

546 n_ints = sum(1 if ray.intersects(line) else 0 for line in self.lines) 

547 return True if n_ints % 2 == 1 else False 

548 

549 @classmethod 

550 def from_value(cls, value, closed=True): 

551 ''' Converts a tuple in the form of ((0.1, 0.2), (0.3, 0.4), ...) to a PolyLine. 

552 

553 Args: 

554 value: the tuple 

555 closed: flags if the newly created PolyLine should be closed or not. 

556 

557 Returns: 

558 The PolyLine instance 

559 

560 Raises: 

561 ValueError: If the tuple could not be converted to a PolyLine. 

562 ''' 

563 if isinstance(value, PolyLine): 

564 return value 

565 elif _issequence(value): 

566 return cls(points=[Point.from_value(pt) for pt in value], closed=closed) 

567 elif isinstance(value, collections.abc.Mapping) and 'points' in value: 

568 closed = bool(value.get('closed', closed)) 

569 return cls(points=[Point.from_value(pt) for pt in value['points']], closed=closed) 

570 else: 

571 raise ValueError(f'Could not convert {value} to PolyLine') 

572 

573 def __getitem__(self, key: int) -> Point: 

574 ''' Returns a single point of this PolyLine. 

575 

576 Args: 

577 key: the index passed to the bracket operator. 

578 

579 Returns: 

580 A single point of this PolyLine. 

581 ''' 

582 if not isinstance(key, int): 

583 raise TypeError('PolyLine indices must be integers.') 

584 return self.points[key] 

585 

586 def __len__(self) -> int: 

587 ''' Returns the number of line segments in this PolyLine. 

588 

589 Returns: 

590 The number of line segments. 

591 ''' 

592 return len(self.points)