Smallest enclosing circle problem: Difference between revisions
Smallest enclosing circle problem (view source)
Revision as of 06:06, 16 December 2021
, 2 years ago→{{header|11l}}
Alextretyak (talk | contribs) (Added 11l) |
Alextretyak (talk | contribs) |
||
Line 37:
R ‘Center ’(.c)‘, Radius ’(.r)
F distSq(Point a, b)
R (a.x - b.x) ^ 2 + (a.y - b.y) ^ 2
F dist(Point a, b)
R sqrt(distSq(a, b))
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(Circle ci, Point p)
R distSq(ci.c, p) <= ci.r ^ 2
F encloses(Circle ci, [Point] ps)
L(p) ps
I !contains(ci, p)
Line 58:
R 1B
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(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([Point] rs)
I rs.empty
R Circle(Point(0, 0), 0)
Line 84:
R circleFrom3(rs[0], rs[1], rs[2])
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([Point] ps)
V pc = copy(ps)
random:shuffle(&pc)
| |||