title: Finding empty terrain rectangles in Grid-Graph
body: <p>The city in my game is randomly generated but is a graph of roads and intersections that can only form rectangles:</p>
  
  <p><img src="https://i.stack.imgur.com/06KIa.png" alt="enter image description here"></p>
  
  <p>As can be seen, my terrain is pretty empty. What I want to do is find each empty rectangle and store in in a list of rectangles, forming Lots.</p>
  
  <p><img src="https://i.stack.imgur.com/LWJis.png" alt="enter image description here"></p>
  
  <p>As you can see in this illustration, I filled in 3 'lots' and in 1 I showed the 3 rectangles it is made of.</p>
  
  <p>My data structures are:</p>
  
  <pre><code>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 &lt; 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;
      }
  }
  </code></pre>
  
  <p>The city is a list of roads and intersections.</p>
  
  <p>Is there some sort of algorithm that could generate these lots and their rectangles?</p>
  
  <p>Thanks</p>