Marching squares: Difference between revisions
m
→{{header|11l}}: X.throw
m (→{{header|Raku}}: insignificant changes) |
Alextretyak (talk | contribs) m (→{{header|11l}}: X.throw) |
||
| (7 intermediate revisions by 5 users not shown) | |||
Line 6:
See: [https://en.wikipedia.org/wiki/Marching_squares Marching squares]
=={{header|11l}}==
{{trans|Wren}}
<syntaxhighlight lang="11l">
-V
DIR_E = ( 1, 0)
DIR_NE = ( 1, 1)
DIR_N = ( 0, 1)
DIR_NW = (-1, 1)
DIR_W = (-1, 0)
DIR_SW = (-1, -1)
DIR_S = ( 0, -1)
DIR_SE = ( 1, -1)
F path_str(origin_x, origin_y, directions)
-V :dirn = [:DIR_E = ‘E’,
:DIR_NE = ‘NE’,
:DIR_N = ‘N’,
:DIR_NW = ‘NW’,
:DIR_W = ‘W’,
:DIR_SW = ‘SW’,
:DIR_S = ‘S’,
:DIR_SE = ‘SE’]
R ‘X: ’origin_x‘, Y: ’origin_y‘, Path: ’directions.map(d -> @:dirn[d])
T MarchingSquares
. Int width, height
. [Int] data
F (width, height, data)
.width = width
.height = height
.data = copy(data)
. F is_set(x, y)
I x <= 0 | x > .width | y <= 0 | y > .height
R 0B
R .data[(y - 1) * .width + (x - 1)] != 0
. F value(x, y)
V sum = 0
I .is_set(x, y) {sum [|]= 1}
I .is_set(x + 1, y) {sum [|]= 2}
I .is_set(x, y + 1) {sum [|]= 4}
I .is_set(x + 1, y + 1) {sum [|]= 8}
R sum
. F identify_perimeter_(=initial_x, =initial_y)
I initial_x < 0 {initial_x = 0}
I initial_x > .width {initial_x = .width}
I initial_y < 0 {initial_y = 0}
I initial_y > .height {initial_y = .height}
V initial_value = .value(initial_x, initial_y)
I initial_value C (0, 15)
X.throw RuntimeError(‘Supplied initial coordinates (#., #.) do not lie on a perimeter.’.format(initial_x, initial_y))
[IVec2] directions
V x = initial_x
V y = initial_y
V previous = (0, 0)
L
IVec2 direction
S .value(x, y)
1, 5, 13
direction = :DIR_N
2, 3, 7
direction = :DIR_E
4, 12, 14
direction = :DIR_W
8, 10, 11
direction = :DIR_S
6
direction = I previous == :DIR_N {:DIR_W} E :DIR_E
9
direction = I previous == :DIR_E {:DIR_N} E :DIR_S
E
X.throw RuntimeError(‘Illegal state.’)
directions.append(direction)
x += direction.x
y -= direction.y
previous = direction
I x == initial_x & y == initial_y
L.break
R path_str(initial_x, -initial_y, directions)
F identify_perimeter()
V size = .width * .height
L(i) 0 .< size
I .data[i] != 0
R .identify_perimeter_(i % .width, i I/ .width)
V example = [
0, 0, 0, 0, 0,
0, 0, 0, 0, 0,
0, 0, 1, 1, 0,
0, 0, 1, 1, 0,
0, 0, 0, 1, 0,
0, 0, 0, 0, 0
]
V ms = MarchingSquares(5, 6, example)
print(ms.identify_perimeter())
</syntaxhighlight>
{{out}}
<pre>
X: 2, Y: -2, Path: [S, S, E, S, E, N, N, N, W, W]
</pre>
=={{header|J}}==
Line 11 ⟶ 123:
This is a partial implementation, see the talk page for some discussion of the untouched issues.
<
step2=: {{(($y)#:i.$y) {{<x step2a y{::LUT}}"1 0 y}}
step2a=: {{ if. #y do. x+"1 y else. y end. }}
Line 49 ⟶ 161:
end.
r,<~.c
}}</
Task example:
<
img
1 1
Line 69 ⟶ 181:
│2 4│
│1 3│
└───┘</
Here, <code>img</code> is a bitmap. We pad the bitmap by surrounding it with zeros during processing. The box at the end contains a contour corresponding to the bitmap. Here, the first column represents row number (row 0 at the top) and the second column represents column number (column 0 at the left). Each contour represents a closed loop (so the final coordinate pair would connect with the first coordinate pair).
Line 75 ⟶ 187:
While the above implementation is incomplete, it seems to adequately handle an oval of cassini with focal points at X=1, -1 and Y=0:
<
X=: |:Y=:201#"0]0.02*i:100
Z0=: (*:(*:X)+(*:Y)) + (_2*(*:a)*X -&*: Y) + *:a
Z=: (Z0>:0.8)*Z0<:1.2
C=: unwind step2 step1 Z</
Here, Z is a bitmap, and C is a list of three contours (one with 336 distinct coordinate pairs, and two with 134 distinct coordinate pairs) which surround that bitmap. These can be inspected (after <code>require'viewmat'</code>) with <code>viewmat Z</code> and <code>viewmat 1 (<"1;C)} 200 200$0</code>, and look plausible.
Line 88 ⟶ 200:
Uses the marching squares algorithm: see github.com/JuliaGeometry/Contour.jl/blob/master/src/Contour.jl
See the discussion page for the Oval of Cassini example
<
import GLMakie as GM # GLMakie also defines Contour so import, not using
Line 124 ⟶ 236:
GM.lines!(ovalxs3, ovalys3, color = :lightgreen, linewidth = 4)
GM.display(oplot)
</
<pre>
points = [(3, 4), (4, 3), (4, 2), (4, 1), (3, 0), (2, 1), (2, 1), (1, 2), (1, 3), (2, 4), (3, 4)]
Line 131 ⟶ 243:
=={{header|Lua}}==
Based on the Phix and Wren solutions.
<
local Directions = { -- clockwise from North
N = {x= 0, y=-1},
Line 227 ⟶ 339:
msMain (1, example)
</
<pre>
root: x=1 y=2
Line 234 ⟶ 346:
positions: {1,2, 2,2, 2,3, 3,3, 4,3, 4,4, 5,4, 5,3, 6,3, 6,2, 7,2, 7,3, 6,3, 6,4, 6,5, 6,6, 7,6, 7,7, 6,7, 6,6, 5,6, 4,6, 4,5, 3,5, 3,6, 2,6, 2,7, 1,7, 1,6, 2,6, 2,5, 2,4, 2,3, 1,3, }
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use v5.36;
no warnings 'experimental::for_list';
use List::Util 'any';
use enum <E N W S>;
sub X ($a,$b) { my @c; for my $aa (0..$a) { for my $bb (0..$b) { push @c, $aa, $bb } } @c }
sub identify_perimeter(@data) {
for my ($x,$y) (X $#{$data[0]}, $#data) {
next unless $data[$y][$x] and $data[$y][$x] != 0;
my ($path,$cx,$cy,$d,$p) = ('', $x, $y);
do {
my $mask;
for my($dx,$dy,$b) (0,0,1, 1,0,2, 0,1,4, 1,1,8) {
my ($mx, $my) = ($cx+$dx, $cy+$dy);
$mask += $b if $mx>1 and $my>1 and $data[$my-1][$mx-1] != 0
}
$d = N if any { $mask == $_ } (1, 5,13);
$d = E if any { $mask == $_ } (2, 3, 7);
$d = W if any { $mask == $_ } (4,12,14);
$d = S if any { $mask == $_ } (8,10,11);
$d = $p == N ? W : E if $mask == 6;
$d = $p == E ? N : S if $mask == 9;
$path .= $p = (<E N W S>)[$d];
$cx += (1, 0,-1,0)[$d];
$cy += (0,-1, 0,1)[$d];
} until $cx == $x and $cy == $y;
return $x, -$y, $path
}
exit 'That did not work out...';
}
my @M = ([0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0]);
printf "X: %d, Y: %d, Path: %s\n", identify_perimeter(@M);</syntaxhighlight>
{{out}}
<pre>X: 2, Y: -2, Path: SSESENNNWW</pre>
=={{header|Phix}}==
Based on the same code as the Wren example.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">E</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">W</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">S</span>
Line 291 ⟶ 450:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"X: %d, Y: %d, Path: %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">identifyPerimeter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">example</span><span style="color: #0000FF;">))</span>
<!--</
{{out}}
<pre>
Line 298 ⟶ 457:
=={{header|Python}}==
<
from skimage import measure
Line 313 ⟶ 472:
contours = round(measure.find_contours(example, 0.1))[0]
print('[', ', '.join([str((p[1], 5 - p[0])) for p in contours]), ']')
</
<pre>
[ (3.0, 0.0), (2.0, 1.0), (2.0, 1.0), (1.0, 2.0), (1.0, 3.0), (2.0, 4.0), (3.0, 4.0), (4.0, 3.0), (4.0, 2.0), (4.0, 1.0), (3.0, 0.0) ]
Line 320 ⟶ 479:
=={{header|Raku}}==
{{trans|Phix}}
<syntaxhighlight lang="raku"
enum <E N W S>;
Line 338 ⟶ 497:
for ^width X ^height -> (\x,\y) {
my ($cx,$cy,$directions,$previous) = x, y;
repeat {
my $mask
for (0,0,1),(1,0,2),(0,1,4),(1,1,8) -> (\dx,\dy,\b) {
my ($mx,$my) = $cx+dx,$cy+dy;
$mask += b if
}
given do given $mask {
Line 355 ⟶ 514:
} {
$directions ~= $previous = $_ ;
($cx,$cy) <<+=<<
}
} until $cx==x and $cy==y ;
Line 362 ⟶ 521:
}
return -1, -1, "Not found!"
}</
Output is the same as the Phix entry.
Line 368 ⟶ 527:
{{libheader|Wren-seq}}
This is a translation of the [http://www.tomgibara.com/computer-vision/marching-squares public domain Java code], written by Tom Gibara, which is linked to from the Wikipedia article. It also uses his example to test the code.
<
/* A direction in the plane. */
Line 585 ⟶ 744:
var ms = MarchingSquares.new(5, 6, example)
var path = ms.identifyPerimeter()
System.print(path)</
{{out}}
| |||