Smallest enclosing circle problem: Difference between revisions
Smallest enclosing circle problem (view source)
Revision as of 05:59, 16 December 2021
, 2 years agoAdded 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 11:
* Circle (sphere) contains point when ''distance between point and circle center <= circle radius''.
=={{header|11l}}==
{{trans|Nim}}
{{trans|Go}}
<lang 11l>T Point
Float x, y
F (x, y)
.x = x
.y = y
F String()
R ‘(’(.x)‘, ’(.y)‘)’
T Circle
Point c
Float r
F (c, r)
.c = c
.r = r
F String()
R ‘Center ’(.c)‘, Radius ’(.r)
F distSq(a, b)
R (a.x - b.x) ^ 2 + (a.y - b.y) ^ 2
F dist(a, b)
R sqrt(distSq(a, b))
F getCircleCenter(bx, by, cx, cy)
V b = bx * bx + by * by
V c = cx * cx + cy * cy
V d = bx * cy - by * cx
R Point((cy * b - by * c) / (2 * d), (bx * c - cx * b) / (2 * d))
F contains(ci, p)
R distSq(ci.c, p) <= ci.r ^ 2
F encloses(ci, ps)
L(p) ps
I !contains(ci, p)
R 0B
R 1B
F circleFrom3(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
i.y += a.y
R Circle(i, dist(i, a))
F circleFrom2(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)
I rs.empty
R Circle(Point(0, 0), 0)
I rs.len == 1
R Circle(rs[0], 0)
I rs.len == 2
R circleFrom2(rs[0], rs[1])
assert(rs.len == 3, ‘There shouldn't be more than three points.’)
L(i) 2
L(j) i + 1 .< 3
V c = circleFrom2(rs[i], rs[j])
I encloses(c, rs)
R c
R circleFrom3(rs[0], rs[1], rs[2])
F welzlHelper(&ps, rs, n)
V rc = copy(rs)
I n == 0 | rc.len == 3
R secTrivial(rc)
V idx = random:(n)
V p = ps[idx]
swap(&ps[idx], &ps[n - 1])
V d = welzlHelper(&ps, rc, n - 1)
I contains(d, p)
R d
rc.append(p)
R welzlHelper(&ps, rc, n - 1)
F welzl(ps)
V pc = copy(ps)
random:shuffle(&pc)
R welzlHelper(&pc, [Point](), pc.len)
V Tests = [[Point(0.0, 0.0), Point(0.0, 1.0), Point(1.0, 0.0)],
[Point(5.0, -2.0), Point(-3.0, -2.0), Point(-2.0, 5.0), Point(1.0, 6.0), Point(0.0, 2.0)]]
L(test) Tests
print(welzl(test))</lang>
{{out}}
<pre>
Center (0.5, 0.5), Radius 0.707106781
Center (1, 1), Radius 5
</pre>
=={{header|Go}}==
| |||