Polygons from line segments

Ami's answer is a good pointer in the correct direction, but here are the more detailed steps you might need to know about:

1. Take the list of line segments and build a collection of vertexes. Since check each individual segment for intersections with each other segment is basically a N^2 operation when done via brute force, you might want to build a quad-tree and use that to reduce the number of checks you are performing. If n is small or you have a lot of cpu time to burn, just brute force it, otherwise you need to be clever about your collision detection. Here is a library that implements quad-tree collision detection: https://github.com/hroger1030/SpatialTrees

2. With your list of nodes and edges, you have the pieces to build a graph. you can call your lines nodes and the intersections the edges or vice-versa, it kind of doesn't matter. The important thing is you can now just go find all the cycles on the graph where the number of nodes in the cycle > 2.

I just so happens that I wrote an implementation of Tarjan Cycle detection in c#: Tarjan cycle detection help C#. This might be an alternative to the suggested Connected Components Algorithm.

This is indeed a classical problem in computational geometry.

Your are looking for the faces of an arrangement of your segments.

For a discussion of this topics with (too many) details, and source code, there is this wonderful library: CGAL .

Note that you'll have to decide what you do for e.g. a polygon inside another, many polygons intertwined, etc.

One way would be to build a graph as follows:

• the nodes are the intersection points of the edges

• there's an edge between nodes i and j iff points i and j are on the same edge

Once you've built the graph:

• Run the Connected Components Algorithm on it, and check for connected components of size > 2

• Run a convex hull algorithm on the intersection points within such a component

Edit modified from original due to excellent point by FooBar.