I use a Flood Fill Algorithm to look if the 1s and 2s of a matrix are making a loop.
For example:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 2 0 0 0
0 0 0 0 0 2 2 1 0 0
0 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Will become:
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 2 0 0 0
0 0 0 0 0 2 2 3 0 0
0 0 0 3 3 3 0 3 0 0
0 0 0 3 0 0 3 3 0 0
0 0 0 3 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
I initialize the algorithm at a given point which is (2,7) and the the algorithm turns into 3s every 1 that is linked to the starting point. I wanted to also implement a digraph (using jgrapht), each 1 being a vertex, and having one edge being created between two 1s which are next to each other. So each time the algorithm turns a 1 into a 3, it makes both the 3 a vertex and creates an edge with the last spot filled.
Note: I use reactivision, so each marker detected is added to the matrix as a 1. Since I can't test right now with 10 markers, I added a matrix to the program.
Here is the part of my code doing this: [EDIT]: I pasted my whole code now since I can't find the error
import TUIO.*;
import java.util.*;
import java.util.List;
import java.util.Arrays;
import java.util.Scanner;
import java.io.*;
import org.joda.time.DateTime;
import org.jgrapht.alg.*;
import org.jgrapht.demo.*;
import java.net.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.alg.*;
TuioProcessing tuioClient;
// --------------------------------------------------------------
// Create matrix
static int[][] matrix = new int[10][10];
// Create Grid
int cols = 10, rows = 10;
int rectangleWidth = 100;
int rectangleHeight = 60;
// these are some helper variables which are used
// to create scalable graphical feedback
float cursor_size = 15;
float object_size = 60;
float table_size = 760;
float scale_factor = 1;
boolean verbose = false; // print console debug messages
boolean callback = true; // updates only after callbacks
// Variables to mesure time
long startTime = 0;
long time ;
// Variables to caracterise each ficudial
int x, y, k, l, iD;
String myType;
// Types of components: V: Vertical / H: Horizontal /ER: Elbow Right / EL: Elbow Left / LI: Left Intersection / VI: Vertical Intersection
// Their position in the list matches their iD
String [] fiducialsList = {
"R300", "R3OO", "R600", "R600", "V", "V", "H", "ER", "H", "ER", "EL", "EL", "R100", "R100", "R900", "R900", "EL", "V", "V", "ER", "H", "H", "Box", "LI", "VI"
};
//Create the directed graph
public static DirectedGraph<Point, DefaultEdge> directedGraph = new DefaultDirectedGraph<Point, DefaultEdge>(DefaultEdge.class);
public static Point firstPoint = new Point(2,7);
// --------------------------------------------------------------
ArrayList<Fiducial> activList = new ArrayList<Fiducial>();
public class Fiducial {
public float x;
public float y;
public int iD;
public String myType;
public Fiducial(float x, float y, int iD, String myType)
{
this.myType = myType;
this.iD = iD;
this.x = x;
this.y = y;
}
@Override
public String toString() {
return ("[iD="+iD+" x="+x+" y="+y +" type="+myType+"]");
}
}
// --------------------------------------------------------------
//Time measurement: every lapse of time spent by the user on a circuit is stored here
ArrayList <Time> timeSpent = new ArrayList <Time> ();
public class Time {
public long time ;
public Time (long time)
{
this.time = time;
}
@Override
public String toString () {
return ("time spent on this circuit:" + time );
}
}
// --------------------------------------------------------------
void setup() {
size(1000, 600);
noCursor();
noStroke();
fill(0);
directedGraph.addVertex(new Point (2,7));
// periodic updates
if (!callback) {
frameRate(60); //<>//
loop();
} else noLoop(); // or callback updates
//int[][] array = new int[10][10];
//System.out.println(Arrays.deepToString(array));
tuioClient = new TuioProcessing(this);
System.out.println(Arrays.deepToString(matrix));
startTime = System.nanoTime();
System.out.println("#vertex: "+ directedGraph.vertexSet());
}
// --------------------------------------------------------------
void draw() {
// Begin loop for columns
for ( k = 0; k < cols; k++) {
// Begin loop for rows
for ( l = 0; l < rows; l++) {
fill(255);
stroke(0);
rect(k*rectangleWidth, l*rectangleHeight, rectangleWidth, rectangleHeight);
}
}
matrix [1][5]= 2;
matrix [1][6]= 2;
matrix [2][5]= 2;
matrix [2][6]= 2;
matrix [3][5]=1;
matrix [2][7]=1;
matrix [4][6]=1;
matrix [3][5]=1;
matrix [4][6]=1;
matrix [4][7]=0;
matrix [3][4]=1;
matrix [3][3]=1;
matrix [3][7]=1;
matrix [3][7]=1;
matrix [3][7]=1;
matrix [3][7]=1;
matrix [4][3]=1;
matrix [5][3]=1;
matrix [5][4]=1;
matrix [5][5]=1;
matrix [5][6]=1;
matrix [6][6]=1;
matrix [7][6]=1;
matrix [3][2]=1;
matrix [3][1]=1;
matrix [3][0]=1;
// Print Matrix
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
// This part detects the fiducial markers
float obj_size = object_size*scale_factor;
float cur_size = cursor_size*scale_factor;
ArrayList<TuioObject> tuioObjectList = tuioClient.getTuioObjectList();
for (int i=0; i<tuioObjectList.size (); i++) {
//System.out.println("#vertex: "+ directedGraph.vertexSet());
TuioObject tobj= tuioObjectList.get(i);
stroke(0);
fill(0, 0, 0);
pushMatrix();
translate(tobj.getScreenX(width), tobj.getScreenY(height));
rotate(tobj.getAngle());
rect(-80, -40, 80, 40);
popMatrix();
fill(255);
x = round(10*tobj.getX ());
y = round(10*tobj.getY ());
iD = tobj.getSymbolID();
// directedGraph.addVertex(new Point(x,y));
int taille = fiducialsList.length;
for (int o = 0; o<taille; o++) {
if (iD == o) {
myType = fiducialsList [o];
}
}
activList.add(new Fiducial (x, y, iD, myType));
matrix [x][y] = 1 ;
circuitState ();
for (int p = 0; p < 10; p++) {
for (int r = 0; r < 10; r++) {
System.out.print(matrix[p][r] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
}
System.out.println("#vertex: "+ directedGraph.vertexSet());
//Re-initialize matrix
for (int[] row : matrix)
Arrays.fill(row, 0);
}
// --------------------------------------------------------------
void circuitState () {
if ( matrix [2][7]==1 ) {
FloodFill.resolution(args);
if (matrix [3][5]== 3) {
System.out.println("Fermé");
} else {
long estimatedTime = System.nanoTime() - startTime;
timeSpent.add(new Time (time));
System.out.println(" Ouvert " + "took" + estimatedTime);
}
}
}
// --------------------------------------------------------------
// Implementation of the Flood Fill Algorithm to detect if circuit is closed or not
public static class FloodFill {
public static void resolution(String[] args) {
System.out.println("Found loop: "+checkIfPositionIsInLoop(matrix, 2, 7, 3));
//result
System.out.println("-------------------");
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.print("\n");
}
System.out.print("\n");
}
private static Direction direction;
public static boolean checkIfPositionIsInLoop(int[][] matrix, int x, int y, int fillValue) {
int targetX = x;
int targetY = y;
return fillReachesTargetPosition(matrix, x, y, targetX, targetY, fillValue, Direction.LEFT );
}
private static boolean fillReachesTargetPosition(int[][] matrix, int x, int y, int targetX, int targetY, int fillValue, Direction forbiddenDirection) {
if (x>=matrix.length)
return false;
if (y>=matrix[x].length)
return false;
int originValue=matrix[x][y];
matrix[x][y]=fillValue;
int xToFillNext;
int yToFillNext;
boolean fillingReachedTargetPosition = false;
// Up
xToFillNext = x-1;
yToFillNext = y;
if (xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.UP)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
return true;
} else if (xToFillNext>=0 && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.UP)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue, Direction.DOWN );
if (fillingReachedTargetPosition) {
return true;
}
}
// Right
xToFillNext = x;
yToFillNext = y+1;
if (xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.RIGHT)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
return true;
} else if (yToFillNext<matrix[xToFillNext].length && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.RIGHT)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue, Direction.LEFT );
if (fillingReachedTargetPosition) {
return true;
}
}
// Down
xToFillNext = x+1;
yToFillNext = y;
if (xToFillNext==targetX && yToFillNext==targetY && !forbiddenDirection.equals(Direction.DOWN)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
return true;
} else if (xToFillNext<matrix.length && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.DOWN)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue, Direction.UP );
if (fillingReachedTargetPosition) {
return true;
}
}
// Left
xToFillNext = x;
yToFillNext = y-1;
if (xToFillNext==targetX && yToFillNext==targetY && forbiddenDirection.equals(Direction.RIGHT)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
return true;
} else if (yToFillNext>=0 && originValue==matrix[xToFillNext][yToFillNext] && !forbiddenDirection.equals(Direction.LEFT)) {
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));
fillingReachedTargetPosition =
fillReachesTargetPosition(matrix, xToFillNext, yToFillNext, targetX, targetY, fillValue, Direction.RIGHT );
if (fillingReachedTargetPosition) {
return true;
}
}
return false;
}
}
// --------------------------------------------------------------
public static class DirectedGraphDemo {
public static void graph(String args[]) {
// constructs a directed graph with the specified vertices and edges
directedGraph.addVertex(firstPoint);
// prints the strongly connected components
System.out.println("Strongly connected components:");
for (int i = 0; i < stronglyConnectedSubgraphs.size(); i++) {
System.out.println(stronglyConnectedSubgraphs.get(i));
}
System.out.println();
}
}
// --------------------------------------------------------------
ArrayList<Point> pointList = new ArrayList<Point>();
public static class Point {
public int x;
public int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
@Override
public String toString() {
return ("[x="+x+" y="+y+"]");
}
}
// --------------------------------------------------------------
// called at the end of each TUIO frame
void refresh(TuioTime frameTime) {
if (verbose) println("frame #"+frameTime.getFrameID()+" ("+frameTime.getTotalMilliseconds()+")");
if (callback) redraw();
}
However, when I run it, I get an error "illegalArgumentException: no such vertex in graph [x=2 y=7]" which is the starting point. So I tried to define this point as vertex by doing:
public static Point firstPoint = new Point(2,7);
and then:
directedGraph.addVertex(new Point (2,7));
but it still won't work I get the same error, always at this line:
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext)); but at different places in the Flood Fill algorithm depending on where Reactivision detects the marker (so it is either in the UP, DOWN, LEFT, or RIGHT section of the algorithm).
I'm completely stuck. I added a print statement so each time the draw method is executed, it returns the vertices of the graph and [2,7] is there ... I can't figure it out, could someone help me ?
Found my error: I had to add:
Point myPoint = new Point(x, y);
Point myNextPoint = new Point(xToFillNext, yToFillNext);
directedGraph.addVertex(myPoint);
directedGraph.addVertex(myNextPoint);
directedGraph.addEdge(myPoint, myNextPoint);
In every section of my Flood Fill algorithm instead of :
directedGraph.addVertex(new Point (x,y));
directedGraph.addVertex(new Point(xToFillNext,yToFillNext));
directedGraph.addEdge(new Point (x,y),new Point(xToFillNext,yToFillNext));