title: Compute length of segment intersecting a polygon in 2D
body: <p>Given a segment S and a polygon P, is there a fast algorithm that returns the total length of the subsegments of S crossing polygon P?</p>
  
  <p>Note: P is defined by a closed LineString (i.e.: an array of points where the first and last one are equal). P does not have any "holes", but can be concave and/or self-intersecting.</p>
  
  <p>Note: the final goal is the total length of all the intersecting subsegments, and if this can be done faster without retrieving an explicit array of all of them, all the better.</p>
  
  <p>Bonus points: a Java implementation for said algorithm. Using libraries like JTS is ok, as long as the resulting solution is fast.</p>
  
  <p>A simple solution using JTS already exists but does not support self-intersecting polygons and, I believe, is not the fastest. This solution involves creating a Polygon object (for P), a 2-point LineString object (for S), and getting the length of the resulting intersection.</p>
  
  <p>Here is the code that does that:</p>
  
  <pre><code>    GeometryFactory fact = new GeometryFactory();
      WKTReader wktRdr = new WKTReader(fact);
  
      String wktP = "POLYGON((40 100, 40 20, 120 20, 120 100, 60 40, 40 100))";
      String wktS = "LINESTRING(20 60, 160 60)";
      Geometry pl = wktRdr.read(wktP);
      Geometry ls = wktRdr.read(wktS);
      Geometry in = pl.intersection(ls);
      System.out.println("P = " + pl);
      System.out.println("S = " + ls);
      System.out.println("P intersection S = " + in);
      System.out.println("S length = " + ls.getLength());
      System.out.println("P intersection S length = " + in.getLength());
  </code></pre>
  
  <p>EDIT: a consideration on self-intersecting polygons: a solution, although maybe not the fastest, could involve pre-processing a self-intersecting polygon by splitting it into multiple non-self-intersecting ones.</p>
  
  <p>Some explanations and some pseudo-code on this matter are here:
  <a href="https://stackoverflow.com/questions/4849645/algorithm-to-split-self-intersected-path2d-into-several-not-self-intersected-pat">Algorithm to split self-intersected Path2D into several not self-intersected paths?</a></p>