No account? Create an account
 Algorithm - The Mad Schemes of Dr. Tectonic [entries|archive|friends|userinfo]
Beemer

 [ userinfo | livejournal userinfo ] [ archive | journal archive ]

(Deleted comment)
 From: 2012-06-28 05:53 am (UTC) (Link)
Ha, yes. Boundary polygon, not bounding box. Makes it a very different problem.

Though they're not completely arbitrary regions; I think the algorithm would break if you're actually working on the globe (as I am) and your region touches a pole or spans the international date line (not cases I have to deal with, thankfully).
 From: 2012-06-28 05:56 am (UTC) (Link)
If you were using this to see how somebody thinks, the bounding box version of the question might be an interesting lead-in, just to see how quickly they can articulate the solution...
 From: 2012-06-29 05:47 am (UTC) (Link)
All I can think of is Minesweeper and Game of Life. So would this pseudocode work? (Please excuse the bad form. It's been a while.)

On the initial grid, do a raster scan and on each grid cell with value 1, compare north, east, west and south neighbours. If any neighbour has a value of zero, mark as an edge cell by recording adjoining zero cells appear on the N/E/S/W side. This gives an outline of the region.

Rasterwise, find the first edge cell (will be marked WN, WNE or WNES). Left edge is FirstPoint. Top edge is TemporaryEndPoint. Add FirstPoint to vertex list. Direction-of-travel := EAST. Next cell is East.

While TemporaryEndPoint != FirstPoint

If Direction-of-travel = EAST
..top edge is TemporaryEndPoint.
..While cell marked N
....top edge is TemporaryEndPoint.
....Next cell to East.
..End While
..If cell marked NE
....add top edge to vertex list.
....right edge is TemporaryEndPoint.
....Direction-of-travel := SOUTH.
....Next cell to South.
..Elseif cell not edge
....Direction-of-travel := NORTH.
....Next cell to North.
..Endif

Elseif Direction-of-travel = NORTH
..left edge is TemporaryEndPoint.
..While cell marked W
....left edge is TemporaryEndPoint.
....Next cell to North.
..End While
..If cell marked WN
....add left edge to vertex list.
....Top edge is TemporaryEndPoint.
....Direction-of-travel := EAST.
....Next cell to East.
..Elseif cell not an edge
....Direction-of-travel := West.
....Next cell to West.
..Endif

Elseif Direction-of-travel = WEST
..bottom edge is TemporaryEndPoint.
..While cell marked S
....bottom edge is TemporaryEndPoint.
....Next cell to West.
..EndWhile
..If cell marked SW
....add bottom edge to vertex list
....left edge is TemporaryEndPoint.
....Direction-of-travel := NORTH.
....Next cell to North.
..Elseif cell not edge
....Direction-of-travel := SOUTH.
....Next cell to South.
..Endif

Elseif Direction-of-travel = SOUTH
..right edge is TemporaryEndPoint.
..While cell marked E
....right edge is TemporaryEndPoint.
....Check cell to North.
..EndWhile
..If cell marked ES
....add right edge to vertex list
....Bottom edge is TemporaryEndPoint
....Direction-of-travel := WEST.
....Next cell is West
..ElseIf cell not an edge
....Direction-of-travel := West
....Next cell to West.
..EndIf
EndWhile
Done

"Next cell to West" would translate to X := X-1 if that is not obvious. "Top edge" is coordinates of center less 0.5 on the X value.