Created
January 14, 2024 18:38
-
-
Save eladn/5201862078bd9d85cc66fe749db61300 to your computer and use it in GitHub Desktop.
Find four extreme vertices of a quadrilateral given a set of sampled points within it.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import numpy as np | |
| import matplotlib | |
| def find_extreme_vertices_of_sampled_quadrilateral(points: np.ndarray) -> np.ndarray: # points.shape: [:, 2] | |
| assert points.ndim == 2 and points.shape[-1] == 2 | |
| min_x, min_y = min(points[:, 0]), min(points[:, 1]) | |
| max_x, max_y = max(points[:, 0]), max(points[:, 1]) | |
| is_min_x = np.isclose(points[:, 0], min_x) | |
| min_y_at_min_x, max_y_at_min_x = min(points[is_min_x][..., 1]), max(points[is_min_x][..., 1]) | |
| is_max_x = np.isclose(points[:, 0], max_x) | |
| min_y_at_max_x, max_y_at_max_x = min(points[is_max_x][..., 1]), max(points[is_max_x][..., 1]) | |
| is_min_y = np.isclose(points[:, 1], min_y) | |
| min_x_at_min_y, max_x_at_min_y = min(points[is_min_y][..., 0]), max(points[is_min_y][..., 0]) | |
| is_max_y = np.isclose(points[:, 1], max_y) | |
| min_x_at_max_y, max_x_at_max_y = min(points[is_max_y][..., 0]), max(points[is_max_y][..., 0]) | |
| all_candidate_extreme_points = [ | |
| [min_x, min_y_at_min_x], | |
| [min_x, max_y_at_min_x], | |
| [max_x, min_y_at_max_x], | |
| [max_x, max_y_at_max_x], | |
| [min_x_at_min_y, min_y], | |
| [max_x_at_min_y, min_y], | |
| [min_x_at_max_y, max_y], | |
| [max_x_at_max_y, max_y], | |
| ] | |
| # Find distinct candidates | |
| sorted_candidate_points = sorted(all_candidate_extreme_points, key=lambda xy: (xy[0], xy[1])) | |
| sorted_distinct_candidate_points = [] | |
| for point in sorted_candidate_points: | |
| if len(sorted_distinct_candidate_points) > 0 and np.allclose(sorted_distinct_candidate_points[-1], point): | |
| continue | |
| sorted_distinct_candidate_points.append(point) | |
| assert len(sorted_distinct_candidate_points) == 4 | |
| sorted_distinct_candidate_points = np.array(sorted_distinct_candidate_points) | |
| # Sort clockwise | |
| center_of_mass = np.array([np.mean(max_x + min_x) / 2, np.mean(max_y + min_y) / 2]) | |
| xs_offsets = sorted_distinct_candidate_points[:, 0] - center_of_mass[0] | |
| ys_offsets = sorted_distinct_candidate_points[:, 1] - center_of_mass[1] | |
| angles = np.arctan2(ys_offsets, xs_offsets) | |
| clockwise_sorted_vertices = sorted_distinct_candidate_points[np.argsort(angles)] | |
| # Verify that all input points are indeed in the produced quadrilateral. | |
| closed_path = matplotlib.path.Path(np.array(list(clockwise_sorted_vertices) + [clockwise_sorted_vertices[0]])) | |
| if not np.all(closed_path.contains_points(points, radius=1e-5)): | |
| raise ValueError("Input points don't represent a quadrilateral.") | |
| return clockwise_sorted_vertices |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment