[SOLVED] Circle around a pixel

MxFxM · June 19, 2018, 9:08am

Hello everbody,

I’m currently working on a project where I need to find a specific distance between a point and a line.
To do that, I draw the line in green and start scanning each pixel around the point. This can take however long it wants to, I don’t need this part of the code to run fast. However I’m currently doing this by going in a rectangular fashion around the starting point:

    int d1 = 1;
    int moving_x = floor(supportpoints[i][2]);
    int moving_y = floor(supportpoints[i][3]);
    int change = +1;
    color c = export_graphic.get(moving_x, moving_y);
    while ((c >> 8 & 0xFF) - 100 != supportpoints[i][4]) {
      for (int count = 0; count < d1; count++) {
        moving_x = moving_x + change;
        c = export_graphic.get(moving_x, moving_y);
        if ((c >> 8 & 0xFF) - 100 == supportpoints[i][4]) {
          break;
        }
      }
      if ((c >> 8 & 0xFF) - 100 == supportpoints[i][4]) {
        break;
      }
      for (int count = 0; count < d1; count++) {
        moving_y = moving_y + change;
        c = export_graphic.get(moving_x, moving_y);
        if ((c >> 8 & 0xFF) - 100 == supportpoints[i][4]) {
          break;
        }
      }
      if ((c >> 8 & 0xFF) - 100 == supportpoints[i][4]) {
        break;
      }
      d1 = d1 + 1;
      change = -change;
    }
    d1 = floor(dist(floor(supportpoints[i][2]), floor(supportpoints[i][3]), moving_x, moving_y));

But the corners will relatively fast be way further out than the sides compared to a circle with equal distance to the surcomference.
I thought about locating the checked pixel useing sin and cos and an angle and increasing the distance for each revolution, however it’s (for long distances) not garanteed to check each pixel on the screen and since the line I’m looking for is only 1 pixel in width it might be missed.

TLDR: Looking for the closest colored pixel in a circle around a point

Does anybody have an working algorithm or any ideas for this?

Greetings Max

PS: I knnow the flooring at the end is not nice but I will look in to that once the distnace thing is done.

cumulus · June 19, 2018, 9:20am

Is the line mathematically straight and do you happen to know its coordinates?
if so there are equations you can use that will do this very efficiently.

MxFxM · June 19, 2018, 9:26am

No the line can have any angle that’s why I can’t just go in x / y direction.
I know about the ways how to calculate the distance between a point and a line. The shortest distance is perpendicular to the line. But the line im looking at has many corners.
Look at this picture:

I want to calculate the shortest distance for each crosspoint of the blue lines to he two closest green lines of different green-level. I already got that sorted out, just the corner-problem remains.

As I said the green lines may vary.

MxFxM · June 20, 2018, 7:06am

Hi, its me again.
I found a solution im ok with:
I draw an ellipse() with scaling size and then I compare the color at the edge of the ellipse.
The way the ellipse is drawn in noSmooth() mode it covers almost every pixel so there is only minimal error.

See you in another topic

jeremydouglass · June 21, 2018, 4:22pm

Glad you found a solution that works for you!

If you are trying to find the minimum distance between a known point x,y and a series of line segments (x1,y1,x2,y2,x3,y3…) then there are geometric algorithms for that which do not require approximation or pixel fiddling. This presumes that you know the list of coordinates that drew the line in the first place.

Given a point to compare to the segmented line;
For each segment:

Apply the point-line distance equation to the segment.
Project back – see “How to make this an algorithm” from geometry - Determing the distance from a line segment to a point in 3-space - Mathematics Stack Exchange
If the distance is less than the previous minimum distance, the closest point on the segment is the new closest point on the segmented line.

Now you have the closest point on the segmented line.

MxFxM · June 22, 2018, 5:09am

Thank you for that idea.
The problem was that I didn’t know the endpoints of the line-segment.
…
Ok now that I think about it I might have known them…

But that’s not the point. The thing is that at the end I’m rounding the numbers anyway so even when I ran a calculation with he real circle-shape the numbers where 1% off from my rectanglular approximation at worst.
(And the rectangle-method runs in 20s where as the circle-method need about 40min )

So for now I’m glad it works and when there is time left at the end of the project I will implement your soluion.

jeremydouglass · June 22, 2018, 7:11pm

Yes, whatever works for you!

Hmm. If your solution is slow, all the more reason to revisit it at some point in the future – without knowing the extent of your data, the size of your images, or the number of segments in your lines, I would still guess that if repeatedly sampling pixels with get is running in ~20s, computing the mathematically solution will (probably!) run in ~0 seconds.

jeremydouglass · June 25, 2018, 10:49pm

P.S. get() is slow compared to using pixels[]. I see that you are already using bitshifting for color access, but if you want a quick speedup without changing your code approach, change your get calls – see the reference:

Getting the color of a single pixel with get(x, y) is easy, but not as fast as grabbing the data directly from pixels. The equivalent statement to get(x, y) using pixels is pixels[y*width+x]. See the reference for pixels for more information.

jeremydouglass · November 22, 2019, 11:34pm

Revisiting the question of finding the closest point on a path of line segments: here is a geometric solution, which runs in realtime.

PVector closestPointOnLineSeg( float px, float py, float x1, float y1, float x2, float y2) {
  PVector result = new PVector();
  float dx = x2 - x1; 
  float dy = y2 - y1; 
  float d = sqrt( dx*dx + dy*dy ); 
  float ca = dx/d; // cosine
  float sa = dy/d; // sine
  float mx = (-x1+px)*ca + (-y1+py)*sa;
  if ( mx <= 0 ) {
    result.x = x1; 
    result.y = y1;
  } else if ( mx >= d ) {
    result.x = x2; 
    result.y = y2;
  } else {
    result.x = x1 + mx*ca; 
    result.y = y1 + mx*sa;
  }
  return result;
}

…and here is an interactive version. It marks the mouse location, closest point on each segment, and the closest point overall.

/**
 * PointLinesClosestPoints
 * 2019-08 Jeremy Douglass
 * Given a pointer and a path made out of points, find the
 * closest point on each segment, then the closest point
 * on the whole path.
 * See: https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/2
 */ 
PVector[] pathpts;
PVector pointer;

void setup() {
  size(400, 400);
  pathpts=randomPoints(10, 0, 0, 400, 400);
  pointer=new PVector(0,0);
}

void draw() {
  background(255);

  pointer.set(mouseX, mouseY);
  PVector[] hits=new PVector[pathpts.length-1];
  float minDist=MAX_FLOAT;
  int minIndex=0;
  for(int i=0; i<pathpts.length-1; i++){
    // draw path
    line(pathpts[i].x, pathpts[i].y, pathpts[i+1].x, pathpts[i+1].y);
    // find hit
    hits[i]=closestPointOnLineSeg(pointer.x, pointer.y, pathpts[i].x, pathpts[i].y, pathpts[i+1].x, pathpts[i+1].y);
    // is this hit the closest one so far?
    float dist=hits[i].dist(pointer);
    if(dist<minDist){
      minDist=dist;
      minIndex=i;
    }
  }
  // draw hits
  fill(160);
  for(int i=0; i<hits.length; i++){
    ellipse(hits[i].x, hits[i].y, 5, 5);
  }
  
  // draw closest hit
  fill(255,0,0);
  ellipse(hits[minIndex].x, hits[minIndex].y, 12, 12);
  
  // draw pointer
  fill(0,0,255);
  ellipse(pointer.x, pointer.y, 10, 10);
  fill(0);
  text(int(minDist), pointer.x+10, pointer.y);
}

PVector[] randomPoints(int count, float xmin, float ymin, float xmax, float ymax) {
  PVector[] result = new PVector[count];
  for (int i=0; i<count; i++) {
    result[i]=new PVector(random(xmin, xmax), random(ymin, ymax));
  }
  return result;
}

PVector closestPointOnLineSeg( float px, float py, float x1, float y1, float x2, float y2) {
  PVector result = new PVector();
  float dx = x2 - x1; 
  float dy = y2 - y1; 
  float d = sqrt( dx*dx + dy*dy ); 
  float ca = dx/d; // cosine
  float sa = dy/d; // sine
  float mx = (-x1+px)*ca + (-y1+py)*sa;
  if ( mx <= 0 ) {
    result.x = x1; 
    result.y = y1;
  } else if ( mx >= d ) {
    result.x = x2; 
    result.y = y2;
  } else {
    result.x = x1 + mx*ca; 
    result.y = y1 + mx*sa;
  }
  return result;
}

float pointLineDistance(float px, float py, float x1, float y1, float x2, float y2) {
  PVector result = closestPointOnLineSeg( px, py, x1, y1, x2, y2);
  float dx2 = px - result.x; 
  float dy2 = py - result.y; 
  return sqrt( dx2*dx2 + dy2*dy2 );
}

void mouseClicked(){
  pathpts=randomPoints(10, 0, 0, 400, 400);
}

void keyReleased(){
  pathpts=randomPoints(10, 0, 0, 400, 400);
}

PointLinesClosestPoints

Topic		Replies	Views
How to make a program that works by coloring each pixel by distance to another? Coding Questions	12	828	October 23, 2018
Tracing a point on a moving circle Coding Questions	1	747	February 4, 2020
Grab Pixels Around Edges of an Irregular Image Shape Coding Questions	4	515	May 3, 2020
Programming advice (spiral from point to point) Coding Questions	16	520	November 27, 2022
Circle grows on left side of screen, not right Coding Questions	6	608	January 7, 2019

[SOLVED] Circle around a pixel

Related topics