[geos-devel] Find self-intersections

[Frederik Ramm]

Hi,

    today I came across the following problem that I tried to solve with 
GEOS.

I had 3.000 linestrings which together formed one large ring. However, 
this ring was not simple; it was 8-shaped. I wanted to find out where 
the intersection point - or perhaps the intersection line! - was.

The best I could come up with was:

for (i=0; i<count; i++)
{
    for (j=i+1; j<count; j++)
    {
       Geometry *p = linestring[i]->intersection(linestring[j])
       if (p)
       {
          // found something
       }
    }
}

This is of course rather inefficient! I'd better build a LinearRing from 
the lot of them and then query for self-intersection. I did find some 
code that does this when looking at how isSimple() is implemented; 
however, that code would only find self intersection points, not lines.

I wonder if there is some generic way to determine a geometry's "self 
intersection"?

Bye
Frederik