The Geonames code is useful IP for our codebase but it's currently too complex. LineReader is really only related to Geonames so we should merge LineReader down into GeonamesReader and maybe make use of a regex to do the parsing (or somehow improve the performance). We could also change Geoname to having a Point, rather than holding distinct latitude and longitude.

The 'Sample' IO is of no use and we should remove it.

Theres no reason to use this name shortening, it just reads badly.

I'm just going to refactor these out everywhere I see them.

We should write our own more extensible WKT Parser which we can have as standard and drop our own 'pseudo' standard language which doesn't really support anything. With our own WKT parser we don't need to require JTS in order to parse WKT, and we can make our own custom extensions for Circles and Envelopes.

Need to wrap with TopologyException with InvalidShapeException, probably within JtsGeometry constructor

com.vividsolutions.jts.geom.TopologyException: found non-noded intersection between LINESTRING ( 350.13064515844655 -70.90020898221194, 394.1403541994338 -68.48279097996054 ) and LINESTRING ( 428.9364182318401 -72.424999983632, 134.4378362928431 -64.92613597664814 ) [ (356.1244099533009, -70.57097629169705, NaN) ]
at com.vividsolutions.jts.noding.FastNodingValidator.checkValid(FastNodingValidator.java:126)
at com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:94)
at com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:59)
at com.vividsolutions.jts.operation.overlay.OverlayOp.computeOverlay(OverlayOp.java:170)
at com.vividsolutions.jts.operation.overlay.OverlayOp.getResultGeometry(OverlayOp.java:127)
at com.vividsolutions.jts.operation.overlay.OverlayOp.overlayOp(OverlayOp.java:66)
at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.getResultGeometry(SnapIfNeededOverlayOp.java:62)
at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.overlayOp(SnapIfNeededOverlayOp.java:25)
at com.vividsolutions.jts.geom.Geometry.union(Geometry.java:1361)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.unionActual(CascadedPolygonUnion.java:369)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.unionOptimized(CascadedPolygonUnion.java:293)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.unionSafe(CascadedPolygonUnion.java:274)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.binaryUnion(CascadedPolygonUnion.java:212)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.binaryUnion(CascadedPolygonUnion.java:218)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.binaryUnion(CascadedPolygonUnion.java:193)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.unionTree(CascadedPolygonUnion.java:139)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.reduceToGeometries(CascadedPolygonUnion.java:243)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.unionTree(CascadedPolygonUnion.java:137)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.reduceToGeometries(CascadedPolygonUnion.java:243)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.unionTree(CascadedPolygonUnion.java:137)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.reduceToGeometries(CascadedPolygonUnion.java:243)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.unionTree(CascadedPolygonUnion.java:137)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.union(CascadedPolygonUnion.java:127)
at com.vividsolutions.jts.operation.union.CascadedPolygonUnion.union(CascadedPolygonUnion.java:73)
at com.vividsolutions.jts.operation.union.UnaryUnionOp.union(UnaryUnionOp.java:174)
at com.vividsolutions.jts.operation.union.UnaryUnionOp.union(UnaryUnionOp.java:93)
at com.vividsolutions.jts.geom.Geometry.union(Geometry.java:1435)
at com.spatial4j.core.shape.jts.JtsGeometry.unionGeometryCollection(JtsGeometry.java:334)
at com.spatial4j.core.shape.jts.JtsGeometry.(JtsGeometry.java:58)
at com.spatial4j.core.io.JtsShapeReadWriter.readShape(JtsShapeReadWriter.java:93)
at com.spatial4j.core.context.SpatialContext.readShape(SpatialContext.java:195)

ReadWriter is clumsy, Codec is cleaner.

This class isn't really related to IO, it's more a generic utility. It's a pretty important class so I think it should go to the top-level. If we end up with a lot of orphaned utilities, then we can create a util package later.

In ShapeReadWriter:
If it detects "y, x" pattern (via seeing the comma), then it assumes it's latitude, longitude because it calls readLatCommaLonPoint() which in turn validates the numbers are in degrees in the expected geodetic ranges.

Is that valid? Probably but I just want to record this. If this is valid then geo=false will also mean that you can't provide points as "y,x" you must use "x y". Seems right I guess.

I think com.spatial4j.core.query.* belongs in Lucene spatial. It's not used by any of the rest of Spatial4j, yet it's tightly related to the concept of querying which is Lucene spatial's business, and is not the business of Spatial4j.

(Chris Male agrees)

Not available LICENSE file in source directory structure
Please. Added license and copyright notice.
the fedora pakaging guideline is very strictly precise about this problem
https://fedoraproject.org/wiki/Packaging:LicensingGuidelines?rd=Packaging/LicensingGuidelines#License_Text
thanks
regards

I'd like to be able to interpolate a pair of adjacent points geodetically by adding a point at the place along the geodetic path that maximizes the distance away from the Euclidean straight-line path. And I'd like to know what that distance delta is, so an algorithm can either decide to add a point or not to. With this capability, I could take a polygon or line string and densify it to configurable geodetic distance tolerances.

AbstractDistanceCalculator doesn't add anything except redirecting distance(Point, Point) to distance(Point, double, double).

Now that we have reusable Points, we should remove distance(Point, double, double) and just keep distance(Point, Point) (it reads alot better) and remove AbstractDistanceCalculator

Spatial4j already has one via JTS but it would be nice to not need the JTS dependency.

Ideally add dateline cross support, akin to how I've done it with JTS. That algorithm may be too complicated and rely on too many sophisticated JTS features, so a simpler implementation could be devised, like one that shifts/pages the query shape across an un-rolled polygon that goes out of geo bounds. JtsGeometry instead slices and shifts the poly after unrolling.

Encode Geo-hashes with Precision

By looking at the Earth shape, one recognizes the size of geohash cells shrinks by moving away from the equator along an arbitrary latitude. In other words the radius depends on the latitudinal value. In cases where a user should able to define a precision he needs, this fact can be used to reduce the length of generated hashes. Also a precision value is a reasonable alternative to the currently used maxtreelevel value, used in geohash implementations.

An Example

The geohash 7zzzzzz refers to a geohash cell latlon1~(-0.00137, -0.00137) to latlon2=(0, 0) near the equator. The distance between these point corresponds to ~216.19656m. A geohash cell at a pole gzzzzzz with the same hash length refers to a cell with a size up to ~152.87406m. If i.e. a precision of 200m is accurate enough to encode geo-positions one can use hashes of length 8 for points between the latitudes -32.4837° and +32.4837° and geohashes of length 7 otherwise.

Be able to specify the JTS precision model.
http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/geom/PrecisionModel.html

Lucene spatial might want to initialize it with a number of decimal places consistent with the level of detail indexed.

It should be possible to take polygons that wrap a pole and process the points so that JTS is happy with it and that it covers the same area. We've got dateline support coordinate pre-processing already.

At the very least we should drop '_' from the middle. I thought we came up with a better name?

Shape: double getArea(SpatialContext ctx); -- kinda kludgy in hindsight now. The fact that the semantics vary depending on ctx being null or not is the big issue. A shape always has a ctx now so it's odd to pass one in.

Perhaps a separate AreaCalculator class could know how to calculate the area for most/all classes, and wether geo or not. I've somewhat tried to keep non-trivial mathematical operations (e.g trigonometry) out of the shapes and into the distance-calculator class / DistanceUtils. The tricky thing is that the non-geo area is needed for JtsGeometry (geo) when it estimates its area against the area of the bounding box.

A possible solution is having static getArea(shape) methods on various classes, in addition to the instance method declared on Shape. The instance method will usually do a simple one-liner to the appropriate static method.

No need for it to have an entire package to itself.

Personally I'd like to see a conditional way to force all polygons valid (to "be generous in what you accept"). There's currently a TODO in JtsGeometry.java but I think this fudging should probably go above the dateline check. Something as simple as the following works for me:

// Conditionally force valid polygons
If (shouldForceValidPolygons && geom instanceof Polygon && !IsValidOp.isValid(geom)) {
    geom = geom.convexHull(); // or even: geom = geom.getEnvelope();
}

// NOTE: All this logic is fairly expensive. There are some short-circuit checks though.
if (ctx.isGeo()) {...

The best way to punt that switch up to the user? I'm not sure.

See https://issues.apache.org/jira/browse/SOLR-4879
This appears to be a bug in JtsGeometry.unwrapDateline(LineString) in which "prevX" is not updated to be "thisX" at the end of the for loop.

When two shapes are equal, the shape.relate(otherShape) method can ambiguously return either Contains or Within. If the caller wants to know specifically if the relationship is Contains (or Within) it can test to see if they are equal if relate() returns Within (or Contains).

Once we introduce aggregate shapes (e.g. ShapeCollection), the aforementioned equality test isn't good enough because the ShapeCollection.relate() doesn't know if the caller prefers Within or Contains. And that's the problem.

One approach taken in SpatialOpRecursivePrefixTreeTest in Lucene spatial is a ShapePair class that has a boolean bias flag to prefer Contains or Within first. It looks something like this:

    private SpatialRelation relateApprox(Shape other) {
      if (biasContainsThenWithin) {
        if (shape1.relate(other) == CONTAINS || shape1.equals(other)
            || shape2.relate(other) == CONTAINS || shape2.equals(other)) return CONTAINS;

        if (shape1.relate(other) == WITHIN && shape2.relate(other) == WITHIN) return WITHIN;

      } else {
        if ((shape1.relate(other) == WITHIN || shape1.equals(other))
            && (shape2.relate(other) == WITHIN || shape2.equals(other))) return WITHIN;

        if (shape1.relate(other) == CONTAINS || shape2.relate(other) == CONTAINS) return CONTAINS;
      }

      if (shape1.relate(other).intersects() || shape2.relate(other).intersects())
        return INTERSECTS;//might actually be 'CONTAINS' if these 2 are adjacent
      return DISJOINT;
    }

Another possible approach (not mutually exclusive) is to establish a protocol in which the more "complex" shape (defaulting to the current shape, 'this', when both shapes are the same type) will always favor 'Contains'. Then if the caller prefers a bias of Within, it can just flip the who relates to who call. This isn't a complete approach that addresses all theoretical use cases, but known cases in Lucene spatial for example could work with this.

Another possible approach is to add a shape.hasRelation(relation, Shape other):boolean method. This would also give the potential for optimization because the implementation can focus on a yes-no answer instead of returning one of multiple possible enum values. However if the caller needs to know if it's Within OR Intersects OR ... (i.e. multiple conditions) then this optimization rationale evaporates.

It's a little messy that you'd need to extend SpatialContext (a very expert thing) in order to use a different parser. What if you wanted to support multiple formats? I think ShapeReadWriter should be standalone.

The "latitude,longitude" format is popular but the "Y,X" order only makes sense when the numbers are latitude and longitude (I think). If geo=false then the coordinates aren't latitudes & longitudes, and it should parse in "X,Y" order instead. This would be a breaking change and might warrant a config boolean. Using a space is always "X Y" order no matter what. I welcome feedback.

By the way, arguably Spatial4j should only worry about WKT parsing and this code might move elsewhere (e.g. Lucene spatial / Solr). But it's here now.

Javadocs should be reviewed and added on all non-test classes. On these classes, non-private methods should be documented, unless they are trivially determined from the method name (e.g. getter/setter).

JtsSpatialContext.getGeometryFrom(shape) doesn't support dateline crossings for rectangle and circle. This condition won't appear for Lucene's RecursivePrefixTreeFilter but it might for the Jts strategy Ryan wrote.

It shouldn't be hard.

The correct code is this:

  /**
   * Return the longest geohash length that will have a width & height >= specified arguments.
   */
  private static int lookupHashLenForWidthHeight(double lonErr, double latErr) {
    //loop through hash length arrays from beginning till we find one.
    for(int len = 1; len <= GeohashUtils.MAX_PRECISION; len++) {
      double latHeight = hashLenToLatHeight[len];
      double lonWidth = hashLenToLonWidth[len];
      if (latHeight < latErr && lonWidth < lonErr)
        return len;
    }
    return GeohashUtils.MAX_PRECISION;
  }

I'd really appreciate support for LineString shapes.

This is extremely complex code just to parse latitude, longitude. We should simplify it and put it where it belongs (if we even have a need for it).

Add a Shape.getArea(distCalc) that does a decent try at estimating the area, considering geospatial matters if a geo context.

See failing test:

@Test
public void testDateLine() throws ParseException {
    WKTReader wktReader = new WKTReader(JtsSpatialContext.GEO.getGeometryFactory());
    Geometry poly = wktReader.read("MULTIPOLYGON (((100 50, -100 50, -100 -50, 100 -50, 100 50)))");

    JtsGeometry polyShape = new JtsGeometry(poly, JtsSpatialContext.GEO, true);
    JtsPoint ptShape = new JtsPoint(JtsSpatialContext.GEO.getGeometryFactory().createPoint(new Coordinate(0, 0)), JtsSpatialContext.GEO);

    SpatialRelation spatialRelation = polyShape.relate(ptShape);
    assertEquals(SpatialRelation.INTERSECTS, spatialRelation);
}

Probably has to do with pole wrap?

This has been talked about a little backwards and forwards, I think it's time to move forward with this and I want it to be a blocker for 0.4.

Having isGeo really breaks OOP since it exposes an internal implementation detail. Any code that has to do X when isGeo is true and Y when its not, should be redefined so it can be extended instead. We should then provide extensions for the common scenarios.

We are not removing Cartesian support, instead we are simply making Spatial4j more open to alternative coordinate systems in the future.

WKTShapeParsers should be able to read WKT strings that contain:

• Z and/or M values
• optional Z/M/ZM flags (as defined by the latest OGC Simple Feature Access specification)

At present I have no requirement for the Z and M values to be used - they can be discarded.

It's a mix of badly formatted code, bad variable names, too many comments to be readable, calcBoxByDistFromPt_latHorizAxisDEG, Shapes are used but never Points (always lat, lon as separate doubles), some major methods aren't even used and it's impossible to tell what's been tested by TestDistances (which seems to double as both a test for DistanceUtils and for DistanceCalculators).

Ideally most of the distance methods would be moved to their Calculators. Any distance calculations directly used by multiple consumers should be re-evaluated to see if the consumers should be using Calculators instead.

A geohash grid square becomes increasingly skinny as it gets closer to a pole. When geohashes used as an encoding for shape coverage (e.g. Lucene spatial's Geohash based SpatialPrefixTree), this is a problem because it doesn't scale. We could add a boolean flag to GeohashUtils when it encodes a point such that certain extreme longitudes don't get split in half like they normally would.

https://issues.apache.org/jira/browse/LUCENE-5056
(and see attached pic too)

Support should be added for the following WKT syntax. I don't think it's defined in any standard, but several existing GIS libraries/systems already support this syntax (including PostGIS and Geotoolkit).

BOX2D(-180.0 -90.0, 180.0 90.0)

Currently SpatialContext instantiates fresh instances.

spatial4j version: 0.3
jts version: 1.13

Given a circle with the center at {x: 0, y: 0}, and radius of 1, we expect that the max and min values for X and Y are 1 and -1 respectively. However the code produces a "circle" with the radius value as its diameter! Also its center x and y values are offset by half the radius.

Circle circle = jtsContext.makeCircle(0, 0, 1);
Geometry geometry = jtsContext.getGeometryFrom(circle);
System.out.println(geometry);

Produces (commas converted to new lines for better readability):
POLYGON((1 0.5
0.9990133642141358 0.5313952597646567
0.996057350657239 0.5626666167821521
0.9911436253643444 0.5936906572928623
0.9842915805643155 0.6243449435824274
0.9755282581475768 0.6545084971874737
0.9648882429441257 0.684062276342339
0.9524135262330098 0.7128896457825363
0.9381533400219317 0.7408768370508576
0.9221639627510075 0.7679133974894983
0.9045084971874737 0.7938926261462366
0.8852566213878945 0.8187119948743449
0.8644843137107058 0.8422735529643444
0.8422735529643444 0.8644843137107058
0.8187119948743449 0.8852566213878946
0.7938926261462365 0.9045084971874737
0.7679133974894983 0.9221639627510075
0.7408768370508576 0.9381533400219318
0.7128896457825363 0.9524135262330098
0.684062276342339 0.9648882429441257
0.6545084971874737 0.9755282581475768
0.6243449435824273 0.9842915805643155
0.5936906572928623 0.9911436253643444
0.5626666167821521 0.996057350657239
0.5313952597646566 0.9990133642141358
0.4999999999999999 1
0.4686047402353433 0.9990133642141358
0.4373333832178478 0.9960573506572389
0.4063093427071376 0.9911436253643443
0.3756550564175726 0.9842915805643155
0.3454915028125262 0.9755282581475768
0.315937723657661 0.9648882429441257
0.2871103542174637 0.9524135262330098
0.2591231629491423 0.9381533400219317
0.2320866025105016 0.9221639627510074
0.2061073738537635 0.9045084971874737
0.1812880051256551 0.8852566213878946
0.1577264470356556 0.8644843137107057
0.1355156862892942 0.8422735529643443
0.1147433786121053 0.8187119948743448
0.0954915028125263 0.7938926261462367
0.0778360372489925 0.7679133974894983
0.0618466599780682 0.7408768370508576
0.0475864737669902 0.7128896457825362
0.0351117570558743 0.6840622763423388
0.0244717418524232 0.6545084971874735
0.0157084194356845 0.6243449435824274
0.0088563746356556 0.5936906572928623
0.0039426493427611 0.562666616782152
0.0009866357858642 0.5313952597646565
0 0.4999999999999998
0.0009866357858642 0.4686047402353433
0.0039426493427611 0.4373333832178479
0.0088563746356557 0.4063093427071376
0.0157084194356845 0.3756550564175725
0.0244717418524232 0.3454915028125262
0.0351117570558744 0.3159377236576608
0.0475864737669903 0.2871103542174637
0.0618466599780682 0.2591231629491423
0.0778360372489925 0.2320866025105016
0.0954915028125264 0.2061073738537633
0.1147433786121055 0.181288005125655
0.1355156862892942 0.1577264470356556
0.1577264470356557 0.1355156862892942
0.1812880051256552 0.1147433786121053
0.2061073738537634 0.0954915028125263
0.2320866025105018 0.0778360372489924
0.2591231629491424 0.0618466599780682
0.2871103542174639 0.0475864737669901
0.3159377236576611 0.0351117570558743
0.3454915028125262 0.0244717418524232
0.3756550564175728 0.0157084194356844
0.4063093427071377 0.0088563746356556
0.4373333832178482 0.0039426493427611
0.4686047402353434 0.0009866357858642
0.4999999999999999 0
0.5313952597646568 0.0009866357858642
0.5626666167821521 0.0039426493427611
0.5936906572928625 0.0088563746356557
0.6243449435824274 0.0157084194356845
0.6545084971874736 0.0244717418524232
0.6840622763423392 0.0351117570558744
0.7128896457825363 0.0475864737669902
0.7408768370508578 0.0618466599780683
0.7679133974894984 0.0778360372489925
0.7938926261462369 0.0954915028125265
0.818711994874345 0.1147433786121055
0.8422735529643444 0.1355156862892942
0.8644843137107059 0.1577264470356559
0.8852566213878947 0.1812880051256552
0.904508497187474 0.2061073738537637
0.9221639627510076 0.2320866025105018
0.9381533400219317 0.2591231629491423
0.9524135262330098 0.2871103542174639
0.9648882429441257 0.315937723657661
0.9755282581475768 0.3454915028125266
0.9842915805643155 0.3756550564175727
0.9911436253643444 0.4063093427071376
0.996057350657239 0.4373333832178481
0.9990133642141358 0.4686047402353434
1 0.5))

Hi,

Following the instructions in the spatial4j-demo/README.txt, I executed this:

mvn clean install

At the very end, this was logged:

[ERROR] Failed to execute goal on project spatial4j-demo: Could not resolve dependencies for project com.spatial4j:spatial4j-demo:war:0.2-SNAPSHOT: The following artifacts could not be resolved: org.apache.lucene:lucene-core:jar:4.0-SNAPSHOT, org.apache.lucene:lucene-queries:jar:4.0-SNAPSHOT, org.apache.lucene:lucene-analyzers-common:jar:4.0-SNAPSHOT, org.apache.solr:solr-core:jar:4.0-SNAPSHOT: Failure to find org.apache.lucene:lucene-core:jar:4.0-SNAPSHOT in https://builds.apache.org/job/Lucene-Solr-Maven-trunk/lastSuccessfulBuild/artifact/maven_artifacts/ was cached in the local repository, resolution will not be reattempted until the update interval of lucene-hudson-trunk has elapsed or updates are forced -> [Help 1]

Any ideas on what I can do to get the demo to build? Looking forward to trying this out!

Thanks!

The normalizeGeomCoords field in JtsShapeReadWriter needs to be configurable. Should there be a constructor overload for this?

Also how is the normalization suppose to work?

If I have this WKT string: POINT (100.0 100.0)

spatial4j converts it to: POINT (100.0 80.0)

Which, at least to me, doesn't make sense.

It's marked with a TODO and we should do it. In situations where we would need to instantiate a SpatialContext just to create a Shape (which will probably only occur like this when bootstrapping the Context), we should just use RectangleImpl.

We should probably be using JTS's PreparedGeometry. A benchmark that creates a polygon, prepares it, then intersects it with a couple thousand rectangles would uncover the benefits of doing so or not.

I've noticed it's a common error in Spatial4j to specify a rectangle using a Polygon in CW order points. We can add a configuration flag such that the current behavior is in effect or one in which a < 180 longitude check occurs.

Spatial4j doesn't support non-subclassed JTS GeometryCollection because relate() fails. Spatial4j's new ShapeCollection could be a substitute.

At a minimum, the JTS polygons should be dateline aware, even if they aren't pole aware. It can assume Mercator projection and thus the lines between the points can be plotted straight on the Lat-Lon based cartesian plane instead of great-circle-distance.

We've already got a BufferedLineString but it isn't geodetic.

A geodetic version could be implemented structurally similarly: It could be an aggregate of buffered lines. And each buffered line is the intersection of a perpendicular pair of infinite lines that are buffered. An infinite line on a sphere is a complete ring around the globe that cuts it in half. So most of the work here would be re-imagining the InfBufLine class in a geodetic way; the rest should hopefully more or less fall into place, maybe even re-using code after some refactoring (but don't worry about re-use at the moment as it may be distracting).

404 : http://spatial4j.github.com/
a template: http://spatial4j.github.com/spatial4j/

In addition it would be good to publish javadocs.

There is common behaviour, particularly around identity (equals and hashcode) that needs to be shared amongst Shape implementations. All Rectangles, no matter how they are implemented, should be considered equal for example. Currently this is solved by having static equals and hashcode methods which impls can share. A cleaner way is to use abstract classes to control the common behaviour.

There is some concern from David that using abstract classes prevents a Shape impl extending a JTS Geometry for example, and implementing a Shape interface. I believe in these instances it is best to wrap the JTS Geometry rather than extend it.