# Filling grid cells inside a shape

**URL:** <https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427>\
**Category:** Coding Questions\
**Created:** [November 10, 2021, 3:20am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427 "2021-11-10T03:20:24Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![tribblesontoast](https://avatars.discourse-cdn.com/v4/letter/t/e99b99/32.png) [@tribblesontoast](https://discourse.processing.org/u/tribblesontoast)\
**Post date:** [November 10, 2021, 3:20am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/1 "2021-11-10T03:20:24Z")

</div>

Hi all,

I’m writing a program that visualises text from posters as a heatmap.  
I draw shapes around the titles of the posters and each of these positions is saved as a PVector.  
In order to visualise these on the heatmap, I use [Seb Delisle’s triangle rectangle intersection test](http://sebleedelisle.com/2009/05/super-fast-trianglerectangle-intersection-test/) to determine which cell on my grid intersects with the lines of my drawn shape.  
This works brilliantly and it shows the shapes I drew, the issue I need to resolve is that the shapes aren’t filled.

_How can I determine which cells are inside the shape?_

The shapes are not rectangular and could have any number of points and could be abnormal like stars with ups and downs of the points.

any help is appreciated.

this is the code that does the checking of the points for the intersection:

```auto

  for (Cell c : grid) {
    for (int i = 0; i < selPoints.size()-1; i++) {
      if (lineRectIntersect(
        selPoints.get(i).x, selPoints.get(i).y, selPoints.get(i+1).x, selPoints.get(i+1).y, 
        c.pos.x, c.pos.y, c.w, c.h) == true && !c.allFilms.contains(fileName)) {

        c.iterateGenreAndHeatAndFilmlists(genres, fileName);
        if (c.heat > high) high = c.heat;
      }
    }
  }

```

---

<div class="post-metadata">

**Author:** ![tribblesontoast](https://avatars.discourse-cdn.com/v4/letter/t/e99b99/32.png) [@tribblesontoast](https://discourse.processing.org/u/tribblesontoast)\
**Post date:** [November 12, 2021, 3:33am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/2 "2021-11-12T03:33:17Z")

</div>

I have made some progress.  
Once all the films are mapped to the cells on the grid, for each film I loop through the grid and check if each cell contains a reference to it, and then work along that row of the grid until i come to another cell that contains a reference to that film - this way i should fill the inside of the shape.  
This works, awesome, however it does have an issue when it can start from a far side and fill outside the shape… So I added some logic to limit it to within the rightmost edge of the shape, this still allows the cell outside the shape to be filled up to this point.  
Images below to illustrate:

Shape to be filled:  
 ![Test](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/0/03beacb3f43ac66ed8d9b32893533e60a360afd4.png)

Shape filled but so are the external areas…  
 ![Test2](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/2/2667e0dcfb367956c3258064060bd3b470d18619.png)

Code from above post but with some additional logic - this is non-functional as the program is too messy currently to do an MVCE

How can I get it to respect the bounds of the shape? I’ve added other logic to try and limit based on top and bottom position but it either fills everything or the wrong parts.

_It’s so close to being finished, what check do I need to do to get it not fill those external areas?_

```auto
//establishes the outer edges of the shape to be drawn
  for (int k = 0; k < selPoints.size(); k++) {
    if (selPoints.get(k).x < leftMost) leftMost = selPoints.get(k).x;
    if (selPoints.get(k).x > rightMost) rightMost = selPoints.get(k).x;
    if (selPoints.get(k).y > bottomMost) bottomMost = selPoints.get(k).y;
    if (selPoints.get(k).y < topMost) topMost = selPoints.get(k).y;
  }

//loops through the grid and checks the lines for intersection with grid cells
  for (Cell c : grid) {
    for (int i = 0; i < selPoints.size()-1; i++) {
      if (lineRectIntersect(
        selPoints.get(i).x, selPoints.get(i).y, selPoints.get(i+1).x, selPoints.get(i+1).y, 
        c.pos.x, c.pos.y, c.w, c.h) == true && !c.allFilms.contains(fileName)) {

        c.iterateGenreAndHeatAndFilmlists(genres, fileName);
        if (c.heat > high) high = c.heat;
      }
    }
  }

//the new logic - looping through the grid to check if we are inside the shape
  for (Cell c : grid) {
    int thisCell = grid.indexOf(c);
    int nextCell = grid.indexOf(c)+1;

    if (nextCell < grid.size()) {
      if (grid.get(thisCell).allFilms.contains(fileName) 
        && !grid.get(nextCell).allFilms.contains(fileName) 
        && grid.get(nextCell).pos.x < rightMost) {
        grid.get(nextCell).iterateGenreAndHeatAndFilmlists(genres, fileName);
        if (grid.get(nextCell).heat > high) high = grid.get(nextCell).heat;
      }
    }
  }

```

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [November 12, 2021, 11:32am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/3 "2021-11-12T11:32:32Z")

</div>

Hi,

You are looking for a [flood fill](https://en.wikipedia.org/wiki/Flood_fill) algorithm.

Since you did not post all you code, I couldn’t adapt it completely to your case but I still created a simple Cell class to show you how you could do it.  
In setup, I create a rectangle that could be any shape you want as long as it is a closed shape. Then when you press a mouse button, I run the flood fill algorithm starting with a cell in the center of the screen.  
Keep in mind that it is a quick and dirty code, there are things that could be improved (I did not check for out of bound cells or tried to improve performance):

```auto
// Cell class
class Cell {
 public int x, y;
 public boolean selected;
 private int size;
 
 Cell(int x, int y) {
   this.x = x;
   this.y = y;
   size = 20;
   selected = false;
 }
 
 public void draw() {
   noStroke();
   if (selected) {
     fill(67, 183, 240);
   } else {
     fill(77, 114, 133);
   }
   rect(x * size, y * size, size, size);
 }
}

// Main code
Cell[][] cells = new Cell[30][20];
ArrayList<PVector> floodStack;

void setup() {
 size(600, 400);
 floodStack = new ArrayList<PVector>();
 
 for (int i = 0; i < 30; i++) {
   for (int j = 0; j < 20; j++) {
     cells[i][j] = new Cell(i, j);
     
     // Draw a box
     if ((i == 6 || i == 23) && j > 3 && j < 16) {
       cells[i][j].selected = true;
     }
     if ((j == 4 || j == 15) && i > 6 && i < 23) {
       cells[i][j].selected = true;
     }
     
   }
 }
}

void draw() {
 background(20);
 for (int i = 0; i < 30; i++) {
   for (int j = 0; j < 20; j++) {
     cells[i][j].draw();
   }
 }
}

void floodFill(int i, int j) {
 floodStack.add(new PVector(i, j));
 
 while (floodStack.size() > 0) {
   fillCell((int)floodStack.get(0).x, (int)floodStack.get(0).y);
   floodStack.remove(0);
 }
}

void fillCell(int i, int j) {
 cells[i][j].selected = true;
 
 //Add top cell
 if (!cells[i][j - 1].selected) {
   floodStack.add(new PVector(i, j - 1));
 }
 
 //Add right cell
 if (!cells[i + 1][j].selected) {
   floodStack.add(new PVector(i + 1, j));
 }
 
 //Add bot cell
 if (!cells[i][j + 1].selected) {
   floodStack.add(new PVector(i, j + 1));
 }
 
 //Add left cell
 if (!cells[i - 1][j].selected) {
   floodStack.add(new PVector(i - 1, j));
 }
}

void mouseClicked() {
 floodFill(15, 10);
}

```

---

<div class="post-metadata">

**Author:** ![hotfooted](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/hotfooted/32/3670_2.png) [@hotfooted](https://discourse.processing.org/u/hotfooted)\
**Post date:** [November 12, 2021, 1:20pm UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/4 "2021-11-12T13:20:33Z")

</div>

https://preview.p5js.org/hotfooted/embed/EBlFkho02

if i understood what you require correctly another option might be something like the above. (left arrow - change the renderType and right arrow - clear the buffer) you can view the source [here](https://editor.p5js.org/hotfooted/sketches/EBlFkho02). i know it’s p5js but it should be easy enough to convert.

---

<div class="post-metadata">

**Author:** ![tribblesontoast](https://avatars.discourse-cdn.com/v4/letter/t/e99b99/32.png) [@tribblesontoast](https://discourse.processing.org/u/tribblesontoast)\
**Post date:** [November 13, 2021, 5:38am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/5 "2021-11-13T05:38:59Z")

</div>

Hi hotfooted,  
Thanks for the help.  
I’ve tried to implement your first suggestion. I’m sharing below the method that ingests the films and populates the cells. I’ve tried to incorporate your logic modified for my program, but the program runs seemingly forever.

Printing the length of the floodstack array shows it gleefully adding more than over 500,000 (before I stopped it) grid cells to the array which is magic as there are only 7400.

I don’t think i’ve got this quite right but i’m not sure where i’ve gone wrong. I know not having the whole code is a nightmare, but the program is rather cumbersome to pull apart currently.

```auto
void getNextFilm(int index) {
  filmTitle = filmData.getRow(int(index));
  fileName = filmTitle.getString("FileName");
  String str = filmTitle.getString("Genres");
  String[] genres = split(str, '|');

  for (int i = 0; i < genreNames[0].length; i++) {
    for (int j = 0; j < genres.length; j++) {
      if (genres[j].equals(genreNames[0][i])) {
        int v = int(genreNames[1][i]);
        genreNames[1][i] = str(v+1);
      }
    }
  }
  String selPointsString = filmTitle.getString("SelectionPoints");
  String[] tmpPoints = splitTokens(selPointsString, "[]|,");
  selPoints = new ArrayList<PVector>();
  for (int i = 0; i < tmpPoints.length; i += 3) {
    selPoints.add(new PVector(float(tmpPoints[i]), float(tmpPoints[i+1]), float(tmpPoints[i+2])));
  }

  leftMost = width;
  rightMost = 0;
  topMost = height;
  bottomMost = 0;

  for (int k = 0; k < selPoints.size(); k++) {
    if (selPoints.get(k).x < leftMost) leftMost = selPoints.get(k).x;
    if (selPoints.get(k).x > rightMost) rightMost = selPoints.get(k).x;
    if (selPoints.get(k).y > bottomMost) bottomMost = selPoints.get(k).y;
    if (selPoints.get(k).y < topMost) topMost = selPoints.get(k).y;
  }

//do the lineRectIntersect check
  for (Cell c : grid) {
    for (int i = 0; i < selPoints.size()-1; i++) {
      if (lineRectIntersect(
        selPoints.get(i).x, selPoints.get(i).y, selPoints.get(i+1).x, selPoints.get(i+1).y, 
        c.pos.x, c.pos.y, c.w, c.h) == true && !c.allFilms.contains(fileName)) {

        c.iterateGenreAndHeatAndFilmlists(genres, fileName);
        if (c.heat > high) high = c.heat;
      }
    }
  }

//once shape has been outlined, check again to fill it
  for (Cell c : grid) {
    int thisCell = grid.indexOf(c);
    int nextCell = grid.indexOf(c)+1;

    if (nextCell < grid.size()) {
      if (!grid.get(thisCell).allFilms.contains(fileName)) {
        floodFill(nextCell, genres, fileName);
      }
    }
  }
}

IntList floodStack = new IntList();
void floodFill(int nxtCellIndex, String[] genres, String fileName) {
  floodStack.append(nxtCellIndex);

  while (floodStack.size() > 0) {
    fillCell(floodStack.get(0), genres, fileName);
    floodStack.remove(0);
  }
}

void fillCell(int cellInd, String[] genres, String fileName) {
  grid.get(cellInd).iterateGenreAndHeatAndFilmlists(genres, fileName);
  if (grid.get(cellInd).heat > high) high = grid.get(cellInd).heat;
  //74 cells to a row

  //Add top cell
  if (cellInd-74 >= 0 && 
    !grid.get(cellInd-74).allFilms.contains(fileName)) floodStack.append(cellInd-74);

  //Add right cell
  if (cellInd+1 <= grid.size() && 
    !grid.get(cellInd+1).allFilms.contains(fileName)) floodStack.append(cellInd+1);

  //Add bottotm cell
  if (cellInd-74 <= grid.size() && 
    !grid.get(cellInd+74).allFilms.contains(fileName)) floodStack.append(cellInd+74);

  //Add left cell
  if (cellInd-1 >= 0 && 
    !grid.get(cellInd-1).allFilms.contains(fileName)) floodStack.append(cellInd-1);
}

```

---

<div class="post-metadata">

**Author:** ![tribblesontoast](https://avatars.discourse-cdn.com/v4/letter/t/e99b99/32.png) [@tribblesontoast](https://discourse.processing.org/u/tribblesontoast)\
**Post date:** [November 15, 2021, 1:14am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/6 "2021-11-15T01:14:46Z")

</div>

I’ve also had a crack at the AABB method you shared.  
It’s allowed me to remove the lineRectIntersection check completely, but is is very very inefficient. I know you warned of that and I appreciate all you’ve shared.

It takes a while to loop through all the cells and do the AABB check, and when I added more than 1 film (that’s what I’m testing with) it takes forever as it’s looping through things far too much.

How can I make this faster?

```auto
void getNextFilm(int index) {
  filmTitle = filmData.getRow(int(index));
  fileName = filmTitle.getString("FileName");
  String str = filmTitle.getString("Genres");
  String[] genres = split(str, '|');

  for (int i = 0; i < genreNames[0].length; i++) {
    for (int j = 0; j < genres.length; j++) {
      if (genres[j].equals(genreNames[0][i])) {
        int v = int(genreNames[1][i]);
        genreNames[1][i] = str(v+1);
      }
    }
  }
  String selPointsString = filmTitle.getString("SelectionPoints");
  String[] tmpPoints = splitTokens(selPointsString, "[]|,");
  selPoints = new ArrayList<PVector>();
  for (int i = 0; i < tmpPoints.length; i += 3) {
    selPoints.add(new PVector(float(tmpPoints[i]), float(tmpPoints[i+1]), float(tmpPoints[i+2])));
  }

  leftMost = width;
  rightMost = 0;
  topMost = height;
  bottomMost = 0;

  for (int k = 0; k < selPoints.size(); k++) {
    if (selPoints.get(k).x < leftMost) leftMost = selPoints.get(k).x;
    if (selPoints.get(k).x > rightMost) rightMost = selPoints.get(k).x;
    if (selPoints.get(k).y > bottomMost) bottomMost = selPoints.get(k).y;
    if (selPoints.get(k).y < topMost) topMost = selPoints.get(k).y;
  }

  for (Cell c : grid) {
    float[] aabb = getAABB(selPoints);

    for (float y = aabb[1]; y < aabb[1] + aabb[3]; y++) {
      for (float x = aabb[0]; x < aabb[0] + aabb[2]; x++) {
        if (isPointInPoly(c.pos.x, c.pos.y, selPoints)) {          
          c.iterateGenreAndHeatAndFilmlists(genres, fileName);
          if (c.heat > high) high = c.heat;
        }
      }
    }
    println(grid.indexOf(c));
  }
}

float[] getAABB(ArrayList<PVector> pointsToBound) {
  float[] result;
  float minX = 10000000;
  float maxX = -10000000;
  float minY = 10000000;
  float maxY = -10000000;

  for (int i = 0; i < pointsToBound.size(); i++) {
    PVector pt = pointsToBound.get(i);
    minX = min(minX, pt.x);
    maxX = max(maxX, pt.x);
    minY = min(minY, pt.y);
    maxY = max(maxY, pt.y);
  }
  result = new float[]{minX, minY, maxX-minX, maxY-minY};
  return result;
}

//you can read more about this here
//https://stackoverflow.com/a/16391873
boolean isPointInPoly(float px, float py, ArrayList<PVector> pts) {
  int i, j;
  boolean c = false;
  for (i = 0, j = pts.size() - 1; i < pts.size(); j = i++) {
    if ((pts.get(i).y > py) != (pts.get(j).y > py) &&
      px < (pts.get(j).x - pts.get(i).x) * (py - pts.get(i).y) / (pts.get(j).y - pts.get(i).y) + pts.get(i).x)
    {
      c = !c;
    }
  }
  return c;
}

```

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [November 15, 2021, 5:21pm UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/7 "2021-11-15T17:21:52Z")

</div>

Hi @tribblesontoast

My pseudo is jb4x not hotfooted 😅

If you run into an infinite stack, my guess is that those lines of code:

```auto
grid.get(cellInd).iterateGenreAndHeatAndFilmlists(genres, fileName);
if (grid.get(cellInd).heat > high) high = grid.get(cellInd).heat;

```

are not toggling the following boolean:

```auto
grid.get(cellInd-74).allFilms.contains(fileName)

```

Also you made a tiny mistake for the bottom cells; instead of +74 you wrote -74.

---

<div class="post-metadata">

**Author:** ![tribblesontoast](https://avatars.discourse-cdn.com/v4/letter/t/e99b99/32.png) [@tribblesontoast](https://discourse.processing.org/u/tribblesontoast)\
**Post date:** [November 16, 2021, 1:36am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/8 "2021-11-16T01:36:46Z")

</div>

My most humble apologies jb4x,

You are right, the top cell check is never being triggered and I have no idea why.  
I have modified the fillCell method to the following:

I’m also including below the output from the console.

```auto
void fillCell(int cellInd, String[] genres, String fileName) {
  grid.get(cellInd).iterateGenreAndHeatAndFilmlists(genres, fileName);
  if (grid.get(cellInd).heat > high) high = grid.get(cellInd).heat;
  //74 cells to a row
  if (cellInd-74 >= 0) println(cellInd-74, cellInd, grid.get(cellInd-74).getAllFilms(), fileName, floodStack.size());

  //Add top cell
  if (cellInd-74 >= 0 && 
    !grid.get(cellInd-74).allFilms.contains(fileName)) {
    floodStack.append(cellInd-74);
  }
  //Add right cell
  if (cellInd+1 <= grid.size() && 
    !grid.get(cellInd+1).allFilms.contains(fileName)) {
    floodStack.append(cellInd+1);
  }
  //Add bottom cell
  if (cellInd+74 <= grid.size() && 
    !grid.get(cellInd+74).allFilms.contains(fileName)) {
    floodStack.append(cellInd+74);
  }
  //Add left cell
  if (cellInd-1 >= 0 && 
    !grid.get(cellInd-1).allFilms.contains(fileName)) {
    floodStack.append(cellInd-1);
  }
}

```

cellInd-74, cellInd, grid.get(cellInd-74).getAllFilms(), fileName, floodStack.size()

```auto
377 451 [Snakes on a Plane] Snakes on a Plane 9135
450 524 [Snakes on a Plane] Snakes on a Plane 9136
450 524 [Snakes on a Plane] Snakes on a Plane 9137
523 597 [Snakes on a Plane] Snakes on a Plane 9138
450 524 [Snakes on a Plane] Snakes on a Plane 9139
523 597 [Snakes on a Plane] Snakes on a Plane 9140
523 597 [Snakes on a Plane] Snakes on a Plane 9141
596 670 [Snakes on a Plane] Snakes on a Plane 9142
450 524 [Snakes on a Plane] Snakes on a Plane 9143
523 597 [Snakes on a Plane] Snakes on a Plane 9144
523 597 [Snakes on a Plane] Snakes on a Plane 9145
596 670 [Snakes on a Plane] Snakes on a Plane 9146
523 597 [Snakes on a Plane] Snakes on a Plane 9147
596 670 [Snakes on a Plane] Snakes on a Plane 9148
596 670 [Snakes on a Plane] Snakes on a Plane 9149
669 743 [Snakes on a Plane] Snakes on a Plane 9150
304 378 [Snakes on a Plane] Snakes on a Plane 9151
377 451 [Snakes on a Plane] Snakes on a Plane 9152
377 451 [Snakes on a Plane] Snakes on a Plane 9153
450 524 [Snakes on a Plane] Snakes on a Plane 9154
377 451 [Snakes on a Plane] Snakes on a Plane 9155
450 524 [Snakes on a Plane] Snakes on a Plane 9156
450 524 [Snakes on a Plane] Snakes on a Plane 9157
523 597 [Snakes on a Plane] Snakes on a Plane 9158
377 451 [Snakes on a Plane] Snakes on a Plane 9159
450 524 [Snakes on a Plane] Snakes on a Plane 9160
450 524 [Snakes on a Plane] Snakes on a Plane 9161
523 597 [Snakes on a Plane] Snakes on a Plane 9162
450 524 [Snakes on a Plane] Snakes on a Plane 9163
523 597 [Snakes on a Plane] Snakes on a Plane 9164

```

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [November 16, 2021, 7:26am UTC](https://discourse.processing.org/t/filling-grid-cells-inside-a-shape/33427/9 "2021-11-16T07:26:36Z")

</div>

I’m afraid your log is not of much help…

Some questions that might help you:

- Are you sure that `grid.get(idx).allFilms.contains(fileName)` is working properly and return true if the cell indeed contains the file `fileName`?
- Are you sure that `grid.get(idx).iterateGenreAndHeatAndFilmlists(genres, fileName)` add the file `fileName` to your grid cell.
- You are checking for a `fileName` file. Are all the cells of your border containing this specific file?

If one of those is failing then you will indeed run in an infinite loop.