muspan.shape_operations.helpers package#

Submodules#

muspan.shape_operations.helpers.are_points_clockwise_oriented module#

are_points_clockwise_oriented(points)#

Determine if a set of 2D points are oriented in a clockwise direction.

Parameters:

pointsarray-like: An array of 2D points.

Returns:

bool: True if the points are clockwise oriented, False otherwise.

muspan.shape_operations.helpers.distance_point_to_line_segment module#

distance_point_to_line_segment(point, v1, v2)#

Calculate the minimum distance from a point to a line segment.

Parameters:

pointarray_like: Coordinates of the point (1xd).
v1array_like: Coordinates of one end of the line segment (1xd).
v2array_like: Coordinates of the other end of the line segment (1xd).

Returns:

float: The minimum distance from the point to the line segment.
tuple: A tuple containing the original point and the closest point on the line segment.

muspan.shape_operations.helpers.distance_point_to_polygon module#

distance_point_to_polygon(point, polygon_edges)#

Calculate the minimum distance from a point to the closest edge of a polygon.

Parameters:

pointarray-like: Coordinates of the point (1xd).
polygon_edgeslist of array-like: List of polygon edges, each defined by two vertices [[v1, v2], [v2, v3], …, [vn-1, vn], [vn, v1]].

Returns:

mindist: The minimum distance from the point to the closest edge of the polygon.
points: Tuple containing (point, closepoint), the original point and its closest point on the polygon edge.

muspan.shape_operations.helpers.distance_polygon_to_polygon module#

distance_polygon_to_polygon(polygon_edges_1, polygon_edges_2)#

Return the minimum distance between two polygons.

Parameters:

polygon_edges_1list: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
polygon_edges_2list: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].

Returns:

float: The minimum distance between the two polygons.
tuple: The closest points on each polygon that define the minimum distance.

muspan.shape_operations.helpers.do_polygons_intersect module#

do_polygons_intersect(polygon_edges_A, polygon_edges_B)#

Check whether two polygons overlap.

This function tests whether two polygons overlap when the region of overlap is not needed (e.g., for testing unions).

Parameters:

polygon_edges_Alist: List of polygon edges for the first polygon, in the form [[v1, v2], [v2, v3], …, [vn-1, vn], [vn, v1]].
polygon_edges_Blist: List of polygon edges for the second polygon, in the form [[v1, v2], [v2, v3], …, [vn-1, vn], [vn, v1]].

Returns:

bool: Boolean indicating whether the two polygons have any degree of overlap.

muspan.shape_operations.helpers.do_shapes_intersect module#

do_shapes_intersect(exterior_edges_A, interior_edges_A, exterior_edges_B, interior_edges_B)#

Check whether the intersection between two shapes (which may have internal boundaries) is non-zero.

Parameters:

exterior_edges_Alist: List of polygon edges for shape A, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
interior_edges_Alist: List of lists of polygon edges for internal boundaries of shape A, in the form [ [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]], … ].
exterior_edges_Blist: List of polygon edges for shape B, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
interior_edges_Blist: List of lists of polygon edges for internal boundaries of shape B, in the form [ [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]], … ].

Returns:

polygons_overlapbool: Boolean describing whether the two polygons have any degree of overlap.

muspan.shape_operations.helpers.find_line_intersections_2D module#

find_line_intersections_2D(line1, line2)#

Identify whether two 2D line segments intersect, and if they do, find and return their point of intersection.

Parameters:

line1array_like: Line segment of the form [[px, py], [qx, qy]].
line2array_like: Line segment of the form [[px, py], [qx, qy]].

Returns:

segments_intersectionbool: Returns True if the line segments intersect, otherwise returns False
point_of_intersectionndarray: 2D array [ix, iy] containing the intersection point, or a line segment [[i1x, i1y], [i2x, i2y]] if the lines are co-linear.

Raises:

ValueError: If attempting to find line intersections for a line of zero length.

signed_triangle_area_times_2(A, B, C)#

triplet_orientation(A, B, C)#

muspan.shape_operations.helpers.get_intersection_area_circle_and_polygon module#

get_intersection_area_circle_and_polygon(point, r, polygon_vertices)#

Calculate the area of intersection between a circle and a polygon. This function computes the area of intersection between a circle of radius r centered at point and a polygon defined by polygon_vertices. It uses a modified version of the shoelace formula to combine signed areas of triangles formed by polygon edges and the point with signed areas of circle sectors inside the polygon.

Parameters:

pointarray_like: The center of the circle. Should be a 2-element array-like object representing the x and y coordinates.
rfloat: The radius of the circle.
polygon_verticesarray_like: A list or array of vertices defining the polygon. Each vertex should be a 2-element array-like object representing the x and y coordinates.

Returns:

float: The area of intersection between the circle and the polygon.

Notes

The function assumes that the polygon vertices are ordered in a clockwise direction.
The function handles cases where the polygon is fully contained within the circle or vice versa.
The function uses a combination of geometric and trigonometric methods to determine the intersection points and areas.

muspan.shape_operations.helpers.get_polygon_intersection_points module#

get_candidates_from_merging_newpair_into_list(order_list, next_pair)#

get_polygon_intersection_points(polygon_edges_A, polygon_edges_B, return_edge_intersection_indices=False)#

Return all points at which edges of two polygons intersect.

Parameters:

polygon_edges_Alist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
polygon_edges_Blist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
return_edge_intersection_indicesbool, optional: If True, return the indices of the edges that intersect.

Returns:

intersection_pointslist: List of points at which two polygons intersect.
intersection_lineslist: List of line segments along which two polygons intersect.
edge_intersection_indicestuple of lists, optional: If return_edge_intersection_indices is True, returns a tuple of lists containing the indices of the edges that intersect.

muspan.shape_operations.helpers.get_polygon_intersection_regions module#

find_an_intersection_region_from_starting_point(all_verts, edge_intersection_indices, starting_edge_intersection_index, polygons, index_trackers)#

get_area(polygon_edges)#

get_polygon_intersection_regions(polygon_edges_A, polygon_edges_B)#

Return outline of the intersection between two polygons. Note there may be multiple distinct regions of intersection.

Parameters:

polygon_edges_Alist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
polygon_edges_Blist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].

Returns:

list: m x n x 2 list of polygon edges defining m regions of intersection.

muspan.shape_operations.helpers.get_polygon_subtraction_regions module#

find_a_subtraction_region_from_starting_point(all_verts, edge_intersection_indices, starting_edge_intersection_index, polygons, index_trackers)#

get_polygon_subtraction_regions(polygon_edges_A, polygon_edges_B)#

Return outline of one polygon minus another. Note there may be multiple distinct regions.

Parameters:

polygon_edges_Alist: List of polygon edges for the first polygon, in the form [[v1,v2], [v2,v3], …, [vn-1,vn], [vn,v1]].
polygon_edges_Blist: List of polygon edges for the second polygon, in the form [[v1,v2], [v2,v3], …, [vn-1,vn], [vn,v1]].

Returns:

list: m x n x 2 list of polygon edges defining m regions.

muspan.shape_operations.helpers.get_polygon_union_regions module#

find_a_union_region_from_starting_point(all_verts, edge_intersection_indices, starting_edge_intersection_index, polygons, index_trackers)#

get_polygon_union_regions(polygon_edges_A, polygon_edges_B)#

Return outline of the union between two polygons. Note there may be multiple distinct regions.

Parameters:

polygon_edges_Alist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
polygon_edges_Blist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].

Returns:

list: m x n x 2 list of polygon edges defining m polygons.

muspan.shape_operations.helpers.get_union_of_set_of_shapes module#

coords_to_poly(coords)#

get_union_of_set_of_shapes(shapes)#

Compute the union of a set of shapes.

This function takes a list of shapes, where each shape is defined by its outer boundary and interior boundaries. It groups shapes that intersect into buckets and then computes the union of shapes within each bucket.

Parameters:

shapeslist of dict: A list of shapes, where each shape is represented as a dictionary with keys ‘outer boundary’ and ‘interior boundary’. The ‘outer boundary’ is a list of coordinates defining the outer boundary of the shape. The ‘interior boundary’ is a list of lists of coordinates, where each list defines an interior boundary (hole) of the shape.

Returns:

list of dict: A list of shapes representing the union of the input shapes. Each shape is represented as a dictionary with keys ‘outer boundary’ and ‘interior boundary’.

Raises:

ValueError: If the union of overlapping shapes results in multiple connected components, which should not occur.

Notes

This function assumes that the input shapes are properly formatted and that the coordinates are in a suitable format for geometric operations. The function uses helper functions coords_to_poly, do_shapes_intersect, and return_union_of_shapes_from_boundaries which are not defined in this scope.

Examples

>>> shapes = [
...     {'outer boundary': [(0, 0), (2, 0), (2, 2), (0, 2)], 'interior boundary': []},
...     {'outer boundary': [(1, 1), (3, 1), (3, 3), (1, 3)], 'interior boundary': []}
... ]
>>> result = get_union_of_set_of_shapes(shapes)
>>> print(result)
[{'outer boundary': [(0, 0), (2, 0), (2, 2), (3, 2), (3, 3), (1, 3), (1, 1), (0, 1)], 'interior boundary': []}]

muspan.shape_operations.helpers.point_in_polygon module#

point_in_polygon(point, polygon_edges)#

Determine if a 2D polygon contains a point.

Parameters:

pointtuple: A tuple representing the point (px, py).
polygon_edgeslist: A list of polygon edges, where each edge is represented as a tuple of two vertices (v1, v2).

Returns:

bool: True if the point is inside the polygon or on its boundary, False otherwise.

muspan.shape_operations.helpers.polygon_in_polygon module#

polygon_in_polygon(polygon_edges_A, polygon_edges_B)#

Test whether polygon_A is fully contained by polygon_B.

Returns true only if there are no intersections between polygon_A and polygon_B, and polygon_A is fully enclosed by the edges of polygon_B.

Parameters:

polygon_edges_Alist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].
polygon_edges_Blist: List of polygon edges, in the form [[v1,v2],[v2,v3],…,[vn-1,vn],[vn,v1]].

Returns:

bool: True if the entirety of polygon_A is contained within polygon_B.

muspan.shape_operations.helpers.remove_zero_length_polygon_edges module#

remove_zero_length_polygon_edges(polygon_edges)#

Remove zero-length polygon edges.

Deletes edges of the form [vi, vj] where vertex vi == vertex vj.

Parameters:

polygon_edgeslist: List of polygon edges, in the form [[v1, v2], [v2, v3], …, [vn-1, vn], [vn, v1]].

Returns:

list: List of polygon edges, with zero-length edges removed.

muspan.shape_operations.helpers.return_difference_of_shapes_from_boundaries module#

coords_to_poly(coords)#

return_difference_of_shapes_from_boundaries(shape_A_exterior, shape_A_interiors, shape_B_exterior, shape_B_interiors)#

Compute the difference of two shapes defined by their boundaries. This function calculates the difference between two shapes, A and B, defined by their exterior and interior boundaries. The result is a list of regions representing the difference of the shapes.

Parameters:

shape_A_exteriorlist: Coordinates defining the exterior boundary of shape A.
shape_A_interiorslist of lists: List of coordinates defining the interior boundaries (holes) of shape A.
shape_B_exteriorlist: Coordinates defining the exterior boundary of shape B.
shape_B_interiorslist of lists: List of coordinates defining the interior boundaries (holes) of shape B.

Returns:

list of dict: A list of dictionaries, each representing a region in the difference of the shapes. Each dictionary contains: - ‘outer boundary’: Coordinates of the outer boundary of the region. - ‘visited_indices_exterior’: Indices of the visited exterior vertices. - ‘intersection_points’: Points of intersection between the shapes. - ‘interior boundary’: Coordinates of the interior boundaries (holes) of the region. - ‘visited_indices_interior’: Indices of the visited interior vertices.

Notes

The function handles cases where the difference operation results in disconnected shapes and accounts for both exterior and interior boundaries.

muspan.shape_operations.helpers.return_intersection_of_shapes_from_boundaries module#

coords_to_poly(coords)#

return_intersection_of_shapes_from_boundaries(shape_A_exterior, shape_A_interiors, shape_B_exterior, shape_B_interiors)#

Compute the intersection of two shapes defined by their exterior and interior boundaries. This function calculates the intersection of two shapes, A and B, where each shape is specified by its exterior boundary and a list of interior boundaries (holes). The intersection is computed by finding the intersection of the exterior boundaries and then subtracting the union of the interior boundaries from the resulting region.

Parameters:

shape_A_exteriorarray-like: Coordinates of the exterior boundary of shape A.
shape_A_interiorslist of array-like: List of coordinates for the interior boundaries (holes) of shape A.
shape_B_exteriorarray-like: Coordinates of the exterior boundary of shape B.
shape_B_interiorslist of array-like: List of coordinates for the interior boundaries (holes) of shape B.

Returns:

list of dict: A list of dictionaries, each representing a region of the intersection. Each dictionary contains: - ‘outer boundary’: array-like, coordinates of the outer boundary of the region. - ‘interior boundary’: list of array-like, coordinates of the interior boundaries (holes) of the region.

Notes

This function is a specialized version of return_union_of_shapes where shapes are specified by their interior and exterior boundaries, not by object IDs. It should be merged with return_intersection_of_shapes as there is no need for both functions.

muspan.shape_operations.helpers.return_union_of_shapes_from_boundaries module#

return_union_of_shapes_from_boundaries(shape_A_exterior, shape_A_interiors, shape_B_exterior, shape_B_interiors)#

Compute the union of two shapes specified by their exterior and interior boundaries. This function calculates the union of two shapes, where each shape is defined by its exterior boundary and a list of interior boundaries (holes). The union is computed by considering the exterior boundaries and the interior holes of both shapes.

Parameters:

shape_A_exteriorlist: Coordinates defining the exterior boundary of shape A.
shape_A_interiorslist of lists: List of coordinates defining the interior boundaries (holes) of shape A.
shape_B_exteriorlist: Coordinates defining the exterior boundary of shape B.
shape_B_interiorslist of lists: List of coordinates defining the interior boundaries (holes) of shape B.

Returns:

list: A list of dictionaries, each representing a union region. Each dictionary contains: - ‘outer boundary’: Coordinates of the exterior boundary of the union region. - ‘interior boundary’: List of coordinates defining the interior boundaries (holes) of the union region.

Raises:

ValueError: If the union of non-overlapping shapes is requested, as this is currently undefined.

Notes

This function is a specialized version of return_union_of_shapes where shapes are specified by their interior and exterior boundaries, not by object IDs. The function handles three cases for internal holes: 1. Holes generated from the union of the exterior boundaries. 2. Holes formed by the interior boundary of one shape and the exterior boundary of the other. 3. Holes formed by the intersection of the interior boundaries of both shapes.

muspan.shape_operations.helpers package#

Submodules#

muspan.shape_operations.helpers.are_points_clockwise_oriented module#

muspan.shape_operations.helpers.distance_point_to_line_segment module#

muspan.shape_operations.helpers.distance_point_to_polygon module#

muspan.shape_operations.helpers.distance_polygon_to_polygon module#

muspan.shape_operations.helpers.do_polygons_intersect module#

muspan.shape_operations.helpers.do_shapes_intersect module#

muspan.shape_operations.helpers.find_line_intersections_2D module#

muspan.shape_operations.helpers.get_intersection_area_circle_and_polygon module#

muspan.shape_operations.helpers.get_polygon_intersection_points module#

muspan.shape_operations.helpers.get_polygon_intersection_regions module#

muspan.shape_operations.helpers.get_polygon_subtraction_regions module#

muspan.shape_operations.helpers.get_polygon_union_regions module#

muspan.shape_operations.helpers.get_union_of_set_of_shapes module#

muspan.shape_operations.helpers.point_in_polygon module#

muspan.shape_operations.helpers.polygon_in_polygon module#

muspan.shape_operations.helpers.remove_zero_length_polygon_edges module#

muspan.shape_operations.helpers.return_difference_of_shapes_from_boundaries module#

muspan.shape_operations.helpers.return_intersection_of_shapes_from_boundaries module#

muspan.shape_operations.helpers.return_union_of_shapes_from_boundaries module#

Module contents#