Marching squares: Difference between revisions

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. }}

end.

r,<~.c

 

Task example:

 

img

1 1

│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).

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

 

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.

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

 

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)]

=={{header|Lua}}==

Based on the Phix and Wren solutions.

local Directions = { -- clockwise from North

N = {x= 0, y=-1},

 

msMain (1, example)

<pre>

root: x=1 y=2

=={{header|Perl}}==

{{trans|Raku}}

no warnings 'experimental::for_list';

use List::Util 'any';

[0, 0, 0, 0, 0]);

 

{{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>

<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>

 

=={{header|Python}}==

from skimage import measure

 

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) ]

=={{header|Raku}}==

{{trans|Phix}}

 

enum <E N W S>;

}

return -1, -1, "Not found!"

Output is the same as the Phix entry.

 

{{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. */

var ms = MarchingSquares.new(5, 6, example)

var path = ms.identifyPerimeter()

 

{{out}}