Comparing images

Hi Guys,

I am reaching out to my fellow developers with an interesting issue i am chewing on, maybe some of you can give me some hooks or insights to continue my research. Here is my problem :

I have an array with lines representing a closed image. Something like this :

[line1_start], [line1_end],
[line2_start], [line2_end],
All lines are in 2D space, so either y or z is always 0, lines are in a random order.

What i need is a method that gives me only the lines that form the outside shape of the image, so all inside lines, that are not part of the outside shape, should be ignored. I will use that to compare the set of lines with other shapes and images.

The array can contain overlapping lines and some lines might only be partly used for the outside shape.

So, the left images is what i have, the right images is what i need.

Anyone any ideas or experience?

I think if you walk counter-clockwise and always pick the right-most edge you’ll find the outer perimeter. Though I’m not entirely sure how you find a good starting edge (one that is already on the perimeter).

@CAUL - you know this one, right?

That’s right, you basically walk the outside of the shape in this manner. To find a start edge (assuming we’re on the xy-plane) find an extreme vertex in some dimension, let’s say positive x. Among the edges of this vertex select a start edge by: max_x_vertex.egdes.max_by { |e| e.other_vertex.x }.

Now, in the case above I think it’s simpler to run find_faces on all edges and then remove all edges connecting two faces.

1 Like

Yes, I agree find_faces + cleanup is the way to go.

Thanks for all the suggestions guys. I found a solution going clockwise that seems to do the trick. Problem was…i have an array of lines that could or could not form 1 or more faces together and the lines are unsorted, not by definition connected and not even always in the same direction (startpoint and enpoints are not always in line) That cross you see in my example, can exist out of 4 lines meeting going any direction possible, it can exist of 2 lines crossing eachoter, or it can exist out of 3 lines.And this is just one of the easier examples. I needed a few more steps by first cleaning up my lines array and it seeems like i managed.
Thanks again for thinking with me, greatly appreciated.

And hope to see any of you on the DevCamp in Leeds

1 Like