(supposed) improvements to dateline handling

[sttawm]

Note that much of this code is copied from
https://github.com/spatial4j/spatial4j/blob/185132fae6897f57faacdac91c0a98a92e380bfc/src/main/java/com/spatial4j/core/shape/jts/JtsGeometry.java.

Note that I have (somewhat arbitrarily and regrettably) removed the Date-Line operations from JtsGeometry.

A few modifications have been made:

• Addressed a TODO -- Negative pages are handled by pageGeom() (AKA cutUnwrappedGeomInto360), which allows for the removal of redundant shifting.
• The boundaries of the date-line have been generalized (in order to
  work with generic projections).
• Rather than unioning paged geometries, they are merely "collected" into a single geometry (for efficiency's sake). This is done by a new method -- collect(). )Perhaps I've missed something here and the use of union is actually crucial in some cases)
• Extended unwrapDateline() to
  handle coordinates outside of the bounds.
• Fixed a bug inunwrapDateline
  that invokes Geometry.geometryChanged() for instances of
  GeometryCollection, which gave rise to another bug in that GeometryCollection.intersects() is an illegal operation, and so...
• These operations have been extended to direct instances of GeometryCollection (i.e. non-subclasses)

Otherwise, some assertions have been removed (sorry), and the style is probably not quite on.

Let me know if you'd like to see some of these changes in with the actual code (as of now, this class is entirely independent, for the purpose of demonstration).

[dsmiley]

I really appreciate what you've done here!

I think it's totally fine that you moved the code to a utility class. I was already thinking it deserved a separate class since there is so much logic to it, plus it's possibly re-usable outside Spatial4j.

I did a quick review right now and the code appears very good but I'll want to do a more detailed comparison later.

Can you tell me how you are using this, and if there was a particular geometry that failed? It would be good to add test failures. This dateline wrapping code is not tested as much as I'd like.

[sttawm]

I've just been playing with this, along with natural earth countries. My main goals were to handle multi-geometries and arbitrary bounds. The operations appear to (now) work with all of the countries except Antarctica -- I'm still not quite sure what to do about Antarctica. The best automation I can think of is to not process rings in which shiftXPage != 0 after unwrapDateline(). Unfortunately, this type of "back-tracking" is likely to make the common case more expensive, though describing the altered coordinates can be relatively compact... What do you think about Antarctica?

By the way, a few of the tests I've added cover new functionality (i.e. they'd previously fail): testShiftedPolygon, testMultiPolygon, testGeometryCollection, testCollect. Still, there's definitely room for more coverage.

[sttawm]

As a kind-of proof of concept, I've added logic to undo some detected failures (i.e. for Antarctica). A relatively inexpensive ShiftHistory is kept, and ShiftHistory.undo() is invoked if ever a non-closed LinearRing is caused. This is reflected in the tests testSphericalRingAKAAntarctica and testSegementizedSphericalRingAKAAntarctica (Clearly I'm not sure what to call such a shape). At the moment, this behavior can be suppressed via the DETECT_AND_UNDO_BAD_SHIFTS flag.

By the way, I've managed to clobber some of your formatting :( On the other hand, I've added some tests.

I'm not sure which direction, if any, you'd like to go with this -- some of these changes definitely affect the readability of the code, and so I'm not sure whether they'd be worth it in the end. Though perhaps most importantly, there's still an outstanding bug in the original repo for direct instances of GeometryCollection that span the dateline -- GeometryCollection.intersect() is not supported. This is one of the changes included in the first commit.

[dsmiley]

After working with you more on this, the "direction" I'd like to go with this is get it back into Spatial4j as a separate class, as you've done.

Regarding Antarctica, it occurred to me that the dateline cross tracking that is currently done would result in an one extra cross that isn't balanced by a cross from the other direction. I haven't yet worked out how to leverage that information to produce an appropriate clipped polygon. This scheme would unlikely work for a LinearRing that encloses both poles, but I'm quite willing to dismiss that as a limitation.

[dsmiley]

Regarding handling direct instances of GeometryCollection, that class doesn't handle some of the relation operations -- I forget which. It's critical for how Spatial4j is typically used. So in Spatial4j I skirted that once ShapeCollection came into existence, which is a substitute for a multi-anything. Spatial4j has it's "Shape" abstraction whereas JTS has its "Geometry".

FYI Spatial4j has it's own shape abstraction distinct from JTS for two reasons:

• JTS doesn't have a Circle, and isn't likely to either.
• JTS is still LGPL licensed, which is a problem for Apache Software Foundation projects (e.g. Lucene). Introducing an abstraction here is a way around that restriction for ASF projects.

[dsmiley]

I looked at this some more and pushed some minor changes to a new sttawm-dateline branch.

I'm not really convinced that this ShiftHistory thing is the right solution to a pole wrapping (aka spherical ring) LinearRing. What I envision is an algorithm that works something like this:

• Keep track of which pair of coordinates had the most extreme latitudes.
• at the end, if shiftXPage == 0 then all is normal (no spherical ring)
• if shiftXPage is 1 or -1 then we've got a spherical ring... (otherwise an error)
  • see which extreme latitude is closest to its pole (N/S)
  • take the point closest to its pole and insert some new coordinates...
  • first new coordinate has same X but goes directly to the pole,
  • then add 3 coordinates also at the pole but X values +120, +240, and then +360 (or the other way depending on the sign of shiftXPage). This in-effect crosses the dateline one more time to bring the effective shiftXPage back to 0.
  • then add a coordinate to go back to the coordinate we came from

[dsmiley]

I was thinking a little more about my proposed algorithm after a good night's rest. By the way, the extreme latitude tracking's purpose is to ensure you can pick a point that can be modified to take a turn to go directly to the pole, without in doing so intersect the LinearRing, which could theoretically change direction at times -- a protruding peninsula poking in an east-west direction (vs north-south). That's why the algorithm picks this particular point versus an arbitrary one.

I think there needs to be more to the algorithm. Have this extreme coordinate, the point where we (eventually) take the detour, have it be the new start of the new rewritten coordinate sequence. Note that CoordinateSequence.java is not expandable so we need to create a new one. So rotate all the points so that the sequence "starts" (and ultimately ends) here. Don't add the duplicated former start/end coordinate. Before adding the final coordinate to join end to beginning, do the coordinate insertions as previously described at the end, and go the direction needed to complete shiftXPage to 0.

In the end you have something that has been unwrapped but needs to be sliced up an union'ed -- an actual union since we want to merge the vertical seam we create between the lowest coordinate and the pole. Also, the coordinates that are between the extreme one where we take the detour to the pole, up until the next dateline cross, need to be paged to the other side of the unwrapping. This is confusing to write about; maybe I'll code it up if you don't beat me to it but I'm quite busy these days.