Talk:Marching squares
Task needs work
Currently, the task description does not allow us to determine whether an implementation is correct.
The referenced wiki pages represent an image transformation, but currently no tasks here generate images (and this site is poorly equipped to represent images).
Instead, some of the tasks currently represent a transformation from a bitmap to a sequence of non-unique coordinates, but it's not clear that those coordinates represent the marching squares image transformation.
Specifically, we see:
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
being transformed into a sequence of 11 coordinates pairs which correspond to 9 distinct coordinates arranged like this:
0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0
This transformation lacks symmetry which makes it suspect. Currently there's nothing in the task description to help us understand this issue. It's difficult to see how this corresponds to a contour of the original image, but if the above were rotated counterclockwise 90 degrees, the inner region of zeros do correspond to the original image:
0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0
Also, one of the duplicated coordinate pairs corresponds to the beginning and end of the path. (But why is the other coordinate pair duplicated?)
In contrast, the Wren and Phix solutions identify a path with length 11 composed of 10 unique coordinates which would probably correspond to these positions (or maybe this should be shifted up and to the left by one grid coordinate? I'm guessing because I don't know whether the 0,0 coordinate would correspond to the upper left hand corner of the bitmap or if it would be outside the bitmap):
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1
Again, this lacks symmetry. This one seems to correspond roughly to the original shape and orientation (though the orientation is my doing, and the interior of the countour does not correspond to the original shape).
Possibly all of these results are correct. Possibly not. Currently the task is too ambiguous. --Rdm (talk) 01:34, 30 June 2022 (UTC)
Looking at this more closely, the implementation of identifyPerimeter
at http://www.tomgibara.com/computer-vision/MarchingSquares.java is unable to identify diagonal contour lines, even though half of the contour lines in the lookup table of the basic algorithm are diagonals. Also, that identifyPerimeter
implementation finds only one contour line (and only if that contour line corresponds to a perimeter which touches the center of the image). --Rdm (talk)
- Overall I would agree this task is far from perfect and TG's code is at best a gross oversimplification (whilst somehow also being a gross overcomplication) that bears little resemblance to anything else I've seen. Then again in my opinion the wp description of the algorithm also leaves much to be desired. It seems to me the Julia and Python outputs are rotated by 90 but with 99.9% of the actual implementation being somewhat hidden I can't exactly be sure about that. A much better (text-representable) input, the expected/desired output (ditto), and maybe a few simple (third-party-hosted) images would certainly help. --Pete Lomax (talk) 15:43, 30 June 2022 (UTC)
- FWIW, I suspect the Wren and Phix output corresponds to the "gaps" in the input, and maybe the (quite blatently deliberate and easily undone) negative Y result is somehow supposed to indicate that? --Pete Lomax (talk) 20:43, 30 June 2022 (UTC)
- If I understand right, the result that we are expecting should correspond to positions half way between pixels. Looking at the wikipedia entry, we should be working with an intermediate result something like this:
- 0 0 0 0 0
- 0 2 3 1 0
- 0 6 15 9 0
- 0 4 14 9 0
- 0 0 4 8 0
- 0 0 0 0 0
Oval of Cassini
It is always difficult when a task is submitted with no implementation and just a reference to Wikipedia, especially if the task's author does not then engage in the discussion. I suggest the task description should be expanded to in include an example, and that that example should be Oval of Cassini. The task being to use Marching Squares to produce Expected Output.--Nigel Galloway (talk) 14:36, 1 July 2022 (UTC)