117 lines
3.0 KiB
GDScript
117 lines
3.0 KiB
GDScript
extends Object
|
|
|
|
const Set = preload("res://Set.gd")
|
|
|
|
var position: Vector2
|
|
var radius: float
|
|
|
|
func _init(p_position: Vector2 = Vector2(), p_radius: float = 0.0):
|
|
position = p_position
|
|
radius = p_radius
|
|
|
|
func contains_point(p: Vector2):
|
|
return position.distance_squared_to(p) <= radius * radius + 0.1
|
|
|
|
func contains_all_points(ps: Array):
|
|
for p in ps:
|
|
if !contains_point(p):
|
|
return false
|
|
return true
|
|
|
|
func circumscribe_two_points(a: Vector2, b: Vector2):
|
|
position = a.linear_interpolate(b, 0.5)
|
|
radius = a.distance_to(b) / 2.0
|
|
|
|
func circumscribe_three_points(a: Vector2, b: Vector2, c: Vector2):
|
|
var bary_mat := [b - a, c - a]
|
|
var det = bary_mat[0].x * bary_mat[1].y - bary_mat[1].x * bary_mat[0].y
|
|
var area = 0.5 * det
|
|
|
|
if area < 0.001:
|
|
position = a
|
|
radius = 0.0
|
|
return
|
|
|
|
position = Vector2(
|
|
a.x + 1.0 / (4.0 * area) * (bary_mat[1].y * a.distance_squared_to(b) - bary_mat[0].y * a.distance_squared_to(c)),
|
|
a.y + 1.0 / (4.0 * area) * (bary_mat[0].x * a.distance_squared_to(c) - bary_mat[1].x * a.distance_squared_to(b))
|
|
)
|
|
radius = position.distance_to(a)
|
|
|
|
func circumscribe(points: Array):
|
|
var n = len(points)
|
|
assert(n > 1)
|
|
|
|
position = Vector2(0, 0)
|
|
radius = INF
|
|
|
|
if n == 2:
|
|
circumscribe_two_points(points[0], points[1])
|
|
return
|
|
elif n == 3:
|
|
circumscribe_three_points(points[0], points[1], points[2])
|
|
return
|
|
|
|
# Check every two points
|
|
for i in range(n):
|
|
for j in range(n):
|
|
if i == j: continue
|
|
var c = get_script().new()
|
|
c.circumscribe_two_points(points[i], points[j])
|
|
if c.radius < radius and c.contains_all_points(points):
|
|
position = c.position
|
|
radius = c.radius
|
|
|
|
# Check every three points
|
|
for i in range(n):
|
|
for j in range(n):
|
|
for k in range(n):
|
|
if i == j or j == k or i == k: continue
|
|
var c = get_script().new()
|
|
c.circumscribe_three_points(points[i], points[j], points[k])
|
|
if c.radius < radius and c.contains_all_points(points):
|
|
position = c.position
|
|
radius = c.radius
|
|
|
|
func circumscribe2_internal(input: Set, support: Set):
|
|
var c = get_script().new()
|
|
if !input.empty():
|
|
var input_prime: Set = input.duplicate()
|
|
var p: Vector2 = input_prime.pop_random() # remove P from Input
|
|
|
|
c.circumscribe2_internal(input_prime, support);
|
|
if c.contains_point(p):
|
|
return c
|
|
else:
|
|
var support_prime = support.duplicate()
|
|
support_prime.add(p)
|
|
|
|
c.circumscribe2_internal(input_prime, support_prime)
|
|
return c
|
|
else:
|
|
var support_values = support.values()
|
|
if len(support_values) == 2:
|
|
c.circumscribe_two_points(support_values[0], support_values[1])
|
|
elif len(support_values) == 3:
|
|
c.circumscribe_three_points(support_values[0], support_values[1], support_values[2])
|
|
return c
|
|
|
|
func circumscribe2(points: Array):
|
|
var n = len(points)
|
|
assert(n > 1)
|
|
|
|
if n == 2:
|
|
circumscribe_two_points(points[0], points[1])
|
|
return
|
|
elif n == 3:
|
|
circumscribe_three_points(points[0], points[1], points[2])
|
|
return
|
|
|
|
var points_set = Set.new()
|
|
points_set.add_all(points)
|
|
var c = circumscribe2_internal(points_set, Set.new())
|
|
position = c.position
|
|
radius = c.radius
|
|
|
|
|