How to find the coordinates of a bitmap shape

[paulstgeorge]

I have a sketch that divides a rectangle into three cells (picture 1). Everything is working as it should, but now I want to know the xy coordinates of the start and end of each border/edge. To show what I mean, I have marked the four points with grey ellipses (picture 2).

I need some help, please, to choose the right approach to solving this problem.

[glv]

Hello @paulstgeorge,

@paulstgeorge

I want to know the xy coordinates of the start and end of each border/edge

I would start here:

Images and Pixels

This example (in tutorial) may be a good place to start:
http://learningprocessing.com/examples/chp15/example-15-13-Convolution

You could modify the convolution function to check the pixels in a matrix for colors and if they are different you will have a point (these will be adjacent pixels and not an exact point).

You may have to consider ranges in your checks if the colors are not homogenous. You can also check for brightness, saturation and hue and ranges for those.

Maybe zoom in to see what a transition looks like and then consider what to check for:

Issue when rendering small rectangles

Hello, A very simple pixel viewer that I use to zoom in on sketch. Try different renderers, smooth() values, etc. I even tried odd and even. No pun intended! Some code for you to experiment with: // Pixel Viewer // v1.0.0 // GLV 2022-08-06 PImage img; boolean toggle; int oddeven, count, choice; void setup() { //size(650, 600); size(650, 600, P2D); //size(650, 600, P3D); background(255); //smooth(4); // Default is 2 noSmooth(); //strokeWeight(1); } …

An example with mouse movement:

PImage img;
int count;

void setup()
  {
  size(651, 477);  //Image size
  img = loadImage( "c5d59a8653f86bbf9bf8daa834e885ae4e998ba5.png" );
  println(img.width, img.height);
  mouseX = 1;
  mouseY = 1;
  }

void draw() 
  {
  image(img, 0, 0);

  //loadPixels();

  // Each pixel location (x,y) gets passed into a function called convolution()
  // The convolution() function returns true if adjacent pixels different.
  boolean b = convolution(mouseX, mouseY); 
  if (b)
    println(b);

  //updatePixels();
  }

boolean convolution(int x, int y) 
  {
  int xc, yc, loc;
  boolean b;
  //println(x, y);
  
  xc = x;
  yc = y;
  loc = xc + img.width*yc;
  int c0 = img.pixels[loc];
 
  xc = x+10; // Adjacent steps not detected well with coarse mouse movements! Made it 10 for testing with mouse!
  yc = y+0;
  loc = xc + img.width*yc;
  int c1 = img.pixels[loc];
  
  // Only checking c0 and c1, 2 adjacent pixels as mouse moves left to right
  if (c0 != c1)
    {
    println(count, hex(c0), hex(c1));
    b = true;
    count++;
    }
  else 
    b = false;      
  return b; 
  }

That above was just my first pass at this; move mouse slowly left to right along x-axis.

I did something similar scanning the pixel array without mouse.
Borders are simple.
Finding that middle point a bit more challenging.

@paulstgeorge

I have a sketch that divides a rectangle into three cells

Since you are generating this you should have the information available to get these points. Just a thought.

:)

[paulstgeorge]

Convolution looks like the way to go, thank you! I will report back.

@glv

Since you are generating this you should have the information available to get these points. Just a thought.

If only. The three cells are a Voronoi diagram. I only know the location of the three ‘seeds’.

[micuat]

I’m a bit confused, if you have the seeds can’t you calculate the edges?

Delaunay triangulation | Relationship with the Voronoi diagram

[paulstgeorge]

Perhaps @micuat , but…

In this image, I have marked the locations of the three seeds. The borders of the red and orange cells are where you would expect them to be: equidistant from the red and orange seeds and perpendicular to the line that joins the red and orange seeds. Likewise with the border between orange and blue.
How would you find the border between the red and blue cells???

[micuat]

for example using mesh library: Mesh – A Processing Library by Lee Byron

I couldn’t find an example sketch so I adapted their snippet on the website

import megamu.mesh.*;

Voronoi myVoronoi;
float[][] points;

void setup() {
  size(400, 400);
  points = new float[3][2];

  points[0][0] = 120; // first point, x
  points[0][1] = 230; // first point, y
  points[1][0] = 150; // second point, x
  points[1][1] = 105; // second point, y
  points[2][0] = 320; // third point, x
  points[2][1] = 113; // third point, y
  
  myVoronoi = new Voronoi( points );
  
  noLoop();
}

void draw() {
  float[][] myEdges = myVoronoi.getEdges();
  
  for(int i=0; i<points.length; i++) {
    circle(points[i][0], points[i][1], 10);
  }

  for(int i=0; i<myEdges.length; i++)
  {
    float startX = myEdges[i][0];
    float startY = myEdges[i][1];
    float endX = myEdges[i][2];
    float endY = myEdges[i][3];
    line( startX, startY, endX, endY );
  }
}

[glv]

@paulstgeorge

How would you find the border between the red and blue cells???

You can get the equation to each of the known lines; it would be 90 deg to the intersecting line (connecting two seeds) and you a point on the line (point of intersection):

Midpoint

Find the intersection between the lines:

Line–line intersection

If I did not have to go to work I would do this.
Give it a try!

Math is fun!

@paulstgeorge

Convolution looks like the way to go, thank you! I will report back

I strayed away from this in the end to simply scan pixels and the then examine them.
I should rename the “convolution” function in my example to “examine”.
If you can understand that example and the others it get easy to examine pixels.
It is a bit brute force but works great for images.
I wrote some code once to follow a line in an image and stay perpendicular (mall vehicle I think) to it and the the Images and Pixels tutorial was invaluable!

Update:
Woops! From some of the Voronoi diagrams I am seeing the above does not apply!
I still had fun doing the math and will certainly explore this further!

Delaunay triangulation - Wikipedia

:)

[Chrisir]

@paulstgeorge

that divides a rectangle into three cells

How do you draw this in the first place?

[paulstgeorge]

@glv
I combined three of your suggestions into a kind of pencil. I just press x to mark the spot (please see below).
I scale the image 200% so I can get the accuracy between pixels. I add margins so I can get the points that are on the edges of the image.
It works, but now I will look at the other approaches.
Thanks,
Paul

PImage img;
float margin = 20;


void setup()
{
  size(1228, 880);  //Image size
  noFill();
  img = loadImage("grid_193645017_200.png");
  image(img, 20, 20);
}

void draw()
{
}


// press key to mark the spot
void keyPressed() {
  if ((key == 'X') || (key == 'x')) {

    //mark the spot
    ellipse(mouseX, mouseY, 16, 16);
    println(mouseX - margin, mouseY - margin);
  } else if ((key == 'C') || (key == 'c')) {


    //mark the shared spot
    ellipse(mouseX, mouseY, 16, 16);
    println("C:", mouseX - margin, mouseY - margin);
  }
}

// I only need special attention if the point is shared

[paulstgeorge]

@Chrisir
I wrote my code from scratch because I wanted to understand each step, but the solution offered by @micuat (thanks!) is far easier and includes the edges!

[paulstgeorge]

@micuit

Perhaps I have misunderstood the mesh library, but…
When I draw the edges of the regions nothing appears along the edge of the stage.
When I try to plonk a circle at the end of an edge, it doesn’t appear because it is thousands of pixels outside the visible stage.

So, it seems to me that the ends of the border lines are way outside the canvas.
This considerably diminishes the usefulness of this library. Before I write it off, can you please confirm or tell me I am wrong?

[ProcessingOrg]

Hello @paulstgeorge ! It looks like you forgot to include a code snippet. Sharing your code helps us understand the issue better and provide more useful advice. Please update your post with a minimal sketch that shows your approach. Thank you!

[glv]

Hello @paulstgeorge,

I managed to do it with some math and PVectors!
This was mostly an exercise to work my brain.
Area on right was workspace to see individual PVectors

That last point in red was calculated!

I started with these seeds:

  a = new PVector(38.0, 609.0);
  b = new PVector(268.0, 634.0);
  c = new PVector(763.0, 178.0)

Steps:

• 2 midpoints
• PVectors from midpoints at 90° to line joining Voronoi seeds
• angleBetween() / Reference / Processing.org to get angles
• cosine law to get length of line
• more PVectors to get final point
• Voila!

Code is not elegant.

@paulstgeorge

I wrote my code from scratch because I wanted to understand each step

I do that all the time!
I do glean insight from other works but only after I thought it through and worked it all out.
It works the brain and I am a better programmer for it.

Note:
cursor() / Reference / Processing.org < I found it useful to use the CROSS cursor on my end to get the seed points in your code.

:)

[paulstgeorge]

@glv
That’s great.

I had done something very similar:

lines that join the seed locations

rotate 90° (two lines perpendicular to the seed to seed lines)

find location of where these two perpendicular lines intersect

BUT and it is a big BUT

the other point needed for the border between red and blue is much more difficult. As we can see, it does not bisect the external angle.

I have changed the cursor in the Pencil sketch. Thank you!!