CODEWITHSUNDEEP
algorithmlanguage-agnosticgrid
Paul Manta
Paul Manta

Reputation: 31577

How to check if selected cells on a grid form a 'tunnel'?

Given a grid map where each cell can be described by a pair (x, y), and a vector of such cells, how can I (nicely) check if the cells in that vector form a 'tunnel', ie. they are all lined up either vertically or horizontally? But what if I only want to see if most of them are lined up (and not all)?

All are lines up             Most are lined up      Not lined up

                             C                       C C C
 C C C C C C C C             C C C C C C C C         C   C C C
                                 C                   C C C C
                                                         C C

Upvotes: 0

Views: 109

Answers (3)

Chris Lawlor
Chris Lawlor

Reputation: 48922

You could calculate the standard deviation of both the X and Y coordinates. The more 'tunnelled' your cells are, the lower the std deviation will be for either X or Y.

For example, in Python:

import numpy

def is_tunnelled(cells):
    # given cells=[(x,y), (x,y),...]
    x_values, y_values = zip(*cells)
    lowest_std_dev = min(numpy.std(x_values), numpy.std(y_values))
    return lowest_std_dev < STD_DEVIATION_THRESHOLD

It's up to you to determine what the value of STD_DEVIATION_THRESHOLD should be.

Upvotes: 1

ingofreyer
ingofreyer

Reputation: 1164

You could do a histogram of the x and y coordinates of the cells. If all cells are lined up horizontally, you get only one y-value in your histogramm and lots of consecutive x-values, which all occur only one times. Vertically is the same with x and y flipped.

If you want to check, if most of them are lined up, search for the value in the histogram, which has the most occurences (longest possible tunnel) and check the cells with that x or y-coordinate, if they are lined up (that is: their y or x-coordinates (depending on wheter x or y was used in the previous step) are consecutive without a gap (maybe sort them first)) If they are not, search for the second highest occurrence value, ...

Upvotes: 2

hammar
hammar

Reputation: 139890

You can check if they make a horizontal tunnel by first checking that their y coordinates are all equal, then sort by the x coordinate and traverse from left to right to check for gaps. Use the opposite coordinates to check for vertical tunnels.

For the approximate check you will have to clarify what you mean by "most".

Upvotes: 1

Related Questions