polygon boundaries

Programming Questions

terekita

in Programming Questions • 1 year ago

Hello,

Given an image such as:

,

I'd like to get a list of all the black pixels segmented according to the polygons that they enclose. In other words, every single black pixel is part of the boundary of at least one polygon. For each polygon, I'd like to have a list of these boundary pixels.

I've been barking up various trees, all involving comparing an individual pixel's color with its neighbors, but before I completely tear my hair out by probably reinventing a wheel, I thought I'd see if anyone could point me in the right direction.

Any help would undoubtedly result in immense karmic rewards, I just know it :)

Thanks!, Michael

Replies(4)

jbum

Re: polygon boundaries

1 year ago

I think, if I were doing this, I would determine the vertices of the polygon corners (that's the hard part). Then I would use Bresenham's line drawing algorithm to determine the pixels that each line segment crosses (that's the easy part).

Bear in mind that you are assuming that each pixel is on or off a line. This is an oversimplification. A fraction of a pixel may be occluded by a line.. But Bresenham will give you the pixels that are crossed by an unantialiased line.

Also, I assume you are only interested in polygons that aren't bisected by a line. Otherwise, there are too many polygons in the above diagram to fit all that data in memory.

I'm curious why you need to store the pixel addresses in a data structure. Bresenham is fast enough that you could just store the corner vertices, and regenerate the pixel cords on the fly (at nearly the same speed it would take to traverse stored data), saving a lot of needless storage.

* * *

So this brings us to the hard problem, creating a set of polygons defined by their corner vertices.

This can be subdivided into two problems

1) convert the lines into a list of vertices connected by line segments.

2) determine the polygons.

You can accomplish step one by iterating through each pair of lines, and determine the intersection point, if any. Bisect each line at the intersection point to create 4 line segments that share a common vertex.

I thnk once you've done that you can find the polygons by traversing the segments In a winding manner (at each vertex, take the sharpest right turn' until you've made a cycle - that's a polygon. Do this for each line segment, discarding duplicate polies.

terekita

Re: polygon boundaries

1 year ago

Thanks very much for your reply, jbum. In particular, it has led me to Bresenham, which I am now attempting to grok.

In the meantime, several things occur to me, though they are still a bit jumbled up (hopefully coffee and a ride on the train will clarify things)...

Since I am drawing the lines merely as a guide to future operations, but don't know the crossings at the time of the drawing, I could draw the lines in color, such that I can examine each pixel and see if it is the sum of more than one line. If so, it's an intersection.

So my new problem then becomes: given a set of points, connect them into polygons that aren't bisected by other lines. Which brings me to your suggestion re: traversing the segments in a winding manner. If I make progress in this, I will post the results.

Thanks again for your help.

davbol

Re: polygon boundaries

1 year ago

>> Since I am drawing the lines

If you are drawing the lines then you obviously must already know their coordinates. (a different problem than as first posted, which was: given an image reconstruct the polygons - much harder)

So, forget pixels, this is a computational geometry problem, and a relatively simple one at that. I suggest you solve it analytically, rather than by scanning pixels. (and you'd still need all the compgeom stuff anyway, eventually, even if you somehow manage to succesfully scan the pixels for proper intersection points)

Start with a rectangle defining the screen boundary

Store that in a collection of polygons

For each line:

For each polygon that it crosses:

Split that polygon into two new ones, store those in the collection

Remove the original polygon from the collection

If you do it "one line at a time", it's really not that big of a deal.

You'll need a line intersection test (to check for crossings and locate the coordinates, an easy test, google for it) and a winding order to reassemble the new pieces (if your polys are already stored in proper winding order, then the split coordinates should already tell you which "side" all the existing vertices belong to, then just "stitch them up" with the new splitting vertices).

The only potential "gotchas" are colinear segments or an exact intersection with an existing vertex, tho both seem unlikely given the sparseness of your lines, but just watch out for them.

hth

terekita

Re: polygon boundaries

1 year ago

Thanks davbol! Yeah--I think I'll probably wind up with both flavors of this problem--where I know the line coordinates as they are drawn, and the other, original problem, where I've done some kind of feature extraction and then wind up with an image, rather than known line coordinates. As an aside, I'd wondered about linear programming solutions...

I don't quite know how to implement your suggestions as stated, but I understand enough of what you've suggested that I've got lots of avenues to being googling on, for which I am very appreciative.

Thanks!

Top Reply