Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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.

share|improve this question
    
Can lines coincide? Can lines cross? (i.e. is it clean?) If so, I hope calling this process Build wouldn't be too app specific. –  Kirk Kuykendall Jan 14 '11 at 0:40
    
Kirk Coincident lines and other "defects" would have been removed prior to constructing the polygons...I am trying to find the "algorithm name" which I am sure has been implemented in various GIS packages (eg arcgis). So in short, consider that all degenerate conditions have been dealt with and you are left with clean lines (2 point lines) that coincide at nodes which you should be able to construct polygons. The key is that the lines exist, there is no degenerate conditions and the intervening space needs to be converted to polygons. Thanks –  Dan Patterson Jan 14 '11 at 2:56
    
Are the points on a plane or on a sphere? –  Kirk Kuykendall Jan 14 '11 at 16:54
    
Kirk...On a plane, metric x, y coordinates, not spherical coordinates. For example, say you have the line segments that would form a voronoi diagram, but all you have is the segments that form it but not the actual data structure the led to it. In short, every segment is connected and every segment is unique. –  Dan Patterson Jan 15 '11 at 12:06

6 Answers 6

up vote 3 down vote accepted

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:

Original graph

Triangulated graph:

enter image description here

share|improve this answer
    
Bill Going to up-vote since I hadn't come across that...not wanting to limit other comments from people in various disciplines. –  Dan Patterson Jan 14 '11 at 2:52
    
Although, largely dealing with raster fills, this is the closest answer. I still don't have an algorithm name unless it is attached to either raster or vector but a "sweep" algorithm might suffice, but I can't figure out for the life of me why coordinates would be sorted by Y rather than X (which is easy to implement in most languages). –  Dan Patterson Jan 18 '11 at 3:42
    
@Dan Sorting by y or x is immaterial, as you suggest. You are also correct that plane-sweep or line-sweep algorithms are involved, but unfortunately this is a general technique that covers almost all computational geometry procedures, so it's not a suitable term for searching specifically for your algorithm. Note that this particular problem is not purely graph-theoretic, because it involves an embedding of the polyline complex into a plane (or sphere), and so a good algorithm must maintain information about the embedding: that's why it really is an area fill problem at heart. –  whuber Jan 18 '11 at 14:09

have you explored GRASS's code base for a solution to your problem? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html

share|improve this answer
    
Thanks...but I am not looking for a specific "packaged" solution but the underlying algorithm and/or its name which would come the various areas of GIS, Comp Geom and/or Comp Sci...keep the ideas coming –  Dan Patterson Jan 14 '11 at 4:28
    
I was thinking of specifically looking at the source code behind the 2 mentioned processes in my link may help you. –  oeon Jan 14 '11 at 16:34
    
I guess I would have to install the software to see the code since I don't see any listing on those pages unless I am missing something. –  Dan Patterson Jan 15 '11 at 12:11
    
You can browse GRASS source online: trac.osgeo.org/grass/browser –  underdark Jan 15 '11 at 13:28
    
@underdark Thanks for the pointer. As far as I can tell from main.c in the v.type source, all that happens is that the features are re-labeled as boundaries: no actual processing occurs. In retrospect this isn't too surprising: if (I don't know for sure) the features are maintained with full 2D topological information, then all the computation to identify polygonal regions has automatically taken place during feature creation or import and is retained throughout all geoprocessing operations. –  whuber Mar 9 '11 at 20:36

In graph theory, this operation is called faces computation. It is related to the computation of the dual of a given graph.

For example, in the GeOxygène java library, a graph (called CarteTopo) has a method getFaces to retrieve its face.

This is called polygonization in JTS

share|improve this answer
    
Good links. However, they all presume @Dan's problem has already been solved: being able to call a graph "planar" means you have already identified the polygonal faces. He wants to know how one goes about converting an arbitrary collection of arcs (in the plane) into an honest-to-goodness planar graph in the first place. This requires building a representation of its "topology," such as a DCEL. –  whuber Mar 9 '11 at 20:38
    
Thanks a lot whuber, you are a fount of knowledge! I wonder how somebody can be so brillant. –  julien Mar 9 '11 at 22:14

The RepRap host software converts a list of line segments (in some unknown random order) into a list of polygons, which sounds similar to what you are trying to do.

In particular, the RepRap "end matching" algorithm handles a bunch of pathological cases.

Alas, the RepRap software assumes that every corner has an even number of edges going to it -- 2 lines going to a corner on a normal object; 4 lines going together when the corner of one object touches the corner of another object, etc. I don't know how hard it would be to adapt this algorithm to handle voronoi diagrams, which usually has 3 edges going to every corner.

share|improve this answer
    
+1 Interesting find! Watch out, though: although this software looks capable of solving many problems related to connecting lines into polygons, it may do too much: it looks like it tries to simplify the features as well, which may be an undesirable side effect. (E.g., it can destroy topological integrity.) –  whuber Mar 9 '11 at 20:30

Hallo

I don't think what you are looking for is a specific algorithm. The task can be quite difficult or very simple depending on your dataset.

You should divide the problem in at least 2 parts. 1) is more of a networking problem, how to find closed rings of linestrings. 2) express the closed linestring as a polygon

The second part, which is "converting lines to polygons" depends more of the format than polygon/linestring representation. I mean going from:

LINESTRING(1 1, 2 2)
LINESTRING(2 2, 2 1)
LINESTRING(2 1, 1 1)

to:
POLYGON((1 1,2 2,2 1,1 1))

is converting line to polygon, but isn't what you are talking about I guess. The more difficult part is the first on. If you have a spaghetti of lines, how to order them as closed linestrings.

I guess the answer to that question depends a lot of the dataset. As Kirk asks, if the lines can cross the problem is much bigger. If you know that all "line collections" is a part of a closed linestring it is getting easier. Then you can grab any line and walk your way around the path until you are back again and then move on to step two above.

My point is that the condition of the dataset sets all the rules about how to do it. If you want to find all possible polygons in a spaghetti of linestrings I assume there will have to be a lot of differnt algorithms involved to put vertex points in all crossings, search all possible paths and so on.

In PostGIS the function is called ST_Polygonize That function creates all possible polygons from the linestrings you give it.

That is performed by GEOS so you can find the algorithms behind in both GEOS and JTS code.

Just some thoughts

/Nicklas

share|improve this answer

You might try searching for the "Forward Star" algorithm. I've been told it is generic, but the only discussions about it I've ever read were always in reference to arcgis. Maybe look into the references cited in these lecture notes for forward star.

share|improve this answer
    
I'll comment here, even though this comment addresses some others of the proposed solutions as well: the problem cannot be represented in a network (or graph). It requires information about how the lines are connected within a two dimensional surface. Thus the forward/backward star representations would be of little use; a DCEL or something like it is needed. –  whuber Mar 9 '11 at 20:29
    
@whuber - I was assuming that Dan's comment that all "defects" had been removed implied that the lines were clean. As such, it should be possible to reduce this to a graph traversal problem of finding all cycles in a graph. At first I thought Forward star would assist in algorithms that walk around a graph taking the sharpest right turn possible at each node. However, looking a bit more it appears there are better ways. stackoverflow.com/questions/261573/… But still, this assumes problem can be re-stated as a graph. –  Kirk Kuykendall Mar 14 '11 at 16:31
    
Finding cycles in a graph is not the same as finding faces in a planar graph. Consider the abstract graph with vertices {a,b,c,d} and edges {a,b}, {a,c}, {b,c}, {b,d}, {c,d}. A basis for the cycles consists of a->b->d->c->a and a->b->c->a. In the planar embedding a->(0,1), b->(2,2), c->(2,0), d->(3,1) (where all edges are line segments), the cycle a->b->d->c->a is not a face, but if we move d to (1,1), it is a face. This shows why the concept of "face" requires the graph to be embedded in the plane and why faces cannot be computed purely from the abstract structure of the graph. –  whuber Mar 14 '11 at 17:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.