Find inside coordinates of polygon in tile based map

Question

If I have all of the outer edges of polygons in a list how would I go about finding the inside coordinates?? To make matters simple I drew the following image to represent the problem:

I need to find the inside of 'buildings' in a tilebased game.

• outside walls - grey shaded cells.
• inside building - light blue cells.

In the event the building is not fully shown in view (right building) I have solved the issue by adding the entire green section (-1,-1, 0,-1, etc.) into the list.

Without following some insane if search tree I have no idea how to solve this. I am posting here for some tips, code, or psuedo code. Any help is so appreciated. Thanks so much! :)

---

EDIT

@Andrew Thompson: I think I miswrote my situaton. This is not like the duplicate you linked to. I don't have the image. The excel drawing I did above was just an example. For that example:

I have a list containing the brown values: ie. {"1,1", "2,1", "3,1", "1,2", etc.}

And I need a corresponding list of the blue values: ie. {"2,2", "2,6", "3,6", "4,6", etc.}

Answer 1

I toyed around with the A* algorithm this week. There may be other solutions to your request, but since I already have the code, it was just a matter of adapting it to your needs. However, for your specific requirement you could also simply use a primitive flood-fill algorithm and classify the cells this way, see the method in the algorithm code.

The A* algorithm finds a path from a given start to a given goal. In your case the start is the goal, which means it's a reference point that classifies an "outside" cell. From there on we search for everything that we can traverse.

I left the path finding code for you in the example, maybe it's of use for your further needs.

Here's the code:

Demo.java

import java.util.List;
import java.util.Set;


public class Demo {

    public static void main(String[] args) {

        // create grid like in the example
        int cols = 9;
        int rows = 9;

        Grid grid = new Grid( cols, rows);

        // create walls like in the example
        grid.getCell( 1, 1).setTraversable( false);
        grid.getCell( 2, 1).setTraversable( false);
        grid.getCell( 3, 1).setTraversable( false);
        grid.getCell( 1, 2).setTraversable( false);
        grid.getCell( 3, 2).setTraversable( false);
        grid.getCell( 6, 2).setTraversable( false);
        grid.getCell( 7, 2).setTraversable( false);
        grid.getCell( 8, 2).setTraversable( false);
        grid.getCell( 1, 3).setTraversable( false);
        grid.getCell( 2, 3).setTraversable( false);
        grid.getCell( 3, 3).setTraversable( false);
        grid.getCell( 6, 3).setTraversable( false);
        grid.getCell( 6, 4).setTraversable( false);
        grid.getCell( 7, 4).setTraversable( false);
        grid.getCell( 1, 5).setTraversable( false);
        grid.getCell( 2, 5).setTraversable( false);
        grid.getCell( 3, 5).setTraversable( false);
        grid.getCell( 4, 5).setTraversable( false);
        grid.getCell( 5, 5).setTraversable( false);
        grid.getCell( 7, 5).setTraversable( false);
        grid.getCell( 8, 5).setTraversable( false);
        grid.getCell( 1, 6).setTraversable( false);
        grid.getCell( 5, 6).setTraversable( false);
        grid.getCell( 1, 7).setTraversable( false);
        grid.getCell( 2, 7).setTraversable( false);
        grid.getCell( 3, 7).setTraversable( false);
        grid.getCell( 4, 7).setTraversable( false);
        grid.getCell( 5, 7).setTraversable( false);

        // find traversables
        // -------------------------

        AStarAlgorithm alg = new AStarAlgorithm();

        Cell start;
        Cell goal;

        // reference point = 0/0
        start = grid.getCell(0, 0);
        Set<Cell> visited = alg.getFloodFillCells(grid, start, true);

        // find inside cells
        for( int row=0; row < rows; row++) {
            for( int col=0; col < cols; col++) {

                Cell cell = grid.getCell(col, row);

                if( !cell.traversable) {
                    cell.setType(Type.WALL);
                }
                else if( visited.contains( cell)) {
                    cell.setType(Type.OUTSIDE);
                } 
                else {
                    cell.setType(Type.INSIDE);
                }

            }
        }

        // log inside cells
        for( int row=0; row < rows; row++) {
            for( int col=0; col < cols; col++) {
                Cell cell = grid.getCell(col, row);
                if( cell.getType() == Type.INSIDE) {
                    System.out.println("Inside: " + cell);
                }
            }
        }

        // path finding
        // -------------------------

        // start = top/left, goal = bottom/right
        start = grid.getCell(0, 0);
        goal = grid.getCell(8, 8);

        // find a* path
        List<Cell> path = alg.findPath(grid, start, goal, true);

        // log path
        System.out.println(path);

        System.exit(0);

    }

}

Type.java

public enum Type {

    OUTSIDE,
    WALL,
    INSIDE,

}

Cell.java

public class Cell implements Cloneable {

    int col;
    int row;
    boolean traversable;
    Type type;

    double g;
    double f;
    double h;

    Cell cameFrom;

    public Cell( int col, int row, boolean traversable) {
        this.col=col;
        this.row=row;
        this.traversable = traversable;
    }

    public double getF() {
        return f;
    }

    public double getG() {
        return g;
    }

    public double getH() {
        return h;
    }

    public void setTraversable( boolean traversable) {
        this.traversable = traversable;
    }

    public void setType( Type type) {
        this.type = type;
    }

    public Type getType() {
        return this.type;
    }

    public String toString() {
        return col + "/" + row;
    }
}

Grid.java

public class Grid {

    Cell[][] cells;

    int cols;
    int rows;

    public Grid( int cols, int rows) {
        this.cols = cols;
        this.rows = rows;
        cells = new Cell[rows][cols];

        for( int row=0; row < rows; row++) {
            for( int col=0; col < cols; col++) {
                cells[row][col] = new Cell( col, row, true); 
            }
        }
    }

    public Cell getCell( int col, int row) {
        return cells[row][col];
    }

    /**
     * Get neighboring cells relative to the given cell. By default they are top/right/bottom/left. 
     * If allowDiagonals is enabled, then also top-left, top-right, bottom-left, bottom-right cells are in the results.
     * @param cell
     * @param allowDiagonals
     * @return
     */
    public Cell[] getNeighbors(Cell cell, boolean allowDiagonals) {

        Cell[] neighbors = new Cell[ allowDiagonals ? 8 : 4];

        int currentColumn = cell.col;
        int currentRow = cell.row;

        int neighborColumn;
        int neighborRow;

        // top
        neighborColumn = currentColumn;
        neighborRow = currentRow - 1;

        if (neighborRow >= 0) {
            if( cells[neighborRow][neighborColumn].traversable) {
                neighbors[0] = cells[neighborRow][neighborColumn];
            }
        }

        // bottom
        neighborColumn = currentColumn;
        neighborRow = currentRow + 1;

        if (neighborRow < rows) {
            if( cells[neighborRow][neighborColumn].traversable) {
                neighbors[1] = cells[neighborRow][neighborColumn];
            }
        }

        // left
        neighborColumn = currentColumn - 1;
        neighborRow = currentRow;

        if ( neighborColumn >= 0) {
            if( cells[neighborRow][neighborColumn].traversable) {
                neighbors[2] = cells[neighborRow][neighborColumn];
            }
        }

        // right
        neighborColumn = currentColumn + 1;
        neighborRow = currentRow;

        if ( neighborColumn < cols) {
            if( cells[neighborRow][neighborColumn].traversable) {
                neighbors[3] = cells[neighborRow][neighborColumn];
            }
        }

        if (allowDiagonals) {

            // top/left
            neighborColumn = currentColumn - 1;
            neighborRow = currentRow - 1;

            if (neighborRow >= 0 && neighborColumn >= 0) {
                if( cells[neighborRow][neighborColumn].traversable) {
                    neighbors[4] = cells[neighborRow][neighborColumn];
                }
            }

            // bottom/right
            neighborColumn = currentColumn + 1;
            neighborRow = currentRow + 1;

            if (neighborRow < rows && neighborColumn < cols) {
                if( cells[neighborRow][neighborColumn].traversable) {
                    neighbors[5] = cells[neighborRow][neighborColumn];
                }
            }

            // top/right
            neighborColumn = currentColumn + 1;
            neighborRow = currentRow - 1;

            if (neighborRow >= 0 && neighborColumn < cols) {
                if( cells[neighborRow][neighborColumn].traversable) {
                    neighbors[6] = cells[neighborRow][neighborColumn];
                }
            }

            // bottom/left
            neighborColumn = currentColumn - 1;
            neighborRow = currentRow + 1;

            if (neighborRow < rows && neighborColumn >= 0) {
                if( cells[neighborRow][neighborColumn].traversable) {
                    neighbors[7] = cells[neighborRow][neighborColumn];
                }
            }

        }


        return neighbors;
    }

}

AStarAlgorithm.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * A* algorithm from http://en.wikipedia.org/wiki/A*_search_algorithm
 */
public class AStarAlgorithm {

    public class CellComparator implements Comparator<Cell>
    {
        @Override
        public int compare(Cell a, Cell b)
        {
            return Double.compare(a.f, b.f);
        }

    }

    /**
     * Find all cells that we can traverse from a given reference start point that's an outside cell.
     * Algorithm is like the A* path finding, but we don't stop when we found the goal, neither do we consider the calculation of the distance.
     * @param g
     * @param start
     * @param goal
     * @param allowDiagonals
     * @return
     */
    public Set<Cell> getFloodFillCells(Grid g, Cell start, boolean allowDiagonals) {

        Cell current = null;

        Set<Cell> closedSet = new HashSet<>();

        Set<Cell> openSet = new HashSet<Cell>();
        openSet.add(start);

        while (!openSet.isEmpty()) {

            current = openSet.iterator().next();

            openSet.remove(current);

            closedSet.add(current);

            for (Cell neighbor : g.getNeighbors(current, allowDiagonals)) {

                if (neighbor == null) {
                    continue;
                }

                if (closedSet.contains(neighbor)) {
                    continue;
                }

                openSet.add(neighbor);
            }

        }

        return closedSet;

    }

    /**
     * Find path from start to goal.
     * @param g
     * @param start
     * @param goal
     * @param allowDiagonals
     * @return
     */
    public List<Cell> findPath( Grid g, Cell start, Cell goal, boolean allowDiagonals) {

        Cell current = null;
        boolean containsNeighbor;

        int cellCount = g.rows * g.cols;

        Set<Cell> closedSet = new HashSet<>( cellCount);

        PriorityQueue<Cell> openSet = new PriorityQueue<Cell>( cellCount, new CellComparator());
        openSet.add( start);

        start.g = 0d;
        start.f = start.g + heuristicCostEstimate(start, goal);


        while( !openSet.isEmpty()) {

            current = openSet.poll();

            if( current == goal) {
                return reconstructPath( goal);
            }

            closedSet.add( current);

            for( Cell neighbor: g.getNeighbors( current, allowDiagonals)) {

                if( neighbor == null) {
                    continue;
                }

                if( closedSet.contains( neighbor)) {
                    continue;
                }

                double tentativeScoreG = current.g + distBetween( current, neighbor);

                if( !(containsNeighbor=openSet.contains( neighbor)) || Double.compare(tentativeScoreG, neighbor.g) < 0) {

                    neighbor.cameFrom = current;

                    neighbor.g = tentativeScoreG;

                    neighbor.h = heuristicCostEstimate(neighbor, goal);
                    neighbor.f = neighbor.g + neighbor.h;

                    if( !containsNeighbor) {
                        openSet.add( neighbor);
                    }
                }
            }

        }

        return new ArrayList<>();
    }

    private List<Cell> reconstructPath( Cell current) {

        List<Cell> totalPath = new ArrayList<>(200); // arbitrary value, we'll most likely have more than 10 which is default for java

        totalPath.add( current);

        while( (current = current.cameFrom) != null) {

            totalPath.add( current);

        }

        return totalPath;
    }

    private double distBetween(Cell current, Cell neighbor) {
        return heuristicCostEstimate( current, neighbor); // TODO: dist_between is heuristic_cost_estimate for our use-case; use various other heuristics
    }

    private double heuristicCostEstimate(Cell from, Cell to) {

        return Math.sqrt((from.col-to.col)*(from.col-to.col) + (from.row - to.row)*(from.row-to.row));

    }

}

The result for the inside cell logging is

Inside: 2/2
Inside: 7/3
Inside: 8/3
Inside: 8/4
Inside: 2/6
Inside: 3/6
Inside: 4/6

The result for the path from 0/0 to 8/8 is

[8/8, 7/7, 7/6, 6/5, 5/4, 5/3, 5/2, 4/1, 3/0, 2/0, 1/0, 0/0]

I wrote an editor for this in JavaFX, will come up as a blog post soon, if you are interested. Basically your grid will look like this:

Where

• black cells = walls
• green cells = traversable cells
• blue cells = path from start to end
• white cells = cells inside walls

The numbers are the ones from the A* algorithm:

• top/left = g (from start to current cell)
• top/right = h (from current cell to goal)
• center = f = g + h

And like this if you don't allow diagonal movement:

But that's just off-topic :-)

Answer 2

I find this a really interesting post :) I find refreshing to try to resolve these apparently simple problems, it's really refreshing.

I've come up with a simple algorithm that could work with rectangular areas. It's just on the paper, untested, but I'll try to explain it as better as I can to see you can convert it to actual code.

My idea is to perform horizontal sweeps to the area, and have some kind of status machine to recognize possible blue tiles. The process would be more or less the following:

• We read a row. There, we look for three or more consecutive brown tiles. If we happen to find that, we store two values in a data variable: the column of the first one (using the first square of your image, column 1) and the column of the last one (same example, 3).
• We read another row. And there, before looking for consecutive rows, we look into the 1 and 3 columns. If they're brown, we look at the color of the tiles between them (in this example, tile [2,2]). If those tiles are not brown, then we store that in a data structure, where we keep track of the potentially blue tiles.
• We read another row. Again, we look into the 1 and 3 columns. And again, they are brown. Again, we look to the color of the tiles between them, and this time they're brown. Good, this is a closed square! We put all those tiles we had stored as potentially blue, ([2,2]) to actual blue.
• We read another row. Again, we look into the 1 and 3 columns. Oh, no luck. They're not brown anymore. We pop the 1 and 3 values, we won't look there anymore as long as no consecutive rows are found again.

I have a meeting right now, if I have some time I'll write a simple pseudocode (just for fun) with the checks in every point of the loop. If I have some more time, I'll think on some kind of improvement to detect non-square areas. I think it can be pretty simple, something like looking for consecutive brown tiles intersecting with marked columns (by marked, I mean for example the 1 and 3 in the sample run above) and adjusting the new marked limits for that area accordingly.

I'll try to consider as well mountain-like areas where you detect two different areas in the upper part of the map, but they end up joining up in the lower part. I never thought this was a simple problem, after all :) Meanwhile, I hope I've been able to provide you some insight.

Answer 3

It's really a floodfill problem.

Do you know the coordinates of the vertices of the polygons ? Then there are algorithms that will compute the floodfill faster. And you won't have to decide which part is a building and which part isn't.

If you don't know the vertices, you will have to do a "real" floodfill :

If there is one tile you know is not in a building, just floodfill there and the rest is the buildings.

If you don't know that, then you can keep floodfilling until there is no more tiles, and you will have divided the area into zones.

Then actually you can't tell the buildings from the rest without making some assumptions. For example, suppose your area is divided in two by a brown line : which one is the building ?

Maybe you know the ground has more tiles than any building ? That two buildings can't touch each other ? That they are convex ?