發現在網格圖形

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