Smallest enclosing circle problem: Difference between revisions
added Raku programming solution
(→{{header|Phix}}: added n-dimensional translation) |
(added Raku programming solution) |
||
Line 824:
Radius is: 2.076492284522762
</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}}==
| |||