seb@Clik.QC.CA (Sebastien Roy) (10/19/89)
I would like to know if there is a simple algorythm to find the edges and vertices of a polygon from a simple bitmap image. If this is too hard, it would be enough to get only the number of vertices in the polygon. Thanks... -- -Sebastien Roy, Director of Computer Services--------Clik Telematique Inc.--- Internet: seb@Clik.QC.CA (being registered..) roys@IRO.UMontreal.CA Dumb: ...mit-eddie!mcgill-vision!iros1!zoom!roys ...mcgill-vision!iros1!roys Phones: (514) 449-2860/home (514) 933-7161/Clik Fax: (514) 933-2164
nagle@well.UUCP (John Nagle) (10/23/89)
In article <413@zoom.Clik.QC.CA> seb@Clik.QC.CA (Sebastien Roy) writes: >I would like to know if there is a simple algorythm to find >the edges and vertices of a polygon from a simple bitmap >image. The real question is how clean an image you have. If there is noise in the bitmap, (perhaps because it was obtained by scanning) then dealing with the noise dominates the problem. The technique described below is reasonably good. It's straightforward to trace around the perimeter of the polygon and extract the perimeter as a set of points. Then, remove all points that are redundant, i.e. nearly collinear with the line between their neighbors. Repeat until no redundant points remain. This probably won't get you a clean polygon; there will be clusters of points near the vertices of the polygon, especially if the vertex is at an acute angle. So look for situations where two long segments surround a cluster of points, and then project the long segments to their intersection. If all the points in the cluster are near the projection of the long segments, replace the points in the cluster with the single point at the intersection of the projected lines. Then go back to redundant point removal as above. Iterate these two phases ("straightening" and "sharpening") until no improvements occur. The process is guaranteed to terminate because improvements always involve removing points. The end result will be a reasonably good polygon perimeter. John Nagle