How to detect intersections (and lines, if possible)?

General Discussion Other

patakk

How to detect intersections (and lines, if possible)?

in General Discussion • Other • 1 year ago

Hello!

I'm working on something which would give results much faster if I could include automatic intersection detection. In short, what I want is to make a function which would recieve an image as an argument and would return (x, y) location(s) of the intersections. To make it a bit simpler, this image would consist only of lines and black&white pixels. The way of storing the coordinates data is not relevant, I'm just looking for a way of getting the yes/no answer if a pixels is an intersection or not.

Here's an example of a typical image that I would use:

What I'm asking you is to give me an advice, is there a good library which would do that for me or should I write this from scratch?
If the answer is the latter, I'd like you to give me an idea or suggest me a way of thinking when approaching a problem like this, if you know what I mean.

Thanks in advance!

Replies(3)

amnon.owed

Re: How to detect intersections (and lines, if possible)?

1 year ago

Use the pixel values, either by thresholding or by counting (neighbour) blackness to determine hotspots. Clean the list of found points from coordinates very close to each other. Either implement that yourself or check out the example below which extracts the 6 intersections from the image you provided.

Code Example

PImage img;
ArrayList <PVector> is;
void setup() {
img = loadImage("image.jpg");
size(img.width, img.height);
is = extractIntersections(img);
smooth();
noFill();
}
void draw() {
image(img, 0, 0);
for (PVector p : is) {
ellipse(p.x, p.y, 15, 15);
}
}
ArrayList <PVector> extractIntersections(PImage in) {
ArrayList <PVector> list = new ArrayList <PVector> ();
PImage work = in.get();
work.filter(THRESHOLD);
color black = color(0);
for (int i=0; i<work.pixels.length; i++) {
if (work.pixels[i] == black) {
int x = i%work.width;
int y = i/work.width;
list.add(new PVector(x,y));
}
}
for (int i=list.size()-1; i>=0; i--) {
PVector p = list.get(i);
for (PVector o : list) {
if (p.dist(o) < 15 && !p.equals(o)) {
list.remove(i);
break;
}
}
}
println("Number of intersections found: " + list.size());
return list;
}

patakk

Re: How to detect intersections (and lines, if possible)?

1 year ago

Thank you so much!

The idea of just counting the number of dark pixels around each pixel came to my mind just minutes ago!

amnon.owed

Re: How to detect intersections (and lines, if possible)?

1 year ago

Yeah. Depending on the images, thresholding might work (like with the provided image) or a little more work would be required by actually counting pixels or pixel values for more robust results. But the basic concept is the same, finding hotspots based on (surrounding) color. Below an even shorter hack (it checks closeness before adding to the list) that still works on the provided image.

Code Example

PImage img;
ArrayList <PVector> is;
void setup() {
img = loadImage("image.jpg");
size(img.width, img.height);
is = extractIntersections(img);
smooth();
noFill();
}
void draw() {
image(img, 0, 0);
for (PVector p : is) {
ellipse(p.x, p.y, 15, 15);
}
}
ArrayList <PVector> extractIntersections(PImage in) {
ArrayList <PVector> list = new ArrayList <PVector> ();
PImage work = in.get();
work.filter(THRESHOLD);
for (int i=0; i<work.pixels.length; i++) {
if (work.pixels[i] << 8 == 0) {
PVector p = new PVector(i%work.width, i/work.width);
boolean close = false;
for (PVector o : list) {
if (p.dist(o) < 15) {
close = true;
break;
}
}
if (!close) { list.add(p); }
}
}
println("Number of intersections found: " + list.size());
return list;
}

Top Reply