I have failed to find the "name" of the algorithm that would allow one to convert lines to polygons. Since this issues crosses GIS and the fields of computational geometry and computer science. I am not sure what else to add to the mix. I am reluctant to provide a list of what I have searched on since I would also like to know what other people would consider their first choice of search criteria.
The scenario...I have lines (two points needed to construct a line)...each line is connected to at least one other line. The intervening space between the connected lines would form a polygon. The simplest scenario would be a triangle...a rectangle...and one could move beyond to multi-segmented features.
Sorry for any vague descriptions, but as I said, I don't want to guide the possible solutions down a path that I have already visited, since I am interested in the "first thought" as much as a final solution.
Answer
Perhaps "area fill"? See here and here.
Edit
Another possibility is constrained triangulation. (The link is to a Java applet that lets you draw a graph with the mouse and then illustrates a plane-sweep algorithm to triangulate it.) The result of any such triangulation, no matter how it is carried out, can readily be processed to create the desired polygons: simply merge all neighboring triangles that share a newly-created edge.
Example
Original graph:
Triangulated graph:
No comments:
Post a Comment