Smallest enclosing circle problem: Difference between revisions

Line 37:

R ‘Center ’(.c)‘, Radius ’(.r)

F distSq(a, b)

F distSq(Point a, b)

R (a.x - b.x) ^ 2 + (a.y - b.y) ^ 2

F dist(a, b)

F dist(Point a, b)

R sqrt(distSq(a, b))

F getCircleCenter(bx, by, cx, cy)

F getCircleCenter(Float bx, by, cx, cy)

V b = bx * bx + by * by

V c = cx * cx + cy * cy

Line 49:

R Point((cy * b - by * c) / (2 * d), (bx * c - cx * b) / (2 * d))

F contains(ci, p)

F contains(Circle ci, Point p)

R distSq(ci.c, p) <= ci.r ^ 2

F encloses(ci, ps)

F encloses(Circle ci, [Point] ps)

L(p) ps

I !contains(ci, p)

Line 58:

R 1B

F circleFrom3(a, b, c)

F circleFrom3(Point a, b, c)

V i = getCircleCenter(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y)

i.x += a.x

Line 64:

R Circle(i, dist(i, a))

F circleFrom2(a, b)

F circleFrom2(Point a, b)

V c = Point((a.x + b.x) * 0.5, (a.y + b.y) * 0.5)

R Circle(c, dist(a, b) / 2)

F secTrivial(rs)

F secTrivial([Point] rs)

I rs.empty

R Circle(Point(0, 0), 0)

Line 84:

R circleFrom3(rs[0], rs[1], rs[2])

F welzlHelper(&ps, rs, n)

F welzlHelper([Point] &ps, [Point] rs, Int n)

V rc = copy(rs)

I n == 0 | rc.len == 3

Line 97:

R welzlHelper(&ps, rc, n - 1)

F welzl(ps)

F welzl([Point] ps)

V pc = copy(ps)

random:shuffle(&pc)