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 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:
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;
}
}
}
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:
Shape filled but so are the external areas…
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?
//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;
}
}
}
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):
// 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);
}
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. i know it’s p5js but it should be easy enough to convert.
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.
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);
}
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?
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;
}
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
