发现在网格图形

Question

在我游戏中的城市是随机生成的空地形矩形，但道路和路口的一个图表，只能形成矩形：

可以看出，我的地形很空。我想要做的是找到每个空矩形并存储在一个矩形列表中，形成很多。

正如你在这个例子看，我填写3“大量”和1我展示了3个矩形它是由。

我的数据结构是：

package com.jkgames.gta; 

import android.graphics.Bitmap; 
import android.graphics.RectF; 

public class Intersection extends Entity 
{ 
    Road topRoad; 
    Road leftRoad; 
    Road bottomRoad; 
    Road rightRoad; 
    Bitmap image; 

    public Bitmap getImage() 
    { 
     return image; 
    } 

    public void setImage(Bitmap image) 
    { 
     this.image = image; 
    } 

    public Intersection(RectF rect, Bitmap image) 
    { 
     setRect(rect); 
     setImage(image); 
    } 

    public Road getTopRoad() 
    { 
     return topRoad; 
    } 

    public void setTopRoad(Road topRoad) 
    { 
     this.topRoad = topRoad; 
    } 

    public Road getLeftRoad() 
    { 
     return leftRoad; 
    } 

    public void setLeftRoad(Road leftRoad) 
    { 
     this.leftRoad = leftRoad; 
    } 

    public Road getBottomRoad() 
    { 
     return bottomRoad; 
    } 

    public void setBottomRoad(Road bottomRoad) 
    { 
     this.bottomRoad = bottomRoad; 
    } 

    public Road getRightRoad() 
    { 
     return rightRoad; 
    } 

    public void setRightRoad(Road rightRoad) 
    { 
     this.rightRoad = rightRoad; 
    } 

    @Override 
    public void draw(GraphicsContext c) 
    { 
     c.drawRotatedScaledBitmap(image, getCenterX(), getCenterY(), 
        getWidth(), getHeight(), getAngle()); 
    } 

} 

public class Road extends Entity 
{ 
    private Bitmap image = null; 
    private Intersection startIntersection; 
    private Intersection endIntersection; 
    private boolean topBottom; 

    public Road(RectF rect, Intersection start, Intersection end, 
      Bitmap image, boolean topBottom) 
    { 
     setRect(rect); 
     setStartIntersection(start); 
     setEndIntersection(end); 
     setImage(image); 
     setTopBottom(topBottom); 
    } 

    @Override 
    public void draw(GraphicsContext c) 
    { 
     //Rect clipRect = c.getCanvas().getClipBounds(); 
     //c.getCanvas().clipRect(getRect()); 
     float sizeW; 
     float sizeH; 
     if(isTopBottom()) 
     { 
      sizeW = getWidth(); 
      sizeH = (sizeW/image.getWidth()) * image.getHeight(); 
     } 
     else 
     { 
      sizeW = getHeight(); 
      sizeH = (sizeW/image.getWidth()) * image.getHeight(); 

     } 

     int numTiles = isTopBottom() ? (int)Math.ceil(getHeight()/sizeH) : 
      (int)Math.ceil(getWidth()/sizeW); 

     for(int i = 0; i < numTiles; ++i) 
     { 
      if(isTopBottom()) 
      { 
       c.drawRotatedScaledBitmap(
         image, 
         getRect().left + (sizeW/2.0f), 
         (getRect().top + (sizeH/2.0f)) + (sizeH * i), 
         sizeW, sizeH, 0.0f); 
      } 
      else 
      { 
       c.drawRotatedScaledBitmap(
         image, 
         getRect().left + (sizeH/2.0f) + (sizeH * i), 
         getRect().top + (sizeH/2.0f), 
         sizeW, sizeH, (float)Math.PI/2.0f); 
      } 

     } 

    // c.getCanvas().clipRect(clipRect); 
    } 

    public Bitmap getImage() 
    { 
     return image; 
    } 

    public void setImage(Bitmap image) 
    { 
     this.image = image; 
    } 

    public Intersection getStartIntersection() 
    { 
     return startIntersection; 
    } 

    public void setStartIntersection(Intersection startIntersection) 
    { 
     this.startIntersection = startIntersection; 
    } 

    public Intersection getEndIntersection() 
    { 
     return endIntersection; 
    } 

    public void setEndIntersection(Intersection endIntersection) 
    { 
     this.endIntersection = endIntersection; 
    } 

    public boolean isTopBottom() 
    { 
     return topBottom; 
    } 

    public void setTopBottom(boolean topBottom) 
    { 
     this.topBottom = topBottom; 
    } 
} 

的城市道路和交叉路口的列表。

是否有某种算法可以生成这些批次及其矩形？

感谢

Answer 1

是在我脑海中是使用洪水填充算法来建立你的地区名单的最简单的方法。所以基本上

foreach square: 
    if the square isn't part of a region: 
     create a new empty region list 
     add the square to it 
     recursivly add all neighboring squares to the region 

最终的结果将是，你将拥有任何你想要的（看看，看看是否有任何包含平方在为有建筑物上，颜色的区域，你可以再做列表用户等）。

注意：为了确定一个正方形是否属于某个区域的一部分，我会为该正方形数据结构添加一个标记的标志或其他东西，这样当您开始时，您会通过并清除所有这些标志，然后当您为设置该标志的区域添加一个正方形，并且想要检查某个区域是否位于区域中时，您只需检查该标志是否设置。这样你最终得到一个线性时间算法来构建你的区域列表。

正如马库斯在这里的评论中指出的那样，这个“标志”实际上可以是一个Lot对象的指针/引用，它包含了你的方格列表，这可能会方便反正。

Answer 2

for (int y = 0; y < height; y++) 
for (int x = 0; x < width; x++) { 
    if (x > 0 && squares[y][x].isConnectedTo(squares[y][x-1]) { 
     // Connected from the left 
     squares[y][x-1].getLot().addSquare(squares[y][x]); 

     if (y > 0 && squares[y][x].isConnectedTo(squares[y-1][x]) { 
      // Connected from both the left and above 
      squares[y-1][x].getLot().mergeWith(squares[y][x].getLot()); 
     } 
    } 
    else if (y > 0 && squares[y][x].isConnectedTo(squares[y-1][x]) { 
     // Connected from above 
     squares[y-1][x].getLot().addSquare(squares[y][x]); 
    } 
    else { 
     // Not connected from either 
     createNewLot().addSquare(squares[y][x]); 
    } 
} 

• Lot.addSquare(…)增加了广场的地段，并在广场上呼吁setLot(…)。
• Lot.mergeWith(…)合并两个批次，并重新分配分配给它们的正方形，如果它们不是相同的批次。
• Square.isConnectedTo(…)检查它们是否是邻居，并且中间没有道路。

你可以通过使用Disjoint-set data structure