Marching squares: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (Added Perl) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 11: | Line 11: | ||
This is a partial implementation, see the talk page for some discussion of the untouched issues. |
This is a partial implementation, see the talk page for some discussion of the untouched issues. |
||
< |
<syntaxhighlight lang="j">step1=: {{2 2 #.@(0 1 3 2&{)@,;._3 ,&0^:2@|:@|.^:4 y}} |
||
step2=: {{(($y)#:i.$y) {{<x step2a y{::LUT}}"1 0 y}} |
step2=: {{(($y)#:i.$y) {{<x step2a y{::LUT}}"1 0 y}} |
||
step2a=: {{ if. #y do. x+"1 y else. y end. }} |
step2a=: {{ if. #y do. x+"1 y else. y end. }} |
||
Line 49: | Line 49: | ||
end. |
end. |
||
r,<~.c |
r,<~.c |
||
}}</ |
}}</syntaxhighlight> |
||
Task example: |
Task example: |
||
< |
<syntaxhighlight lang="j"> img=: 4~:i.3 2 |
||
img |
img |
||
1 1 |
1 1 |
||
Line 69: | Line 69: | ||
│2 4│ |
│2 4│ |
||
│1 3│ |
│1 3│ |
||
└───┘</ |
└───┘</syntaxhighlight> |
||
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). |
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: | Line 75: | ||
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: |
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: |
||
< |
<syntaxhighlight lang="j">a=: 1 |
||
X=: |:Y=:201#"0]0.02*i:100 |
X=: |:Y=:201#"0]0.02*i:100 |
||
Z0=: (*:(*:X)+(*:Y)) + (_2*(*:a)*X -&*: Y) + *:a |
Z0=: (*:(*:X)+(*:Y)) + (_2*(*:a)*X -&*: Y) + *:a |
||
Z=: (Z0>:0.8)*Z0<:1.2 |
Z=: (Z0>:0.8)*Z0<:1.2 |
||
C=: unwind step2 step1 Z</ |
C=: unwind step2 step1 Z</syntaxhighlight> |
||
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. |
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: | Line 88: | ||
Uses the marching squares algorithm: see github.com/JuliaGeometry/Contour.jl/blob/master/src/Contour.jl |
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 |
See the discussion page for the Oval of Cassini example |
||
< |
<syntaxhighlight lang="ruby">using Contour |
||
import GLMakie as GM # GLMakie also defines Contour so import, not using |
import GLMakie as GM # GLMakie also defines Contour so import, not using |
||
Line 124: | Line 124: | ||
GM.lines!(ovalxs3, ovalys3, color = :lightgreen, linewidth = 4) |
GM.lines!(ovalxs3, ovalys3, color = :lightgreen, linewidth = 4) |
||
GM.display(oplot) |
GM.display(oplot) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
points = [(3, 4), (4, 3), (4, 2), (4, 1), (3, 0), (2, 1), (2, 1), (1, 2), (1, 3), (2, 4), (3, 4)] |
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: | Line 131: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Based on the Phix and Wren solutions. |
Based on the Phix and Wren solutions. |
||
< |
<syntaxhighlight lang="lua">-- positive directions: right, down, clockwise |
||
local Directions = { -- clockwise from North |
local Directions = { -- clockwise from North |
||
N = {x= 0, y=-1}, |
N = {x= 0, y=-1}, |
||
Line 227: | Line 227: | ||
msMain (1, example) |
msMain (1, example) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
root: x=1 y=2 |
root: x=1 y=2 |
||
Line 237: | Line 237: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">use v5.36; |
||
no warnings 'experimental::for_list'; |
no warnings 'experimental::for_list'; |
||
use List::Util 'any'; |
use List::Util 'any'; |
||
Line 278: | Line 278: | ||
[0, 0, 0, 0, 0]); |
[0, 0, 0, 0, 0]); |
||
printf "X: %d, Y: %d, Path: %s\n", identify_perimeter(@M);</ |
printf "X: %d, Y: %d, Path: %s\n", identify_perimeter(@M);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>X: 2, Y: -2, Path: SSESENNNWW</pre> |
<pre>X: 2, Y: -2, Path: SSESENNNWW</pre> |
||
Line 284: | Line 284: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Based on the same code as the Wren example. |
Based on the same code as the Wren example. |
||
<!--< |
<!--<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;">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> |
<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 338: | Line 338: | ||
<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> |
<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 345: | Line 345: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from numpy import array, round |
||
from skimage import measure |
from skimage import measure |
||
Line 360: | Line 360: | ||
contours = round(measure.find_contours(example, 0.1))[0] |
contours = round(measure.find_contours(example, 0.1))[0] |
||
print('[', ', '.join([str((p[1], 5 - p[0])) for p in contours]), ']') |
print('[', ', '.join([str((p[1], 5 - p[0])) for p in contours]), ']') |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<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) ] |
[ (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 367: | Line 367: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
<lang |
<syntaxhighlight lang="raku" line># 20220708 Raku programming solution |
||
enum <E N W S>; |
enum <E N W S>; |
||
Line 409: | Line 409: | ||
} |
} |
||
return -1, -1, "Not found!" |
return -1, -1, "Not found!" |
||
}</ |
}</syntaxhighlight> |
||
Output is the same as the Phix entry. |
Output is the same as the Phix entry. |
||
Line 415: | Line 415: | ||
{{libheader|Wren-seq}} |
{{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. |
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. |
||
< |
<syntaxhighlight lang="ecmascript">import "./seq" for Lst, FrozenList |
||
/* A direction in the plane. */ |
/* A direction in the plane. */ |
||
Line 632: | Line 632: | ||
var ms = MarchingSquares.new(5, 6, example) |
var ms = MarchingSquares.new(5, 6, example) |
||
var path = ms.identifyPerimeter() |
var path = ms.identifyPerimeter() |
||
System.print(path)</ |
System.print(path)</syntaxhighlight> |
||
{{out}} |
{{out}} |