Rosetta Code

Smallest enclosing circle problem: Difference between revisions

Page Discussion

Smallest enclosing circle problem (view source)

Revision as of 17:02, 22 February 2024

4,566 bytes added ,  2 months ago
Realize in F#
m (syntax highlighting fixup automation)
(Realize in F#)
 
(2 intermediate revisions by 2 users not shown)
Line 100:
</pre>
 
=={{header|F_Sharp|F#}}==
This task uses [https://rosettacode.org/wiki/Centre_and_radius_of_a_circle_passing_through_3_points_in_a_plane#F# Centre and radius of a circle passing through 3 points in a plane (F#)]
<syntaxhighlight lang="fsharp">
// Smallest enclosing circle problem. Nigel Galloway: February 22nd., 2024
let mcc points=
let fN g=points|>List.map(fun n->(n,d g n))|>List.maxBy snd
let P1,P2=Seq.allPairs points points|>Seq.maxBy(fun(n,g)->d n g)
let c1,r1=let ((nx,ny) as n),((gx,gy) as g)=P1,P2 in (((nx+gx)/2.0,(ny+gy)/2.0),(d n g)/2.0)
match fN c1 with (_,d) when d=r1->(c1,r1)
|(P3,_)->let c2,r2=circ P1 P2 P3
match fN c2 with (_,d) when d=r2->(c2,r2)
|(P4,_)->[circ P1 P3 P4;circ P2 P3 P4]|>List.minBy snd
 
let testMCC n=let centre,radius=mcc n in printfn "Minimum Covering Circle is centred at %A with a radius of %f" centre radius
testMCC [(0.0, 0.0);(0.0, 1.0);(1.0, 0.0)]
testMCC [(5.0, -2.0);(-3.0, -2.0);(-2.0, 5.0);(1.0, 6.0);(0.0, 2.0)]
testMCC [(15.85,6.05);(29.82,22.11);(4.84,20.32);(25.47,29.46);(33.65,17.31);(7.30,10.43);(28.15,6.67);(20.85,11.47);(22.83,2.07);(26.28,23.15);(14.39,30.24);(30.24,25.23)]
testMCC [(15.85,6.05);(29.82,22.11);(4.84,20.32);(25.47,29.46);(33.65,17.31);(7.30,10.43);(28.15,6.67);(20.85,11.47);(22.83,2.08);(26.28,23.15);(14.39,30.24);(30.24,25.23)]
</syntaxhighlight>
{{out}}
<pre>
Minimum Covering Circle is centred at (0.5, 0.5) with a radius of 0.707107
Minimum Covering Circle is centred at (1.0, 1.0) with a radius of 5.000000
Minimum Covering Circle is centred at (18.97851566, 16.2654108) with a radius of 14.708624
Minimum Covering Circle is centred at (18.97952365, 16.27401209) with a radius of 14.707010
</pre>
=={{header|Go}}==
{{trans|Wren}}
Line 236 ⟶ 262:
{(0.500000, 0.500000), 0.707107}
{(1.000000, 1.000000), 5.000000}
</pre>
 
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
 
'''Adapted from [[#Wren|Wren]]'''
 
In the following, a Point (x,y) is represented by a JSON array [x,y],
and a Circle by a JSON object of the form {center, radius}.
<syntaxhighlight lang="jq">
# Vector sum of the input array of Points
def sum: transpose | map(add);
 
# The square of the distance between two points
def distSq:
def sq: . * .;
. as [$a, $b]
| (($a[0] - $b[0]) | sq) +(($a[1] - $b[1]) | sq) ;
 
# The distance between two points
def distance:
distSq | sqrt;
 
# Does the input Circle contain the point $p?
def contains($p):
([.center, $p] | distSq) <= .radius * .radius;
 
# Does the input Circle contain the given array of points?
def encloses($ps):
. as $c
| all($ps[]; . as $p | $c | contains($p));
 
# The center of a circle defined by 3 points
def getCircleCenter(bx; by; cx; cy):
(bx*bx + by*by) as $b
| (cx*cx + cy*cy) as $c
| (bx*cy - by*cx) as $d
| [(cy*$b - by*$c) / (2 * $d), (bx*$c - cx*$b) / (2 * $d)];
 
# The (smallest) circle that intersects 1, 2 or 3 distinct points
def Circle:
if length == 1 then {center: .[0], radius: 0}
elif length == 2
then {center: (sum | map(./2)),
radius: (distance/2) }
 
elif length == 3
then . as [$a, $b, $c]
| ([getCircleCenter($b[0] - $a[0];
$b[1] - $a[1];
$c[0] - $a[0];
$c[1] - $a[1]), $a] | sum) as $i
| {center: $i, radius: ([$i, $a]|distance)}
else "Circle/0 expects an input array of from 1 to 3 Points" | error
end;
# The smallest enclosing circle for n <= 3
def secTrivial:
. as $rs
| length as $length
| if $length > 3 then "Internal error: secTrivial given more than 3 points." | error
elif $length == 0 then [[0, 0]] | Circle
elif $length <= 2 then Circle
else first(
range(0; 2) as $i
| range($i+1; 3) as $j
| ([$rs[$i], $rs[$j]] | Circle)
| select(encloses($rs)) )
// Circle
end;
 
# Use the Welzl algorithm to find the SEC of the incoming array of points
def welzl:
# Helper function:
# $rs is an array of points on the boundary;
# $n keeps track of how many points remain:
def welzl_($rs; $n):
if $n == 0 or ($rs|length) == 3
then $rs | secTrivial
else 0 as $idx # or Rand($n)
| .[$idx] as $p
| .[$idx] = .[$n-1]
| .[$n-1] = $p
| welzl_($rs; $n-1) as $d
| if ($d | contains($p)) then $d
else welzl_($rs + [$p]; $n-1)
end
end ;
welzl_([]; length);
 
def tests:
[ [0, 0], [0, 1], [1, 0] ],
[ [5, -2], [-3, -2], [-2, 5], [1, 6], [0, 2] ]
;
 
tests
| welzl
| "Circle(\(.center), \(.radius))"
</syntaxhighlight>
{{output}}
<pre>
Circle([0.5,0.5], 0.7071067811865476)
Circle([1,1], 5)
</pre>
 
Line 1,084 ⟶ 1,215:
 
It is based on Welzl's algorithm and follows closely the C++ code [https://www.geeksforgeeks.org/minimum-enclosing-circle-set-2-welzls-algorithm/?ref=rp here].
<syntaxhighlight lang="ecmascriptwren">import "random" for Random
 
var Rand = Random.new()
Nigel Galloway
2,171

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328399...354337"