Hi, I am trying to output a list of points and connect them to be a polygon from a gray scale image. I know I can do edge detection to get the points, but then how can I connect them up nicely? I tried some sources but didn't find the answer. Thanks for any information.

The most direct solution may be to create an ordered list of the edge pixel's positions (Counter clockwise or something)

From this you can calculate the angle from one point to the next (or from one point to, say, the average of the next 3 point's angles, not individually, but from points 1-2 1-3 1-4.)

Keep track of the current angle, detect (using some margin of error/change value) where the linear equation changes. (Obviously, this is where you add the point to the point list for the polygon.)

Depending upon the resolution of the image, taking the angle between two sequencial points may prove to be more detrimental than beneficial.


Depending upon the complexity of the shape (and if it has holes it makes stuff a real pain) you may have to figure out the best way to triangulate the resulting polygon. The dead easy way is to make a triangle fan with a point in the "middle"/average of all the point's positions. This won't always work though, and if you search on gamedev's forums, you'll find this problem has been discussed several/many times before.

Good luck, (any questions?) tell me how it works!

-Michael g.

Thank you so much Michael!

Well I do have questions... From the very beginning:

Quote:The most direct solution may be to create an ordered list of the edge pixel's positions (Counter clockwise or something)

How? The best source I could find so far is from MatLab's description page: http://www.mathworks.com/access/helpdesk/help/techdoc/creating_plots/specia29.html. But this is far from being detailed -- I could think of several special cases that this algorithm (if described as simply as in there) would fail.

I know I would be able to work out an algorithm by myself in a couple of days but believe there's already something good out there to save me the time.

For the "holes" problem you mentioned, I thought about for a while and came up with a solution: for every pixel in the image, count the number of crossing (edge) pixels. Each time we work on one edge pixel (connect it with edges etc, i.e. examine it), decrease the counter by one. Until we hit zero. There are two ways to implement it: 1. keep a seperate "mask" image that has zeros for non-edge pixel and ones for edge-pixles. Each time after we finish one contour and change the mask image by removing the ones that correspond to this contour, we go through the mask image to see if there's any "ones" left. The complexity is O(M x N), where M is the number of contours and N is the number of pixels. 2. Keep a list of edge points, delete one point if it is in a known contour, until the list is empty. The complexity is O(N), with list operation overhead.

[edit] Hm my solution is not the real solution -- it doesn't take care of the triangulation problem, which was actually what you raised. Sorry.

I recently did something similair, my input was a black and white image. What I did:
1. Find the first black pixel
2. Walk around the edge, using a 'cursor' placed on the intersection of four pixels, determine what direction to move in based on the neighbouring pixels
3. Add a line segment when you move the cursor
4. When we reach the start, we are done
5. Clean up the polygon by combining consecutive line segments, or using more fancy algorithms (I convert lines to bezier curves)

If there can be holes, or there can be multiple polygons; simply repeat the process. Mark polygons that you already found.

Take a look at the marching squares algorithm:

google

It is used to generate a contour from a 2D image given a threshold/level value.

If you already have points and want to connect them to form a single convex polygon, you may want to look into computing a convex hull from points:

link

Edit:
Use marching squares for a "quick-n-dirty" way to get the job done.
Heck, even use it to come up with the polygon edge list. If you want to simplify the mesh you'll want to post-process it as well, though.
----

twanvl detailed how you can go about creating that ordered list of points.
The method he talks about though will probably only work well if the edge is exactly 1 pixel wide.
This isn't bad, and is (if at all possible) what you'll want to shoot for.

Clean up that source data as best as possible. Automate the process, and you're set.
He mentions using a black/white dataset. You'll probably want to break yours down to black/white as well (after finding the edges.)

He mentions to
---
5. Clean up the polygon by combining consecutive line segments, or using more fancy algorithms (I convert lines to bezier curves)
---

That's what I was talking about with this part
---
From this you can calculate the angle from one point to the next (or from one point to, say, the average of the next 3 point's angles, not individually, but from points 1-2 1-3 1-4.)

Keep track of the current angle, detect (using some margin of error/change value) where the linear equation changes. (Obviously, this is where you add the point to the point list for the polygon.)

Depending upon the resolution of the image, taking the angle between two sequencial points may prove to be more detrimental than beneficial.
---

If you're trying to create simplified models you'll probably want to do some data cleanup similar to what I've suggested.
If you want full resolution, you'll want to mess with bezier curves, on the full dataset, etc.

The whole "cursor" idea is probably best, but you may have to add a little more logic to where it steps next, especially if the line is more than one pixel wide. In this case you may opt to follow the "left" side of the curve. And always choose the "left-most" line pixel in the path. ("left" in this case, is relative to the cursor. That means, if you're travelling clockwise around the poly, it will be the "outside edge". If you'lre travelling couter-clockwise, it would be the "inside edge". However, when you begin following the shape, you really don't know which side (relative left or relative right) is the "inner" or "outer" edge so you have to just choose one!

----------
There seems to be quite a bit of information on triangulation on the 'net, so I'll leave that up to you (unless you're a die-hard do-it-yourself I'd just use a tried and proven method/function already in existance.) If you'd like to code that yourself, some simple (but non-optimal) solutions come to mind.

-Michael g.

Thank you twanvl for sharing your algorithm with me. I would be working on grayscale images (Thr33d, I need the contour lines, which might not be edges, thus using edge detection to convert the image to black-and-white is not always possible), but it seems that your algorithm can be easily generated to grayscale images.

Thank you slack for the info and the links. They provided with much more insight into this problem than I had expected! I spent about 3 hours this morning going through your recommended websites.

Let me start with the basic before working on making triangles/bezier curves. Actually I have an old project on bezier/subdivision etc so that would not be a problem later. Below would be what I would be working on tomorrow:

Quote:Walk around the edge, using a 'cursor' placed on the intersection of four pixels, determine what direction to move in based on the neighbouring pixels

Quote:The whole "cursor" idea is probably best, but you may have to add a little more logic to where it steps next, especially if the line is more than one pixel wide. In this case you may opt to follow the "left" side of the curve. And always choose the "left-most" line pixel in the path. ("left" in this case, is relative to the cursor. That means, if you're travelling clockwise around the poly, it will be the "outside edge". If you'lre travelling couter-clockwise, it would be the "inside edge". However, when you begin following the shape, you really don't know which side (relative left or relative right) is the "inner" or "outer" edge so you have to just choose one!

If you have more details on this I would greatly appreciate that. Otherwise I would still be able to get the job done (probably more time).

Thanks a lot guys!