110 lines
3.3 KiB
Tcl
110 lines
3.3 KiB
Tcl
set circles {
|
|
1.6417233788 1.6121789534 0.0848270516
|
|
-1.4944608174 1.2077959613 1.1039549836
|
|
0.6110294452 -0.6907087527 0.9089162485
|
|
0.3844862411 0.2923344616 0.2375743054
|
|
-0.2495892950 -0.3832854473 1.0845181219
|
|
1.7813504266 1.6178237031 0.8162655711
|
|
-0.1985249206 -0.8343333301 0.0538864941
|
|
-1.7011985145 -0.1263820964 0.4776976918
|
|
-0.4319462812 1.4104420482 0.7886291537
|
|
0.2178372997 -0.9499557344 0.0357871187
|
|
-0.6294854565 -1.3078893852 0.7653357688
|
|
1.7952608455 0.6281269104 0.2727652452
|
|
1.4168575317 1.0683357171 1.1016025378
|
|
1.4637371396 0.9463877418 1.1846214562
|
|
-0.5263668798 1.7315156631 1.4428514068
|
|
-1.2197352481 0.9144146579 1.0727263474
|
|
-0.1389358881 0.1092805780 0.7350208828
|
|
1.5293954595 0.0030278255 1.2472867347
|
|
-0.5258728625 1.3782633069 1.3495508831
|
|
-0.1403562064 0.2437382535 1.3804956588
|
|
0.8055826339 -0.0482092025 0.3327165165
|
|
-0.6311979224 0.7184578971 0.2491045282
|
|
1.4685857879 -0.8347049536 1.3670667538
|
|
-0.6855727502 1.6465021616 1.0593087096
|
|
0.0152957411 0.0638919221 0.9771215985
|
|
}
|
|
|
|
proc init {} {
|
|
upvar 1 circles circles
|
|
set xMin [set yMin inf]
|
|
set xMax [set yMax -inf]
|
|
set i -1
|
|
foreach {xc yc rad} $circles {
|
|
set xMin [expr {min($xMin, $xc-$rad)}]
|
|
set xMax [expr {max($xMax, $xc+$rad)}]
|
|
set yMin [expr {min($yMin, $yc-$rad)}]
|
|
set yMax [expr {max($yMax, $yc+$rad)}]
|
|
lset circles [incr i 3] [expr {$rad**2}]
|
|
}
|
|
return [list $xMin $xMax $yMin $yMax]
|
|
}
|
|
|
|
proc sampleGrid {circles steps} {
|
|
lassign [init] xMin xMax yMin yMax
|
|
set dx [expr {($xMax-$xMin)/$steps}]
|
|
set dy [expr {($yMax-$yMin)/$steps}]
|
|
set n 0
|
|
for {set i 0} {$i < $steps} {incr i} {
|
|
set x [expr {$xMin + $i * $dx}]
|
|
for {set j 0} {$j < $steps} {incr j} {
|
|
set y [expr {$yMin + $j * $dy}]
|
|
foreach {xc yc rad2} $circles {
|
|
if {($x-$xc)**2 + ($y-$yc)**2 <= $rad2} {
|
|
incr n
|
|
break
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return [expr {$dx * $dy * $n}]
|
|
}
|
|
|
|
proc sampleMC {circles samples} {
|
|
lassign [init] xMin xMax yMin yMax
|
|
set n 0
|
|
for {set i 0} {$i < $samples} {incr i} {
|
|
set x [expr {$xMin+rand()*($xMax-$xMin)}]
|
|
set y [expr {$yMin+rand()*($yMax-$yMin)}]
|
|
foreach {xc yc rad2} $circles {
|
|
if {($x-$xc)**2 + ($y-$yc)**2 <= $rad2} {
|
|
incr n
|
|
break
|
|
}
|
|
}
|
|
}
|
|
return [expr {($xMax-$xMin) * ($yMax-$yMin) * $n / $samples}]
|
|
}
|
|
|
|
proc samplePerturb {circles steps votes} {
|
|
lassign [init] xMin xMax yMin yMax
|
|
set dx [expr {($xMax-$xMin)/$steps}]
|
|
set dy [expr {($yMax-$yMin)/$steps}]
|
|
set n 0
|
|
for {set i 0} {$i < $steps} {incr i} {
|
|
set x [expr {$xMin + $i * $dx}]
|
|
for {set j 0} {$j < $steps} {incr j} {
|
|
set y [expr {$yMin + $j * $dy}]
|
|
foreach {xc yc rad2} $circles {
|
|
set in 0
|
|
for {set v 0} {$v < $votes} {incr v} {
|
|
set xr [expr {$x + (rand()-0.5)*$dx}]
|
|
set yr [expr {$y + (rand()-0.5)*$dy}]
|
|
if {($xr-$xc)**2 + ($yr-$yc)**2 <= $rad2} {
|
|
incr in
|
|
}
|
|
}
|
|
if {$in*2 >= $votes} {
|
|
incr n
|
|
break
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return [expr {$dx * $dy * $n}]
|
|
}
|
|
|
|
puts [format "estimated area (grid): %.4f" [sampleGrid $circles 500]]
|
|
puts [format "estimated area (monte carlo): %.2f" [sampleMC $circles 1000000]]
|
|
puts [format "estimated area (perturbed sample): %.4f" [samplePerturb $circles 500 5]]
|