java - 在基于图 block 的 map 中查找多边形的内部坐标

Question

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

我需要在基于图 block 的游戏中找到“建筑物”的内部。

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

如果建筑物未完全显示在 View 中(右侧建筑物)，我已通过将整个绿色部分(-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

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

A* algorithm找到从给定起点到给定目标的路径。在您的情况下，开始就是目标，这意味着它是对“外部”单元格进行分类的引用点。从那里开始，我们搜索所有可以遍历的东西。

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

代码如下:

演示.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);

    }

}

类型.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;
    }
}

网格.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 为此编写了一个编辑器，如果您感兴趣的话，很快就会以博客文章的形式出现。基本上你的网格看起来像这样:

哪里

• 黑色细胞=墙壁
• 绿色单元格 = 可遍历单元格
• 蓝色单元格=从开始到结束的路径
• 白细胞 = 壁内细胞

这些数字是来自 A* 算法的数字:

• 上/左= g(从开始到当前单元格)
• 上/右 = h(从当前单元格到目标)
• 中心 = f = g + h

如果你不允许对角线移动，就像这样:

但这只是题外话:-)