Calculating distance between point and black pixel of an image

Programming Questions

gera

Calculating distance between point and black pixel of an image

in Programming Questions • 1 year ago

Hi!!

Im working in a little project and I need to know the distance between some point (x,y) and the first black pixel of an image in a given direction.

Im trying to simulate a maze solving robot. The point represents the robot, and the image will be the maze (black walls). The robot needs to know how far are the walls in the front and the sides.

I attach an image to illustrate this:

So, what I need is to know the lenght of the red lines.

I hope you can help me. Thank you!!

Replies(5)

tfguy44

Re: Calculating distance between point and black pixel of an image

1 year ago

If the robot can only make 45 degree angle turns, this would be simple. But if it can be pointing in any direction, this is quite a bit more difficult.

It might be helpful to know more about these walls. Can we assume they have a minimal thickness? How is their position determined?

Anyway, what you'd do is work out a tiny x and y step you'd need to make to follow along each red line, then make small steps, approximating that position to a specific pixel, which you would then test for its color.

gera

Re: Calculating distance between point and black pixel of an image

1 year ago

The robot can point in any direction. I wanted to use an image as the maze so I can edit it.

Look, here is an example of what I want to do:

http://www.youtube.com/watch?v=fRIOyrGe5b8

And here is an example of the distance between the robot and the wall:

http://www.youtube.com/watch?v=0Str0Rdkxxo&feature=related

I thought doing some kind of "scan" from the point to the wall to measure the distance, but thats not an efficient way.

Thank you for your answer!! :)

tfguy44

Re: Calculating distance between point and black pixel of an image

1 year ago

Ah ha! Well now, that second video you posted sure is interesting. Notice that the walls in it are CONSIDERABLY thicker than simple lines - they're basically AREAS. Also notice that you don't need the EXACT distance to a wall - just a rough estimate. This makes things considerable easier for you (to the point where it's a manageable problem!).

So, here you go! Learn for this example and you should be able to get your feeler arms working in no time!

float xStep = 0;
float yStep = 0;
float angle = 0;
int checkStep = 5;
void setup() {
size(500, 500);
ellipseMode(CENTER);
rectMode(CENTER);
}
void draw() {
background(128);
fill(255, 255, 0);
ellipse( width/2.0, height/2.0, 300, 300);
rect(width/2.0, height/6.0, 20, 80);
if (mousePressed) {
angle -=0.1;
angle%=TWO_PI;
}
xStep = cos(angle);
yStep = sin(angle);
fill(0, 255, 0);
for ( int i = 0; i <= 250; i+=checkStep) {
float testX = mouseX + i * xStep;
float testY = mouseY + i * yStep;
if ( get(int(testX), int(testY)) == color(255, 255, 0) ) {
fill( 255, 0, 0);
}
ellipse( testX, testY, 5, 5);
}
}

kritzikra..

Re: Calculating distance between point and black pixel of an image

1 year ago

--- edit: fixed a bug in my code --

hey!

i love tfguy's solution, i think it's already relly good, but i couldn't help but attempt it too...

i've used the bresenham algorithm, that is the algorithm used to draw lines on a computer.

so basically i'm following the test-ray while it is being drawn,

and soon as it would overwrite a black pixel i made the algorithm cancel and return the coordinates.

here's some code:

float angle = PI/2;
int rayLength = 300;
int rayColor = color( 255, 0, 0 );
boolean drawRays = true;
int N = 30;
PVector wallPoints[] = new PVector[N];
void setup() {
size(500, 500);
ellipseMode(CENTER);
rectMode(CENTER);
}
void draw() {
background(128);
fill(255, 255, 0);
stroke( 0 );
strokeWeight( 2 );
ellipse( width/2.0, height/2.0, 300, 300);
fill( 0, 255, 255 );
ellipse( width/2.0, height/2.0+200, 300, 300);
rect(width/2.0, height/6.0, 20, 80);
if( mousePressed ){
angle -=0.01;
angle%=TWO_PI;
}
// how many intersections do we want to test?
// TO MAKE THINGS MORE FANCY:
// let's do the line checking a few times in a loop
for( int i = 0; i < N; i++ ){
float alpha = angle + i*TWO_PI/N;
// draw a line from the current mouse coordinates with some direction "alpha"
wallPoints[i] = findWall( mouseX, mouseY, (int)(mouseX+rayLength*cos(alpha)), (int)(mouseY+rayLength*sin(alpha)) );
}
// draw them later, otherwise we might draw over the edge and then we
// can't detect it anymore
for( int i = 0; i < N; i++ ){
if( wallPoints[i] != null ){
noFill();
stroke( 0, 255, 0 );
ellipse( wallPoints[i].x, wallPoints[i].y, 10, 10 );
// this would be the distance:
// println( "Distance is currently: " + wallPoints[i].dist( new PVector( mouseX, mouseY ) ) );
}
}
}
// bresenham java implementation adapted from the "drawLine" method from
// http://onyx.boisestate.edu/~tcole/cs498/spr04/ammeraal/Bresenham.java
// this attempty to draw a line between two points.
// as soon as it hits a black pixel it stops and returns the coordinates.
PVector findWall(int xP, int yP, int xQ, int yQ)
{ int x = xP, y = yP, D = 0, HX = xQ - xP, HY = yQ - yP,
c, M, xInc = 1, yInc = 1;
// do we start on a wall?
if( get( xP, yP ) == color( 0, 0, 0 ) ) return new PVector( xP, yP );
if (HX < 0){xInc = -1; HX = -HX;}
if (HY < 0){yInc = -1; HY = -HY;}
if (HY <= HX)
{ c = 2 * HX; M = 2 * HY;
for (;;)
{
if( (xP!=x || yP!=y) &&get( x, y ) == color( 0, 0, 0 ) ) return new PVector( x, y );
// disable this if you don't want to draw the trace
if( drawRays ) set( x, y, rayColor );
if (x == xQ) break;
x += xInc;
D += M;
if (D > HX){y += yInc; D -= c;}
}
}
else
{ c = 2 * HY; M = 2 * HX;
for (;;)
{
if( (xP!=x || yP!=y) &&get( x, y ) == color( 0, 0, 0 ) ) return new PVector( x, y );
// disable if you don't want to draw the trace
if( drawRays ) set(x, y, rayColor);
if (y == yQ) break;
y += yInc;
D += M;
if (D > HY){x += xInc; D -= c;}
}
}
// nothing found?
return null;
}

btw:

you'll notice this code has two problems:

1. your wall needs to be at least 2px thick, otherwise the algorithm might "slip by" a wall

2. as soon as you start drawing where the ray hits you might end up painting over the wall,

and the next wall check has found a way to slip by.

both should be quite easy to work around,

the first by drawing a 2px wall, the second by simply not drawing any results until you've made

all your wall checks ...

good luck with your project!

best, hansi.

gera

Re: Calculating distance between point and black pixel of an image

1 year ago

Wow, that was clever! ;) its exactly what I need! You are awesome guys, thanks a lot!!

Top Reply