# \[SOLVED\] Circle around a pixel

**URL:** <https://discourse.processing.org/t/solved-circle-around-a-pixel/1071>\
**Category:** Coding Questions\
**Created:** [June 19, 2018, 9:08am UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071 "2018-06-19T09:08:04Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![MxFxM](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MxFxM](https://discourse.processing.org/u/MxFxM)\
**Post date:** [June 19, 2018, 9:08am UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/1 "2018-06-19T09:08:04Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![cumulus](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/cumulus/32/451_2.png) [@cumulus](https://discourse.processing.org/u/cumulus)\
**Post date:** [June 19, 2018, 9:20am UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/2 "2018-06-19T09:20:33Z")

</div>

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.

> **[Distance from a point to a line](https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line)**
>
> The distance (or perpendicular distance) from a point to a line is the shortest distance from a fixed point to any point on a fixed infinite line in Euclidean geometry. It is the length of the line segment which joins the point to the line and is perpendicular to the line. The formula for calculating it can be derived and expressed in several ways.
> Knowing the shortest distance from a point to a line can be useful in various situations—for example, finding the shortest distance to reach a road, ...

---

<div class="post-metadata">

**Author:** ![MxFxM](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MxFxM](https://discourse.processing.org/u/MxFxM)\
**Post date:** [June 19, 2018, 9:26am UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/3 "2018-06-19T09:26:21Z")

</div>

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:

 ![test5](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/1X/01028c77fcedec62ecf2f4ac068ac2498af432b5.png)

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.

---

<div class="post-metadata">

**Author:** ![MxFxM](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MxFxM](https://discourse.processing.org/u/MxFxM)\
**Post date:** [June 20, 2018, 7:06am UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/4 "2018-06-20T07:06:50Z")

</div>

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 😃

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [June 21, 2018, 4:22pm UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/5 "2018-06-21T16:22:10Z")

</div>

> [@MxFxM](#):
>
> 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.

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:

1. Apply the point-line distance equation to the segment.
2. 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](https://math.stackexchange.com/a/322836/396141)
3. 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.

---

<div class="post-metadata">

**Author:** ![MxFxM](https://avatars.discourse-cdn.com/v4/letter/m/71e660/32.png) [@MxFxM](https://discourse.processing.org/u/MxFxM)\
**Post date:** [June 22, 2018, 5:09am UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/6 "2018-06-22T05:09:56Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [June 22, 2018, 7:11pm UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/7 "2018-06-22T19:11:12Z")

</div>

Yes, whatever works for you!

> [@MxFxM](#):
>
> And the rectangle-method runs in 20s where as the circle-method need about 40min

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.

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [June 25, 2018, 10:49pm UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/8 "2018-06-25T22:49:16Z")

</div>

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.

- [get() / Reference / Processing.org](https://processing.org/reference/PImage_get_.html)
- [pixels[] / Reference / Processing.org](https://processing.org/reference/pixels.html)

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [November 22, 2019, 11:34pm UTC](https://discourse.processing.org/t/solved-circle-around-a-pixel/1071/9 "2019-11-22T23:34:27Z")

</div>

> [@jeremydouglass](#):
>
> Given a point to compare to the segmented line;  
> For each segment:
> 
> 1. Apply the point-line distance equation to the segment.

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

```auto
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.

```auto
/**
 * 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](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/2/24cf707bd38c7c72d7c420694f279022d286e565.png)