Class CollisionGeometryCalculator

Namespace

GridPlacement.GDScript

Assembly

MoonBark.GridPlacement.GDScript.dll

Pure logic class for collision geometry calculations. Contains no state and can be easily tested in isolation.\n\nPOLYGON 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.\n\nAlgorithm 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\n\nWhy 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\n\nDefault 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)\n\nKey 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\n\nTesting: All clipping methods are public for comprehensive unit testing validation.

class CollisionGeometryCalculator extends RefCounted

CollisionGeometryCalculator

Fields

AREA_REL_EPS

const AREA_REL_EPS: float = 0.01

AREA_ABS_EPS

const AREA_ABS_EPS: float = 1.0

Properties

debug_polygon_overlap

static var debug_polygon_overlap: bool = false

overlapped_tiles

var overlapped_tiles: Array[Vector2i] = []

bounds

var bounds = _get_polygon_bounds(polygon)

start_tile

var start_tile: Vector2i = Vector2i()

end_tile

var end_tile = Vector2i(ceil((bounds.position.x + bounds.size.x) / tile_size.x), ceil((bounds.position.y + bounds.size.y) / tile_size.y))

tile_pos

var tile_pos = Vector2i(x, y)

tile_world_center

var tile_world_center = tile_map_layer.to_global(tile_map_layer.map_to_local(tile_pos))

tile_rect

var tile_rect = Rect2(tile_world_center - tile_size_vec * 0.5, tile_size_vec)

overlapped_tiles

var overlapped_tiles: Array[Vector2i] = []

bounds

var bounds = _get_polygon_bounds(polygon)

range

var range: Dictionary = CollisionGeometryUtils.compute_tile_iteration_range(bounds, tile_map_layer)

start_tile

var start_tile: Vector2i = Vector2i()

end_exclusive

var end_exclusive: Vector2i = Vector2i()

end_tile

var end_tile = Vector2i(ceil((bounds.position.x + bounds.size.x) / tile_size.x), ceil((bounds.position.y + bounds.size.y) / tile_size.y))

tile_pos

var tile_pos = Vector2i(x, y)

tile_world_center

var tile_world_center = tile_map_layer.to_global(tile_map_layer.map_to_local(tile_pos))

tile_size_vec

var tile_size_vec: Vector2 = Vector2(tile_map_layer.tile_set.tile_size) if tile_map_layer.tile_set else tile_size

tile_rect

var tile_rect = Rect2(tile_world_center - tile_size_vec * 0.5, tile_size_vec)

overlapped_tiles

var overlapped_tiles: Array[Vector2i] = []

bounds

var bounds = _get_polygon_bounds(polygon)

top_left_world

var top_left_world = bounds.position

bottom_right_world

var bottom_right_world = bounds.position + bounds.size

top_right_world

var top_right_world = Vector2(bottom_right_world.x, top_left_world.y)

bottom_left_world

var bottom_left_world = Vector2(top_left_world.x, bottom_right_world.y)

corners_tile

var corners_tile = [

min_tile_x

var min_tile_x = corners_tile[0].x

max_tile_x

var max_tile_x = corners_tile[0].x

min_tile_y

var min_tile_y = corners_tile[0].y

max_tile_y

var max_tile_y = corners_tile[0].y

tile_pos

var tile_pos = Vector2i(x, y)

tile_world_center

var tile_world_center = tile_map_layer.to_global(tile_map_layer.map_to_local(tile_pos))

tile_size

var tile_size = Vector2(tile_map_layer.tile_set.tile_size) if tile_map_layer.tile_set else Vector2(16, 16)

half_width

var half_width = tile_size.x * 0.5

half_height

var half_height = tile_size.y * 0.5

tile_diamond

var tile_diamond = PackedVector2Array([

bounds1

var bounds1 = _get_polygon_bounds(shape1)

bounds2

var bounds2 = _get_polygon_bounds(shape2)

min_x

var min_x = polygon[0].x

min_y

var min_y = polygon[0].y

max_x

var max_x = polygon[0].x

max_y

var max_y = polygon[0].y

output

var output = polygon

edge_vec

var edge_vec = edge_end - edge_start

edge_normal

var edge_normal = Vector2(-edge_vec.y, edge_vec.x).normalized()

prev

var prev: Vector2 = output[output.size()-1]

prev_inside

var prev_inside = point_inside_boundary(prev, boundary, left, right, top, bottom)

curr_inside

var curr_inside = point_inside_boundary(curr, boundary, left, right, top, bottom)

intersection

var intersection = p1 + ua * (p2 - p1)

intersection

var intersection = p1 + ua * (p2 - p1)

denominator

var denominator = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y)

ua

var ua = ((p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x)) / denominator

intersection

var intersection = p1 + ua * (p2 - p1)

clipped

var clipped = clip_polygon_to_rect(polygon, rect)

edge_start

var edge_start = poly2[i]

edge_end

var edge_end = poly2[(i + 1) % poly2.size()]

overlap_area

var overlap_area = polygon_area(clipped)

min_area

var min_area: float = rect_area * clamp(min_overlap_ratio, 0.0, 1.0)

area_eps

var area_eps: float = 0.0

adjusted_min_area

var adjusted_min_area: float = max(0.0, min_area - area_eps)

poly_bounds

var poly_bounds = _get_polygon_bounds(polygon)

clipped

var clipped = clip_polygon_to_rect(polygon, rect)

area

var area = polygon_area(clipped)

rect_area

var rect_area = rect.size.x * rect.size.y

min_area

var min_area: float = rect_area * clamp(min_overlap_ratio, 0.0, 1.0)

area_eps

var area_eps: float = 0.0

adjusted_min_area

var adjusted_min_area: float = max(0.0, min_area - area_eps)

debug_near_threshold

var debug_near_threshold = false

debug_condition

var debug_condition = debug_polygon_overlap and debug_near_threshold

result

var result: PackedVector2Array = PackedVector2Array()

out

var out: PackedVector2Array = PackedVector2Array()

n

var n = polygon.size()

eps

var eps = 0.0001

last

var last: Vector2 = polygon[0]

p

var p: Vector2 = polygon[i]

cleaned

var cleaned: PackedVector2Array = PackedVector2Array()

m

var m = out.size()

a

var a: Vector2 = polygon[i]

b

var b: Vector2 = polygon[(i + 1) % n]

c

var c = out[(i + 1) % m]

cross

var cross = (b - a).cross(c - b)

output

var output = polygon

left

var left = rect.position.x

right

var right = rect.position.x + rect.size.x

top

var top = rect.position.y

bottom

var bottom = rect.position.y + rect.size.y

result

var result: PackedVector2Array = PackedVector2Array()

prev

var prev: Vector2 = output[output.size()-1]

prev_inside

var prev_inside = point_inside_boundary(prev, boundary, left, right, top, bottom)

curr_inside

var curr_inside = point_inside_boundary(curr, boundary, left, right, top, bottom)

t

var t = 0.0

n

var n = polygon.size()

sum

var sum = 0.0

a

var a: Vector2 = polygon[i]

b

var b: Vector2 = polygon[(i + 1) % n]

inside

var inside = false

j

var j = polygon.size() - 1

denominator

var denominator = (p4.y - p3.y) * (p2.x - p1.x) - (p4.x - p3.x) * (p2.y - p1.y)

ua

var ua = ((p4.x - p3.x) * (p1.y - p3.y) - (p4.y - p3.y) * (p1.x - p3.x)) / denominator

ub

var ub = ((p2.x - p1.x) * (p1.y - p3.y) - (p2.y - p1.y) * (p1.x - p3.x)) / denominator

edge1_start

var edge1_start = poly1[i]

edge1_end

var edge1_end = poly1[(i + 1) % poly1.size()]

edge2_start

var edge2_start = poly2[j]

edge2_end

var edge2_end = poly2[(j + 1) % poly2.size()]

Methods

calculate_tile_overlap

static func calculate_tile_overlap( polygon: PackedVector2Array,

calculate_tile_overlap_numeric

static func calculate_tile_overlap_numeric( polygon: PackedVector2Array,

detect_collisions

static func detect_collisions( shape1: PackedVector2Array,

polygons_overlap

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

Parameters

poly1

poly2

min_overlap_ratio

reference_area

Returns

polygon_overlaps_rect

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

Parameters

polygon

rect

epsilon

min_overlap_ratio

Returns

clip_polygon_to_rect

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

Parameters

polygon

rect

Returns

point_inside_boundary

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

Parameters

p

boundary

left

right

top

bottom

Returns

polygon_area

static func polygon_area(polygon: PackedVector2Array) -> float:

Parameters

polygon

Returns

point_in_polygon

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

Parameters

point

polygon

Returns