在基于图块的地图中查找多边形的内部坐标

Question

如果列表中包含多边形的所有外边缘，我将如何找到内部坐标？为了简单起见，我画了下图来表示问题：

我需要在基于图块的游戏中找到 'buildings' 的内部。

外墙 - 灰色阴影单元格。
建筑物内部 - 浅蓝色单元格。

如果建筑物没有完全显示在视图中（右侧建筑物），我通过将整个绿色部分（-1、-1、0、-1 等）添加到列表中解决了这个问题。

如果不遵循一些疯狂的 if 搜索树，我不知道如何解决这个问题。我在这里发布一些提示、代码或伪代码。非常感谢任何帮助。非常感谢！ :)

编辑

@Andrew Thompson：我想我写错了我的情况。这不像您链接到的副本。我没有图像。我上面画的 excel 只是一个例子。例如：

我有一个包含棕色值的列表： IE。 {“1,1”、“2,1”、“3,1”、“1,2”等}

我需要一个相应的蓝色值列表：即。 {“2,2”、“2,6”、“3,6”、“4,6”等}

Answer 1

我发现这真的很有趣 post :) 我发现尝试解决这些看似简单的问题令人耳目一新，这真的令人耳目一新。

我想出了一个可以处理矩形区域的简单算法。它只是写在纸上，未经测试，但我会尽力解释它，看看您是否可以将其转换为实际代码。

我的想法是对该区域进行水平扫描，并使用某种状态机来识别可能的蓝色方块。该过程大致如下：

我们读了一行。在那里，我们寻找 三个或更多连续的棕色瓷砖。如果我们碰巧发现，我们将两个值存储在数据变量中：第一个列（使用图像的第一个方块，第 1 列）和最后一个列（同一个例子，3）。
我们又读了一行。在那里，在查找连续的行之前，我们查看第 1 列和第 3 列。 如果它们是棕色的，我们会查看它们之间的方块颜色（在本例中为方块 [2,2]）。 如果这些图块不是棕色的，那么我们将其存储在一个数据结构中，我们在其中跟踪可能是蓝色的图块。
我们又读了一行。我们再次查看第 1 列和第 3 列。再一次，它们是棕色的。再一次，我们看看它们之间的瓷砖颜色，这次它们是棕色的。很好，这是一个封闭的广场！我们将所有存储为潜在蓝色 ([2,2]) 的图块放入 实际蓝色.
我们又读了一行。我们再次查看第 1 列和第 3 列。哦，运气不好。它们不再是棕色的了。我们弹出 1 和 3 值，只要没有再次找到连续的行，我们就不会再在那里查找。

我现在要开会，如果我有时间的话，我会写一个简单的伪代码（只是为了好玩），在循环的每个点进行检查。如果我有更多时间，我会考虑进行某种改进以检测非正方形区域。我认为它可以非常简单，比如寻找与标记列相交的连续棕色瓷砖（标记，我的意思是例如上面示例运行中的 1 和 3）并调整该区域的新标记限制因此。

我也会尝试考虑像山一样的区域，您在地图的上部检测到两个不同的区域，但它们最终在下部连接在一起。我从没想过这是一个简单的问题，毕竟 :) 与此同时，我希望我能够为您提供一些见解。

Answer 2

这周我研究了 A* 算法。您的请求可能有其他解决方案，但由于我已经有了代码，所以只需根据您的需要对其进行调整即可。但是，对于您的特定要求，您也可以简单地使用 原始洪水填充算法 并以这种方式对单元格进行分类，请参阅算法代码中的方法。

A* algorithm 找到从给定起点到给定目标的路径。在您的情况下，开始就是目标，这意味着它是对 "outside" 单元格进行分类的参考点。从那里我们搜索我们可以遍历的一切。

我在示例中为您留下了路径查找代码，也许它对您的进一步需求有用。

代码如下：

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));

    }

}

内部单元格记录的结果是

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

从 0/0 到 8/8 的路径的结果是

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

我在 JavaFX 中为此编写了一个编辑器，如果您有兴趣，很快就会作为博客出现 post。基本上你的网格看起来像这样：

在哪里

黑色细胞 = 墙壁
绿色单元格 = 可遍历单元格
蓝色单元格 = 从头到尾的路径
白细胞 = 内壁细胞

数字是A*算法的数字：

top/left = g（从开始到当前单元格）
top/right = h（从当前单元格到目标）
中心=f=g+h

如果不允许对角线移动，则像这样：

但这只是题外话:-)

Answer 3

真是floodfill个问题。

你知道多边形的顶点坐标吗？还有一些算法可以更快地计算 floodfill。而且您不必决定哪部分是建筑物，哪部分不是。

如果您不知道顶点，则必须进行 "real" floodfill :

如果您知道有一块地砖不在建筑物中，只需填满那里，其余的就是建筑物。

如果你不知道，那么你可以继续填充，直到没有更多的瓷砖，你就把这个区域分成了区域。

那么实际上，如果不做一些假设，您就无法将建筑物与其他建筑物区分开来。例如，假设您的区域被一条棕线一分为二：哪一个是建筑物？

也许你知道地上的瓷砖比任何建筑物都多？那两栋楼不能互相接触？他们是凸的？

在基于图块的地图中查找多边形的内部坐标

Find inside coordinates of polygon in tile based map

java

awt

polygon

java-2d

coordinates