Smallest enclosing circle problem: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: syntax coloured, made p2js compatible) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 16: | Line 16: | ||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="11l">T Point = (Float, Float) |
||
T Circle |
T Circle |
||
Line 92: | Line 92: | ||
L(test) Tests |
L(test) Tests |
||
print(welzl(test))</ |
print(welzl(test))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 102: | Line 102: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 230: | Line 230: | ||
fmt.Println(welzl(test)) |
fmt.Println(welzl(test)) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 240: | Line 240: | ||
=={{header|Julia}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="julia">import Base.pop!, Base.push!, Base.length, Base.* |
||
using LinearAlgebra, Random |
using LinearAlgebra, Random |
||
Line 411: | Line 411: | ||
testwelzl() |
testwelzl() |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
For points: [[0.0, 0.0], [0.0, 1.0], [1.0, 0.0]] |
For points: [[0.0, 0.0], [0.0, 1.0], [1.0, 0.0]] |
||
Line 431: | Line 431: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">f=BoundingRegion[#,"MinBall"]&; |
||
f[{{0,0},{0,1},{1,0}}] |
f[{{0,0},{0,1},{1,0}}] |
||
f[{{5,-2},{-3,-2},{-2,5},{1,6},{0,2}}] |
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[{{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`}}]</ |
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`}}]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Ball[{0.5,0.5},0.707107] |
<pre>Ball[{0.5,0.5},0.707107] |
||
Line 445: | Line 445: | ||
{{trans|Go}} |
{{trans|Go}} |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="nim">import math, random, strutils |
||
type |
type |
||
Line 546: | Line 546: | ||
for test in Tests: |
for test in Tests: |
||
echo welzl(test)</ |
echo welzl(test)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 554: | Line 554: | ||
=={{header|Phix}}== |
=={{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. |
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. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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> |
<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: | 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: #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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 629: | Line 629: | ||
{{trans|Python}} |
{{trans|Python}} |
||
Uses the last test from Julia, however, since that's given more accurately. |
Uses the last test from Julia, however, since that's given more accurately. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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> |
<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: | 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: #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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 810: | Line 810: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{trans|Julia}} |
{{trans|Julia}} |
||
< |
<syntaxhighlight lang="python">import numpy as np |
||
class ProjectorStack: |
class ProjectorStack: |
||
Line 969: | Line 969: | ||
print(" Center is at: ", nsphere.center) |
print(" Center is at: ", nsphere.center) |
||
print(" Radius is: ", np.sqrt(nsphere.sqradius), "\n") |
print(" Radius is: ", np.sqrt(nsphere.sqradius), "\n") |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
For points: [[0. 0.] |
For points: [[0. 0.] |
||
Line 1,006: | Line 1,006: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<lang |
<syntaxhighlight lang="raku" line>class P { has ($.x, $.y) is rw; # Point |
||
method gist { "({$.x~", "~$.y})" } |
method gist { "({$.x~", "~$.y})" } |
||
} |
} |
||
Line 1,072: | Line 1,072: | ||
} |
} |
||
say "Solution for smallest circle enclosing {$_.gist} :\n", welzl $_ for @tests;</ |
say "Solution for smallest circle enclosing {$_.gist} :\n", welzl $_ for @tests;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Solution for smallest circle enclosing ((0, 0) (0, 1) (1, 0)) : |
<pre>Solution for smallest circle enclosing ((0, 0) (0, 1) (1, 0)) : |
||
Line 1,084: | 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]. |
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="ecmascript">import "random" for Random |
||
var Rand = Random.new() |
var Rand = Random.new() |
||
Line 1,200: | Line 1,200: | ||
] |
] |
||
for (test in tests) System.print(Circle.welzl(test))</ |
for (test in tests) System.print(Circle.welzl(test))</syntaxhighlight> |
||
{{out}} |
{{out}} |