Basic Idea

In order to detect polygons we need to use several algorithms. First we must find all intersections between line segments. As an output of the algorithm we will have a graph in which endpoints of segments and intersections between them are vertices while edges of the graph are segments. (pic1). Next we need to find the minimum basis cycle of that graph. And finally we have to transform these cycles into polygons.

Detecting Intersections

For our needs we will use Bentley-Ottmann algorithm which is very famous algorithm for detecting geometric intersections. It is based on a sweep line technique - imagine horizontal line drifting from left to right through coordinate plane intersecting set of line segments.During this drifting there are some positions when we need to save some information about segments and sweeping horizontal line.We need two balanced binary trees for saving that information in sorted order. There are two invariants which we need to consider.

-segments which are left from the sweep line are already processed and intersections are founded
-information for processing segments which are right from the sweep line or are intersecting it is stored in data structures.

Segments which are at the moment intersecting sweep line are stored in structure 1. When sweep line meets new segment i.e starting point of new segment we need to add that segment into structure 1. Segments in tree are sorted by Y coordinate from top to bottom. Alternatively when sweep line meets endpoint of currently intersecting segment we need to delete that segment from structure 1. And imagine a situation in which segments S1 and S2 are intersecting sweep line and new segment S3 stands between these two segments. In this case we need to change the order of segments in structure 1. And every time finding intersection of segments we have to swap those segments in structure 1. Points in which these situations occur are known as transition points and we will store these points in structure 2. In every such kind of situations we need to test an occurance of intersection between two segments which are adjacent to each other on the sweep line. To get an insight of this idea let's consider the following example. Suppose we currently have two segments S1 and S2 intersecting sweep line and segment S3 whose starting point encounters sweep line. As we mentioned above we need to add this segment into structure 1. In our structure 1 S1 is succsesor of S3 as in the pic.2 and S2 is predecessor of S3.

As pic.2 shows segment S3 becomes adjacent to both segments S1 and S2 so we need to test if they do intersect. If we find out that they intersect we must add their intersection point into structure 2. Now let's consider another situation where sweep line encounters intersection point of two segments(pic.3).

As we recall every time when we detect intersection we swap that segments in data structure. In our case we assume that S1 and S2 are already swaped and we need to check these two segments' intersection with adjacent segments. As picture 3 shows we need to check S2 and S3 if they intersect and if yes we add that intersection point into structure 2. Similarly we need to check S1 and S3.

Detecting Polygons

Detecting polygons is simmiliar to finding cycles in a graph (pic4). We take into count only small polygons (i.e polygons with minimum number of edges and which cannot be constructed by connecting other small polygons), because number of cycles in a graph can grow exponentially with respect to number of vertices. Finding small polygons is the same as searching for a Minimum Cycle Basis

Constructing polygons

At this step all is left is to construct polygons from the MCB.This is a very easy step: you can find pseudocode of algorithm here.

To summarize our combined algorithm takes as an input a set of segments and in the output we find polygons.