CollisionGeometryCalculator
Summary
Section titled “Summary”Pure logic class for collision geometry calculations. Contains no state and can be easily tested in isolation.
POLYGON CLIPPING ALGORITHM - SUTHERLAND-HODGMAN =============================================== This class implements the Sutherland-Hodgman polygon clipping algorithm for determining polygon-rectangle overlap areas. The algorithm is correct for both convex and concave polygons.
Algorithm Overview: 1. The polygon is clipped against each of the 4 rectangle boundaries (left, right, top, bottom) 2. Each clipping operation produces a new polygon that is guaranteed to be inside that boundary 3. The final clipped polygon represents the intersection area between the original polygon and rectangle 4. The area of this clipped polygon determines if the overlap meets the minimum threshold
Why Sutherland-Hodgman is Correct: - Works for both convex and concave polygons (unlike some simpler algorithms) - Produces a valid polygon as output (no self-intersections or invalid geometry) - Handles edge cases like polygons completely inside/outside the rectangle - Deterministic and numerically stable with proper epsilon handling
Default Overlap Thresholds: - Edge epsilon: 0.01 (1% tolerance for numerical precision) - Minimum overlap ratio: 0.05 (5% of tile area required for detection) - Polygons with < 5% tile overlap are considered non-overlapping (prevents spurious micro-overlaps)
Key Methods: - clip_polygon_to_rect(): Implements the core Sutherland-Hodgman algorithm - polygon_overlaps_rect(): Uses clipping to determine if overlap meets threshold - polygon_area(): Calculates area using shoelace formula for overlap measurement
Testing: All clipping methods are public for comprehensive unit testing validation.
Methods
Section titled “Methods”static func _get_polygon_bounds( polygon: PackedVector2Array ) -> Rect2Pure function to get polygon bounds
static func _clip_polygon_to_edge( polygon: PackedVector2Array, edge_start: Vector2, edge_end: Vector2 ) -> PackedVector2ArrayPure 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
static func _line_intersection( p1: Vector2, p2: Vector2, p3: Vector2, p4: Vector2 ) -> Vector2Calculate intersection point of two line segments Returns Vector2.INF if lines don’t intersect
static func polygons_overlap( poly1: PackedVector2Array, poly2: PackedVector2Array, min_overlap_ratio: float, reference_area: float ) -> boolCheck if two arbitrary polygons overlap with a minimum overlap ratio Uses Sutherland-Hodgman clipping to compute precise overlap area
static func polygon_overlaps_rect( polygon: PackedVector2Array, rect: Rect2, epsilon: float, min_overlap_ratio: float ) -> boolThis 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.
static func _sanitize_polygon( polygon: PackedVector2Array ) -> PackedVector2ArrayRemove duplicate consecutive points and collinear middle points from polygon
static func clip_polygon_to_rect( polygon: PackedVector2Array, rect: Rect2 ) -> PackedVector2ArrayClips 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.
static func point_inside_boundary( p: Vector2, boundary: int, left: float, right: float, top: float, bottom: float ) -> boolChecks 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.
static func _compute_intersection( a: Vector2, b: Vector2, boundary: int, left: float, right: float, top: float, bottom: float ) -> Vector2static func polygon_area( polygon: PackedVector2Array ) -> floatComputes 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.
static func point_in_polygon( point: Vector2, polygon: PackedVector2Array ) -> boolPure 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
static func _lines_intersect( p1: Vector2, p2: Vector2, p3: Vector2, p4: Vector2 ) -> boolPure function to check if two lines intersect
static func _polygons_intersect( poly1: PackedVector2Array, poly2: PackedVector2Array, epsilon: float ) -> boolPure function to check if two polygons intersect
Source
Section titled “Source”addons/grid_building/placement/manager/components/collision_geometry_calculator.gd
This API reference is automatically generated from the plugin source code. For implementation examples and usage guides, see the guides section.