Constructs the convex hull of a set of 2D points using a brute force algorithm. The algorithm basically considers all combinations of points (i, j) and uses the definition of convexity to determine whether (i, j) is part of the convex hull or not. (i, j) is part of the convex hull
(points: list[Point])
| 221 | |
| 222 | |
| 223 | def convex_hull_bf(points: list[Point]) -> list[Point]: |
| 224 | """ |
| 225 | Constructs the convex hull of a set of 2D points using a brute force algorithm. |
| 226 | The algorithm basically considers all combinations of points (i, j) and uses the |
| 227 | definition of convexity to determine whether (i, j) is part of the convex hull or |
| 228 | not. (i, j) is part of the convex hull if and only iff there are no points on both |
| 229 | sides of the line segment connecting the ij, and there is no point k such that k is |
| 230 | on either end of the ij. |
| 231 | |
| 232 | Runtime: O(n^3) - definitely horrible |
| 233 | |
| 234 | Parameters |
| 235 | --------- |
| 236 | points: array-like of object of Points, lists or tuples. |
| 237 | The set of 2d points for which the convex-hull is needed |
| 238 | |
| 239 | Returns |
| 240 | ------ |
| 241 | convex_set: list, the convex-hull of points sorted in non-decreasing order. |
| 242 | |
| 243 | See Also |
| 244 | -------- |
| 245 | convex_hull_recursive, |
| 246 | |
| 247 | Examples |
| 248 | --------- |
| 249 | >>> convex_hull_bf([[0, 0], [1, 0], [10, 1]]) |
| 250 | [(0.0, 0.0), (1.0, 0.0), (10.0, 1.0)] |
| 251 | >>> convex_hull_bf([[0, 0], [1, 0], [10, 0]]) |
| 252 | [(0.0, 0.0), (10.0, 0.0)] |
| 253 | >>> convex_hull_bf([[-1, 1],[-1, -1], [0, 0], [0.5, 0.5], [1, -1], [1, 1], |
| 254 | ... [-0.75, 1]]) |
| 255 | [(-1.0, -1.0), (-1.0, 1.0), (1.0, -1.0), (1.0, 1.0)] |
| 256 | >>> convex_hull_bf([(0, 3), (2, 2), (1, 1), (2, 1), (3, 0), (0, 0), (3, 3), |
| 257 | ... (2, -1), (2, -4), (1, -3)]) |
| 258 | [(0.0, 0.0), (0.0, 3.0), (1.0, -3.0), (2.0, -4.0), (3.0, 0.0), (3.0, 3.0)] |
| 259 | """ |
| 260 | |
| 261 | points = sorted(_validate_input(points)) |
| 262 | n = len(points) |
| 263 | convex_set = set() |
| 264 | |
| 265 | for i in range(n - 1): |
| 266 | for j in range(i + 1, n): |
| 267 | points_left_of_ij = points_right_of_ij = False |
| 268 | ij_part_of_convex_hull = True |
| 269 | for k in range(n): |
| 270 | if k not in {i, j}: |
| 271 | det_k = _det(points[i], points[j], points[k]) |
| 272 | |
| 273 | if det_k > 0: |
| 274 | points_left_of_ij = True |
| 275 | elif det_k < 0: |
| 276 | points_right_of_ij = True |
| 277 | # point[i], point[j], point[k] all lie on a straight line |
| 278 | # if point[k] is to the left of point[i] or it's to the |
| 279 | # right of point[j], then point[i], point[j] cannot be |
| 280 | # part of the convex hull of A |
no test coverage detected