Skip to content

compas_model.geometry ¤

Functions¤

combine_aabbs ¤

combine_aabbs(boxes: list[Box]) -> Box

Combine multiple axis-aligned bounding boxes into a single axis-aligned bounding box.

Parameters:

  • boxes (list[Box]) –

    A list of axis-aligned bounding boxes.

Returns:

combine_obbs ¤

combine_obbs(boxes: list[Box]) -> Box

Combine multiple oriented bounding boxes into a single oriented bounding box.

Parameters:

  • boxes (list[Box]) –

    A list of oriented bounding boxes.

Returns:

intersection_ray_triangle ¤

intersection_ray_triangle(line: Line, triangle: list[Point]) -> Point | None

Compute the intersection between a ray and a triangle.

Parameters:

  • line (Line) –

    The ray.

  • triangle (list[Point]) –

    The triangle as a list of three points.

Results

Point | None The intersection point if one exists.

Notes

The function is an implementation of the Möller-Trumbore intersection algorithm 1.

  1. https://en.wikipedia.org/wiki/M%C3%B6ller%E2%80%93Trumbore_intersection_algorithm ↩

intersections_line_aabb ¤

intersections_line_aabb(line: Line, box: Box) -> tuple[int, list[Point]]

Find the intersections between a line and an axis aligned box.

Parameters:

  • line (Line) –

    The line.

  • box (Box) –

    An axis aligned box.

Returns:

  • tuple[bool, list[Point]] –

    The number of intersections, and a list of intersection points. If the number of intersections is 0 (zero), the list is empty. If the number of intersections is 1 (one), the list contains two identical points. If the number of intersections is 2 (two), the list contains two distinct points.

intersections_line_box ¤

intersections_line_box(line: Line, box: Box) -> tuple[int, list[Point]]

Find the intersections between a line and a box.

Parameters:

  • line (Line) –

    The line.

  • box (Box) –

    An oriented box.

Returns:

  • tuple[bool, list[Point]] –

    The number of intersections, and a list of intersection points. If the number of intersections is 0 (zero), the list is empty. If the number of intersections is 1 (one), the list contains two identical points. If the number of intersections is 2 (two), the list contains two distinct points.

intersections_ray_aabb ¤

intersections_ray_aabb(ray: Line, box: Box) -> tuple[int, list[Point]]

Find the intersections between a ray and an axis aligned box.

Parameters:

  • ray (Line) –

    The ray.

  • box (Box) –

    An axis aligned box.

Returns:

  • tuple[bool, list[Point]] –

    The number of intersections, and a list of intersection points. If the number of intersections is 0 (zero), the list is empty. If the number of intersections is 1 (one), the list contains two identical points. If the number of intersections is 2 (two), the list contains two distinct points.

intersections_ray_box ¤

intersections_ray_box(ray: Line, box: Box) -> tuple[int, list[Point]]

Find the intersections between a ray and a box.

Parameters:

  • ray (Line) –

    The line.

  • box (Box) –

    An oriented box.

Returns:

  • tuple[bool, list[Point]] –

    The number of intersections, and a list of intersection points. If the number of intersections is 0 (zero), the list is empty. If the number of intersections is 1 (one), the list contains two identical points. If the number of intersections is 2 (two), the list contains two distinct points.

is_collision_poly_poly_xy ¤

is_collision_poly_poly_xy(A: Polygon, B: Polygon) -> bool

Determine whether two convex polygons collide in the XY plane using the GJK algorithm.

Parameters:

  • A (Polygon) –

    The first polygon.

  • B (Polygon) –

    The second polygon.

Returns:

  • bool –

    True if the polygons collide. False otherwise.

Raises:

  • RuntimeError –

    If the GJK algorithm doesn't converge after 100 iterations.

Warnings

Only works for convex polygons in the XY plane.

Examples:

>>> from compas.geometry import Polygon
>>> from compas_model.geometry import is_collision_poly_poly_xy

Construct two polygons in the XY plane.

>>> A = Polygon.from_rectangle([0, 0, 0], 2, 1)
>>> B = Polygon.from_rectangle([1.5, 0.5, 0], 1, 1)

Check if the polygons collide.

>>> is_collision_poly_poly_xy(A, B)
True

is_intersection_box_box ¤

is_intersection_box_box(a: Box, b: Box) -> bool

Determine whether a box intersects another box.

Parameters:

  • a (Box) –

    The first box.

  • b (Box) –

    The second box.

Returns:

  • bool –

    True if the boxes intersect. False otherwise.

Notes

The algorithm uses the method of separating axes, which states, for two convex objects: If there exists a line for which the intervals of projection of the two objects onto that line do not intersect, then the objects do not intersect.

The underlying theorem is described here 1.

For two oriented (bounding) boxes, this can be formulated in the form of 15 axis checks, based on the coordinate frames of the boxes, and the box coordinate extents.

  1. https://en.wikipedia.org/wiki/Hyperplane_separation_theorem ↩

Examples:

>>> from compas.geometry import Box, Frame
>>> from compas_model.geometry import is_intersection_box_box

>>> A = Box(2, 2, 2)
>>> B = Box(1, 1, 1, frame=Frame(point=[1, 1, 1], xaxis=[1, 1, 0], yaxis=[-1, 1, 0]))

>>> is_intersection_box_box(A, B)
True

is_intersection_line_aabb ¤

is_intersection_line_aabb(line: Line, box: Box) -> bool

Determine whether a line intersects with an aligned box.

Parameters:

  • line (Line) –

    The line.

  • box (Box) –

    The test box.

Returns:

is_intersection_line_box ¤

is_intersection_line_box(line: Line, box: Box) -> bool

Determine whether a line intersects an oriented box.

Parameters:

  • line (Line) –

    The line.

  • box (Box) –

    The box.

Returns:

  • bool –

    True if the line intersects the box. False otherwise.

is_intersection_ray_aabb ¤

is_intersection_ray_aabb(ray: Line, box: Box) -> bool

Determine whether a ray intersects an axis aligned box.

Parameters:

  • ray (Line) –

    The ray.

  • box (Box) –

    The box.

Returns:

  • bool –

    True if the ray intersects the box. False otherwise.

is_intersection_ray_box ¤

is_intersection_ray_box(ray: Line, box: Box) -> bool

Determine whether a ray intersects a box.

Parameters:

  • ray (Line) –

    The ray.

  • box (Box) –

    The box.

Returns:

  • bool –

    True if the ray intersects the box. False otherwise.

is_intersection_segment_aabb ¤

is_intersection_segment_aabb(segment: Line, box: Box) -> bool

Determine whether a segment intersects an axis aligned box.

Parameters:

  • segment (Line) –

    The segment.

  • box (Box) –

    The box.

Returns:

  • bool –

    True if the segmnet intersects the box. False otherwise.

Warnings

The name of this function can be misleading, since it returns True not only when the segment intersects the box boundary, but also when the segment is contained inside the box.

This makes sense if you think of the box as a "solid", but is less intuitive when you think of it as a "shell".

See Also

Examples:

Note that :class:Line can be used as an infinite line, a rays, and as a segment between the two points at t=0 and t=1.

>>> from compas.geometry import Line
>>> from compas.geometry import Box
>>> from compas_model.geometry import is_intersection_segment_aabb

Create a box centered at the origin.

>>> box = Box(1, 1, 1)

A segment crossing the box boundary intersects the box.

>>> line = Line([0, 0, 0], [1, 0, 0])
>>> is_intersection_segment_aabb(line, box)
True

A segment contained inside the box interiro intersects the box.

>>> line = Line([0, 0, 0], [0.1, 0, 0])
>>> is_intersection_segment_aabb(line, box)
True

A segment outside the box but with one point on the box boundary intersects the box.

>>> line = Line([0.5, 0, 0], [1.5, 0, 0])
>>> is_intersection_segment_aabb(line, box)
True

A segment outside the box doesn't intersect the box.

>>> line = Line([1.0, 0, 0], [2.0, 0, 0])
>>> is_intersection_segment_aabb(line, box)
False

is_intersection_segment_box ¤

is_intersection_segment_box(segment: Line, box: Box) -> bool

Determine whether a segment intersects a box.

Parameters:

  • segment (Line) –

    The segment.

  • box (Box) –

    The box.

Returns:

  • bool –

    True if the segment intersects the box. False otherwise.

is_intersection_sphere_aabb ¤

is_intersection_sphere_aabb(sphere: Sphere, box: Box) -> bool

Determine whether a sphere intersects an axis-aligned box.

Parameters:

  • sphere (Sphere) –

    The sphere.

  • box (Box) –

    The box.

Returns:

  • bool –

    True if the sphere intersects the aabb. False otherwise.

is_intersection_sphere_box ¤

is_intersection_sphere_box(sphere: Sphere, box: Box) -> bool

Determine whether a sphere intersects an oriented box.

Parameters:

  • sphere (Sphere) –

    The sphere.

  • box (Box) –

    The box.

Returns:

  • bool –

    True if the sphere intersects the box. False otherwise.

minkowski_difference_xy ¤

minkowski_difference_xy(A: Polygon, B: Polygon) -> Polygon

Compute the Minkowski difference of convex polygons A and B in the XY plane.

Parameters:

  • A (Polygon) –

    The first polygon.

  • B (Polygon) –

    The second polygon.

Returns:

  • Polygon –

    The polygon representing the difference as the sum of A and -B.

Warnings

Currently only convex polygons are supported.

See Also
Notes

The Minkwoski "difference" of two polygons A and B, can be formulated as the Minkowski sum of A and inverted B: A + (-B). 1

A useful application of the Minkowski difference of two convex polygons A and B is collision detection. If the origin (0, 0) is contained in the difference polygon A + (-B), then a collision between A and B exists.

  1. https://en.wikipedia.org/wiki/Minkowski_addition ↩

Examples:

>>> from compas.geometry import Polygon
>>> from compas.geometry import is_point_in_convex_polygon_xy
>>> from compas_model.geometry import minkowski_difference_xy

>>> A = Polygon.from_rectangle([1, 0, 0], 1, 1)
>>> B = Polygon.from_sides_and_radius_xy(5, 1).translated([2.5, 1, 0])
>>> C = minkowski_difference_xy(A, B)

>>> is_point_in_convex_polygon_xy([0, 0, 0], C)
True

minkowski_sum_xy ¤

minkowski_sum_xy(A: Polygon, B: Polygon) -> Polygon

Compute the Minkowski sum of two polygons.

Parameters:

  • A (Polygon) –

    The first polygon.

  • B (Polygon) –

    The second polygon.

Returns:

  • Polygon –

    The polygon representing the sum.

Warnings

Currently only convex polygons are supported.

See Also

pca_box ¤

pca_box(points: list[Point]) -> Box

Compute an oriented bounding box for the given points based on the principle components of the XYZ coordinates.

Parameters:

  • points (list[Point]) –

    A list of 3D points.

Returns:

See Also
Notes

The resulting box is not (necessarily) a minimum bounding volume. The box is computed by reprojecting the points onto the principle component vectors to identify the box extents. The origin of the box is found as the centroid of the points, corrected with the box extents.

Examples:

>>> import random
>>> import math
>>> from compas.geometry import Pointcloud
>>> from compas.geometry import Translation, Rotation
>>> from compas_model.geometry import pca_box

Construct a cloud of points.

>>> cloud = Pointcloud.from_bounds(8, 3, 1, 53)

Construct a random translation.

>>> vector = [10 * random.random(), 10 * random.random(), 10 * random.random()]
>>> T = Translation.from_vector(vector)

Construct a random rotation.

>>> axis = [random.random(), random.random(), random.random()]
>>> angle = math.radians(random.random() * 180)
>>> R = Rotation.from_axis_and_angle(axis, angle)

Transform the cloud and compute its PCA box.

>>> cloud.transform(T * R)
>>> box = pca_box(cloud)

Check.

>>> all(box.contains_point(point) for point in cloud)
True