Marching squares: Difference between revisions
Content added Content deleted
(J: lame partial implementation -- no treatment of saddle points (this version will throw an error for saddle points)) |
|||
Line 6: | Line 6: | ||
See: [https://en.wikipedia.org/wiki/Marching_squares Marching squares] |
See: [https://en.wikipedia.org/wiki/Marching_squares Marching squares] |
||
=={{header|J}}== |
|||
This is a partial implementation, see the talk page for some discussion of the untouched issues. |
|||
<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}} |
|||
step2a=: {{ if. #y do. x+"1 y else. y end. }} |
|||
LUT=: <@".;._2 {{)n |
|||
EMPTY NB. 0 |
|||
0 0,:1 1 NB. 1 |
|||
0 1,:1 0 NB. 2 |
|||
0 0,:0 1 NB. 3 |
|||
0 0,:1 1 NB. 4 |
|||
a: NB. 5 not used |
|||
0 0,:1 0 NB. 6 |
|||
a: NB. 7 |
|||
1 0,:0 1 NB. 8 |
|||
1 1,:0 1 NB. 9 |
|||
a: NB. 10 not used |
|||
a: NB. 11 not used |
|||
a: NB. 12 not used |
|||
a: NB. 13 not used |
|||
EMPTY NB. 14 |
|||
EMPTY NB. 15 |
|||
}} |
|||
unwind=: {{ |
|||
near=. 7 8 5 1 3 {,(+/~ *&({:$y))i:1 |
|||
r=., c=. EMPTY |
|||
TODO=. I.(<EMPTY)~:Y=.,y |
|||
j=. _ |
|||
while.#TODO=. TODO-.j do. |
|||
adj=. (j+near) ([-.-.) TODO |
|||
if. #adj do. |
|||
j=. {.adj |
|||
else. |
|||
if. #c do. c=.EMPTY [r=. r,<~.c end. |
|||
j=. {.TODO |
|||
end. |
|||
c=. c, j{::Y |
|||
end. |
|||
r,<~.c |
|||
}}</lang> |
|||
Task example: |
|||
<lang J> img=: 4~:i.3 2 |
|||
img |
|||
1 1 |
|||
1 1 |
|||
0 1 |
|||
unwind step2 step1 img |
|||
┌───┐ |
|||
│1 2│ |
|||
│2 1│ |
|||
│3 1│ |
|||
│4 2│ |
|||
│5 3│ |
|||
│4 4│ |
|||
│3 4│ |
|||
│2 4│ |
|||
│1 3│ |
|||
└───┘</lang> |
|||
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). |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |