Smallest enclosing circle problem: Difference between revisions
m
syntax highlighting fixup automation
m (→{{header|Phix}}: syntax coloured, made p2js compatible) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 16:
{{trans|Go}}
<
T Circle
Line 92:
L(test) Tests
print(welzl(test))</
{{out}}
Line 102:
=={{header|Go}}==
{{trans|Wren}}
<
import (
Line 230:
fmt.Println(welzl(test))
}
}</
{{out}}
Line 240:
=={{header|Julia}}==
N-dimensional solution using the Welzl algorithm. Derived from the BoundingSphere.jl module at https://github.com/JuliaFEM. See also Bernd Gärtner's paper at people.inf.ethz.ch/gaertner/subdir/texts/own_work/esa99_final.pdf.
<
using LinearAlgebra, Random
Line 411:
testwelzl()
</
<pre>
For points: [[0.0, 0.0], [0.0, 1.0], [1.0, 0.0]]
Line 431:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
f[{{0,0},{0,1},{1,0}}]
f[{{5,-2},{-3,-2},{-2,5},{1,6},{0,2}}]
f[{{2,4,-1},{1,5,-3},{8,-4,1},{3,9,-5}}]
f[{{-0.6400900432782123`,2.643703255134232`,0.4016122094706093`,1.8959601399652273`,-1.1624046608380516`},{0.5632393652621324`,-0.015981105190064373`,-2.193725940351997`,-0.9094586577358262`,0.7165036664470906`},{-1.7704367632976061`,0.2518283698686299`,-1.3810444289625348`,-0.597516704360172`,1.089645656962647`},{1.3448578652803103`,-0.18140877132223002`,-0.4288734015080915`,1.53271973321691`,0.41896461833399573`},{0.2132336397213029`,0.07659442168765788`,0.148636431531099`,2.3386893481333795`,-2.3000459709300927`},{0.6023153188617328`,0.3051735340025314`,1.0732600437151525`,1.1148388039984898`,0.047605838564167786`},{1.3655523661720959`,0.5461416420929995`,-0.09321951900362889`,-1.004771137760985`,1.6532914656050117`},{-0.14974382165751837`,-0.5375672589202939`,-0.15845596754003466`,-0.2750720340454088`,-0.441247015836271`}}]</
{{out}}
<pre>Ball[{0.5,0.5},0.707107]
Line 445:
{{trans|Go}}
{{trans|Wren}}
<
type
Line 546:
for test in Tests:
echo welzl(test)</
{{out}}
Line 554:
=={{header|Phix}}==
Based on the same code as Wren, and likewise limited to 2D circles - I believe (but cannot prove) the main barrier to coping with more than two dimensions lies wholly within the circle_from3() routine.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">type</span> <span style="color: #000000;">point</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">type</span>
Line 619:
<span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}}}</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #000000;">welzl</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 629:
{{trans|Python}}
Uses the last test from Julia, however, since that's given more accurately.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">inf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e300</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e300</span><span style="color: #0000FF;">,</span>
Line 784:
<span style="color: #0000FF;">{-</span><span style="color: #000000;">0.14974382165751837</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">0.5375672589202939</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">0.15845596754003466</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">0.2750720340454088</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">0.441247015836271</span><span style="color: #0000FF;">}}}</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #000000;">welzl</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 810:
=={{header|Python}}==
{{trans|Julia}}
<
class ProjectorStack:
Line 969:
print(" Center is at: ", nsphere.center)
print(" Radius is: ", np.sqrt(nsphere.sqradius), "\n")
</
<pre>
For points: [[0. 0.]
Line 1,006:
=={{header|Raku}}==
{{trans|Go}}
<syntaxhighlight lang="raku"
method gist { "({$.x~", "~$.y})" }
}
Line 1,072:
}
say "Solution for smallest circle enclosing {$_.gist} :\n", welzl $_ for @tests;</
{{out}}
<pre>Solution for smallest circle enclosing ((0, 0) (0, 1) (1, 0)) :
Line 1,084:
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].
<
var Rand = Random.new()
Line 1,200:
]
for (test in tests) System.print(Circle.welzl(test))</
{{out}}
| |||