[geos-devel] Fwd: Geometry/Rectangle Intersection: line touching rectangle

[Sandro Santilli]

On Thu, Sep 11, 2014 at 07:30:45PM +0300, Mika Heiskanen wrote:
> On 09/11/2014 06:57 PM, Sandro Santilli wrote:
> >Did you take a look at the algorithm ?
> >It sounds like by the end of operations the class is left with a bunch
> >of lines to work with, not much to build a result w/out going back
> >to look at which sides of those lines are internal or external of the
> >originals.
> 
> At the time of insertion into the builder it is known for all
> linestrings whether they are part of a hole or the exterior of
> a polygon. This information can be inserted into the builder
> along with the linestring, and used in the rebuild phase.

Not only whether the linestring was part of an hole or a shell, but
in case it was part of the hole, we must also pass along which side
of boundary segments had the area. Look here:

Clipping rectangle       Expected result
and input                ( a poligon + a line )

 +-------+               . . . . .
 |rect   |               .       .
 |  +----:-----+         .  +----+
 |  |    :     |         .  |    |
 |  | +--+     |         .  | +--+
 |  | |h |     |         .  | |  | <-- dangling line
 |  | +--+ s   |         .  | +--+
 |  |    :     |         .  |    |
 |  |    +--+  |         .  |    |
 |  |    |h |  |         .  |    | <-- dissolved
 |  |    +--+  |         .  |    |
 |  |    :     |         .  |    |
 |  +----:-----+         .  +----+
 |       :               .       .
 +-------+               . . . . .

> Currently
> the logic dictates that any clipped hole must necessarily become
> a part of the exterior of a polygon, and the linestrings are
> connected accordingly by traveling the rectangle clockwise to
> find the next linestring to connect to. Even though the orientation
> of the holes was counter-clockwise, connecting to the linestring in
> the original order is correct for building the exterior.

That logic doesn't work in the case above

Builder currently        And after connecting the linsestrings
sees this:               produces this (single polygon with an hole):

 . . . . .               . . . . .
 .       .  l: line      .       .  s: shell
 .  +----+  p: poly      .  +----+  h: hole
 .  |    .               .  | s  |
 .  | +--+               .  | +--+  This is an invalid polygon
 .  | | p|               .  | | h|  because the shell and the
 .  | +--+               .  | +--+  hole have a linear intersection
 .  |    .               .  |    |  thus producing a "side-location conflict"
 .  |    +               .  |    |  when attempts are made to build a
 . l|    |l              .  |    |  topology of them (ie: both sides
 .  |    +               .  |    |  of the edge are _external_).
 .  |    .               .  |    |
 .  +----+               .  +----+
 .       .               .       .
 . . . . .               . . . . .

In order to fix the above, the Builder should not receive the top hole
as a polygon, but as a line:

  +-------+             . . . . .         
  |rect   |             .       .  l: line
  |  +----:-----+       .  +----+  
  |  |    :     |       .  |    .         
  |  | +--+     |       .  | +--+        
  |  | |h |     |       .  | |l .        
  |  | +--+ s   |       .  | +--+        
  |  |    :     |       .  |    .        
  |  |    +--+  |       .  |    +        
  |  |    |h |  |       . l|    |l       
  |  |    +--+  |       .  |    +        
  |  |    :     |       .  |    .        
  |  +----:-----+       .  +----+        
  |       :             .       .        
  +-------+             . . . . .        

In order to do so, the RectangleIntersection class should be able
to distinguish hole boundaries falling on the rectangle boundary
in base or the side containing the interior hole. If the hole
interior is interior to the rectangle (top hole), then the boundary edge
needs to be omitted, if it's exterior (bottom hole), it must be included.

Still, in order to be able to construct the expected output, the
hole boundary which was "omitted" would need to be re-included as
part of the output collection, in order not to drop any point in
the intersection point-set. So maybe RectangleIntersectionBuilder
would also need another container to push things to...

--strk;

> What should remain is how to detect in the reconnect
> phase the special case of a linestring traveling only on the edges
> of the rectangle, and to handle it accordingly. I'm not sure,
> but wouldn't the boolean passed along with the linestring
> (hole or not) be enough to decide whether to just throw the
> linestring away or keep it in the reconnect phase? Possibly
> such a linestring could be even detected during the clipping
> phase by keeping track on whether all the vertices so far have
> been on the edges without true intersections, and then the
> linestring would not be inserted into the builder at all if it is
> not of the correct type (hole/exterior).
> 
> Mika Heiskanen / FMI