StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>How big is the space you're working in?</p> <p>Simulate the whole thing with a simple rectangular grid assuming even-rows are staggered right.</p> <p>Any node has coordinates <code>[x,y]</code></p> <ul> <li>For <code>(y%2 == 0)</code> neighbor nodes are <code>[x-1,y][x+1,y][x,y+1][x,y-1][x-1,y-1][x-1,y+1]</code></li> <li>For <code>(y%2 == 1)</code> neighbor nodes are <code>[x-1,y][x+1,y][x,y+1][x,y-1][x+1,y-1][x+1,y+1]</code></li> </ul> <p>Each node can be <em>full</em> or <em>empty</em> and empty nodes can be <em>checked</em> or <em>not checked</em>. Originally all empty nodes are <em>not checked</em>.</p> <p>Check if a node belongs to a hole by:</p> <ul> <li>if node is <em>full</em> - it does not belong to hole, it belongs to the shape.</li> <li>if a node is <em>empty</em> mark node as <em>checked</em>.</li> <li>Iterate over all neighbor nodes: <ul> <li>Skip nodes marked as <em>checked</em> or <em>full</em></li> <li>recursively repeat the search for all nodes <em>not checked</em>.</li> </ul></li> <li>If the recursion brings you into any <code>x<0, y<0, x>MAX_X, y>MAX_Y</code>, abort. The node is <em>outside the shape</em></li> <li>If the recursion ends without finding edges of the playfield, the node <em>belongs to a hole</em>.</li> </ul> <p>Additionally, you may now repeat the procedure turning all <em>checked</em> nodes into <em>outside</em> or <em>hole</em> for later reference.</p> <p>If you want to index all holes at start, it may be easier to find all <em>not checked</em> empty nodes at borders of the playfield (<code>x==0, y==0, x==MAX_X, y==MAX_Y</code>) and use the above algorithm to mark them as <em>outside</em>. All remaining empty nodes are holes.</p> <p>Depending on your grid size, you may implement it as 2D array of structs/objects containing object state (or even <code>char</code>s, with status as bits of the number), sized [MAX_X+1][MAX_Y+1] if it's reasonably sized, or as a list (vector) of full nodes, each containing its coords, status and if you want this to be more speed-optimal, neighbors. In this case, search the shape, finding all <em>empty</em> neighbor nodes for potential holes. Edge nodes with extreme coords (lowest/highest x/y) belong to "outside". Follow their empty neighbors that have full neighbors, to find the outer edge of the shape. All remaining are inner edges and after following the algorithm starting with them you'll have all your "holes".</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload