Smallest enclosing circle problem: Difference between revisions
Content added Content deleted
(→{{header|Phix}}: added n-dimensional translation) |
(added Raku programming solution) |
||
Line 824: | Line 824: | ||
Radius is: 2.076492284522762 |
Radius is: 2.076492284522762 |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
{{trans|Go}} |
|||
<lang perl6># 20201208 Raku programming solution |
|||
class P { has ($.x, $.y) is rw; # Point |
|||
method gist { "({$.x~", "~$.y})" } |
|||
} |
|||
class C { has (P $.c, Numeric $.r); # Circle |
|||
method gist { "Center = " ~$.c.gist ~ " and Radius = $.r\n" } |
|||
# returns whether a circle contains the point 'p' |
|||
method contains(P \p --> Bool) { return distSq($.c, p) ≤ $.r² } |
|||
method encloses(@ps --> Bool) { |
|||
@ps.map: { return False unless $.contains($_) } |
|||
return True |
|||
} # returns whether a circle contains a slice of point |
|||
} |
|||
# returns the square of the distance between two points |
|||
sub distSq (P \a, P \b) { return (a.x - b.x)² + (a.y - b.y)² } |
|||
sub getCenter (\bx, \by, \cx, \cy --> P) { |
|||
my (\b,\c,\d) = bx²+by² , cx²+cy², bx*cy - by*cx; |
|||
P.new: x => (cy*b - by*c) / (2 * d), y => (bx*c - cx*b) / (2 * d) |
|||
} # returns the center of a circle defined by 3 points |
|||
sub circleFrom3 (P \a, P \b, P \c --> C) { |
|||
my \k = $ = getCenter(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y); |
|||
k.x += a.x; |
|||
k.y += a.y; |
|||
return C.new: c => k, r => distSq(k, a).sqrt |
|||
} # returns a unique circle that intersects 3 points |
|||
sub circleFrom2 (P \a, P \b --> C ) { |
|||
my \center = P.new: x => ((a.x + b.x) / 2), y => ((a.y + b.y) / 2) ; |
|||
return C.new: c => center, r => (distSq(a, b).sqrt / 2) |
|||
} # returns smallest circle that intersects 2 points |
|||
sub secTrivial( @rs --> C ) { |
|||
given +@rs { |
|||
when * > 3 { die "There shouldn't be more than 3 points." } |
|||
when * == 0 { return C.new: c => (P.new: x => 0, y => 0) , r => 0 } |
|||
when * == 1 { return C.new: c => @rs[0], r => 0 } |
|||
when * == 2 { return circleFrom2 @rs[0], @rs[1] } |
|||
} |
|||
for 0, 1 X 1, 2 -> ( \i, \j ) { |
|||
given circleFrom2(@rs[i], @rs[j]) { return $_ if .encloses(@rs) } |
|||
} |
|||
return circleFrom3 @rs[0], @rs[1], @rs[2] |
|||
} # returns smallest enclosing circle for n ≤ 3 |
|||
sub welzlHelper( @ps is copy, @rs is copy , \n --> C ) { |
|||
return secTrivial(@rs) if ( n == 0 || +@rs == 3 ); |
|||
my \p = @ps.shift; |
|||
given welzlHelper(@ps, @rs, n-1) { return $_ if .contains(p) } |
|||
return welzlHelper(@ps, @rs.append(p), n-1) |
|||
} # helper function for Welzl method |
|||
# applies the Welzl algorithm to find the SEC |
|||
sub welzl(@ps --> C) { return welzlHelper(@ps.pick(*), [], +@ps) } |
|||
my @tests = ( |
|||
[ (0,0), (0,1), (1,0) ], |
|||
[ (5,-2), (-3,-2), (-2,5), (1,6), (0,2) ] |
|||
).map: { |
|||
@_.map: { P.new: x => $_[0], y => $_[1] } |
|||
} |
|||
say "Solution for smallest circle enclosing {$_.gist} :\n", welzl $_ for @tests;</lang> |
|||
{{out}} |
|||
<pre>Solution for smallest circle enclosing ((0, 0) (0, 1) (1, 0)) : |
|||
Center = (0.5, 0.5) and Radius = 0.7071067811865476 |
|||
Solution for smallest circle enclosing ((5, -2) (-3, -2) (-2, 5) (1, 6) (0, 2)) : |
|||
Center = (1, 1) and Radius = 5</pre> |
|||
=={{header|Wren}}== |
=={{header|Wren}}== |