CollisionGeometryCalculator

AUTO-GENERATED FILE – DO NOT EDIT MANUALLY

Pure logic class for collision geometry calculations. Contains no state and can be easily tested in isolation.

Source File: addons/grid_building/placement/manager/components/collision_geometry_calculator.gd

Extends: RefCounted

Constants

• Constant: AREA_REL_EPS: float = 0.01 # 1% of tile area as relative tolerance
• Constant: AREA_ABS_EPS: float = 1.0 # 1.0 square units as absolute tolerance

Public Methods

polygons_overlap

1
2
3
4
5
6

polygons_overlap(
    poly1: PackedVector2Array,
    poly2: PackedVector2Array,
    min_overlap_ratio: float,
    reference_area: float
) -> bool

Flags: static

Check if two arbitrary polygons overlap with a minimum overlap ratio Uses Sutherland-Hodgman clipping to compute precise overlap area

polygon_overlaps_rect

1
2
3
4
5
6

polygon_overlaps_rect(
    polygon: PackedVector2Array,
    rect: Rect2,
    epsilon: float,
    min_overlap_ratio: float
) -> bool

Flags: static

This is a critical method that determines which tiles are considered “covered” by a polygon

Algorithm: Uses Sutherland-Hodgman polygon clipping to compute precise overlap area

1. Fast reject via bounding box intersection test
2. Clip polygon to rectangle using Sutherland-Hodgman algorithm
3. Calculate area of clipped polygon using shoelace formula
4. Compare to minimum overlap threshold (min_overlap_ratio * rectangle_area)

The Sutherland-Hodgman algorithm correctly handles both convex and concave polygons, producing accurate overlap areas for all polygon shapes.

clip_polygon_to_rect

1
2
3
4

clip_polygon_to_rect(
    polygon: PackedVector2Array,
    rect: Rect2
) -> PackedVector2Array

Flags: static

Clips a polygon to an axis-aligned rectangle (inclusive). Returns resulting polygon points. PUBLIC for testing - this is the core clipping algorithm that needs validation for concave polygons

Implements the Sutherland-Hodgman polygon clipping algorithm:

• Iteratively clips the polygon against each of the 4 rectangle boundaries
• Each boundary clip produces a new polygon guaranteed to be inside that boundary
• The final result is the intersection of the polygon with the rectangle
• Works correctly for both convex and concave input polygons

Algorithm steps for each boundary:

1. Start with previous vertex (last vertex for first iteration)
2. For each current vertex in the polygon:

• If current vertex is inside boundary: add intersection point (if previous was outside), then add current vertex
• If current vertex is outside boundary: add intersection point (if previous was inside)

3. Repeat for all 4 boundaries (left, right, top, bottom)

The algorithm maintains polygon validity and handles edge cases properly.

point_inside_boundary

1
2
3
4
5
6
7
8

point_inside_boundary(
    p: Vector2,
    boundary: int,
    left: float,
    right: float,
    top: float,
    bottom: float
) -> bool

Flags: static

Checks if a point is inside a boundary edge for clipping PUBLIC for testing - validates point-in-boundary logic used in clipping

Boundary mapping for Sutherland-Hodgman algorithm: 0 = left boundary (x >= left) 1 = right boundary (x <= right) 2 = top boundary (y >= top) 3 = bottom boundary (y <= bottom)

Uses small epsilon (-0.0001) to handle floating-point precision issues and ensure inclusive boundary checking.

polygon_area

1

polygon_area(polygon: PackedVector2Array) -> float

Flags: static

Computes the area of a polygon using the shoelace formula PUBLIC for testing - validates clipped polygon area calculations Calculates the area of a polygon using the shoelace formula Returns absolute area (always positive) for overlap calculations

Shoelace formula: For polygon with vertices (x1,y1), (x2,y2), …, (xn,yn): Area = 1/2 * |Σ(i=1 to n) (xiyi+1 - xi+1yi)| where xn+1 = x1 and yn+1 = y1

This gives the signed area; we take the absolute value for overlap measurements.

point_in_polygon

1
2
3
4

point_in_polygon(
    point: Vector2,
    polygon: PackedVector2Array
) -> bool

Flags: static

Pure function to check if point is inside polygon Pure function to check if point is inside polygon PUBLIC for testing - uses ray casting algorithm for point-in-polygon test

Private Methods

_get_polygon_bounds

1

_get_polygon_bounds(polygon: PackedVector2Array) -> Rect2

Flags: static, private

Pure function to get polygon bounds

_clip_polygon_to_edge

1
2
3
4
5

_clip_polygon_to_edge(
    polygon: PackedVector2Array,
    edge_start: Vector2,
    edge_end: Vector2
) -> PackedVector2Array

Flags: static, private

Pure function to check if polygon overlaps with rectangle - PUBLIC for testing Clip a polygon against a single edge defined by two points Used for general polygon-to-polygon clipping

_line_intersection

1
2
3
4
5
6

_line_intersection(
    p1: Vector2,
    p2: Vector2,
    p3: Vector2,
    p4: Vector2
) -> Vector2

Flags: static, private

Calculate intersection point of two line segments Returns Vector2.INF if lines don’t intersect

_sanitize_polygon

1

_sanitize_polygon(polygon: PackedVector2Array) -> PackedVector2Array

Flags: static, private

Remove duplicate consecutive points and collinear middle points from polygon

_compute_intersection

1
2
3
4
5
6
7
8
9

_compute_intersection(
    a: Vector2,
    b: Vector2,
    boundary: int,
    left: float,
    right: float,
    top: float,
    bottom: float
) -> Vector2

Flags: static, private

_lines_intersect

1
2
3
4
5
6

_lines_intersect(
    p1: Vector2,
    p2: Vector2,
    p3: Vector2,
    p4: Vector2
) -> bool

Flags: static, private

Pure function to check if two lines intersect

_polygons_intersect

1
2
3
4
5

_polygons_intersect(
    poly1: PackedVector2Array,
    poly2: PackedVector2Array,
    epsilon: float
) -> bool

Flags: static, private

Pure function to check if two polygons intersect