locationtech/jts

The JTS Topology Suite is a Java library for creating and manipulating vector geometry.

jts's Issues

GeometryPrecisionReducer can produce empty geometry

When using the GeometryPrecisionReducer, the geometry can collapse to an invalid result, which is then "fixed" with the .buffer(0) trick.
This can in some cases - and quite without warning - result in an empty geometry. (See https://sourceforge.net/p/jts-topo-suite/bugs/33/ or https://sourceforge.net/p/jts-topo-suite/mailman/message/29504850/ for an old mention of the problem).

This is a dangerously surprising behavior. I am aware that doing a more robust fixing of invalid geometries is a quite complex problem, but without it, the GeometryPrecisionReducer should at least come with a very big warning sign about this behavior in the documentation.

(This is somewhat related to #87, in the need for an automagic "make valid" function).

Shorten the jar-with-dependencies name.

I believe jar-with-dependencies is a default profile/type in the Maven assembly plugin. For this issue, we'll shorten the name as possible/appropriate.

Create SoftReference in PackedCoordinateSequence.Double constructor

Double(Coordinate[] coordinates, int dimension) {
...
this.coordRef = new SoftReference(coordinates);
...
}

Geometry.Distance() allocates unnecessary arrayList

The DistanceOp class makes use of the PolygonExtractor class, which makes an empty array to pass around to collect pieces of the geometry to calculate the distance between, but this is never used if there are no polygons in the distance calculation. This may seem minor but the distance operation is very basic and in some processing situations you may need to make millions of distance calculations; in my specific case these allocations caused the peak memory use of my program to increase from 2GB to 2.5GB. I think the DistanceOp class could be refactored to use more specific, optimized code for specific types of input geometry, rather than the current highly generalized approach which assumes the worst case of two multi-polygons and only afterward narrows down to the specific geometry types involved.
Another approach might be to refactor the PolygonExtractor into an iterator, rather than copying the polygon parts into a new list, it would allow iteration over the parts in-place, requiring less memory allocation and copying.

Information about license header is missing

The guidelines for contributing to this repository are lacking information that all source code files should have a license header and especially how it should look like.

unexpected intersection result

Hi,
i've computed intersection of two polygons
POLYGON ((3.166572116932842 48.5390194687463, 3.166572116932842 50.470470727186765, 4.180930086918854 50.470470727186765, 4.180930086918854 48.5390194687463, 3.166572116932842 48.5390194687463))
POLYGON ((2.152214146946829 50.470470727186765, 18.381941666723034 19.567250592139274, 2.390837642830135 49.228045261718165, 2.152214146946829 50.470470727186765))
which have a very small area in common if any, but the result was whole first polygon.

code

import com.vividsolutions.jts.geom.*;
import com.vividsolutions.jts.geom.impl.CoordinateArraySequence;

public class IntersectTest {
    static GeometryFactory factory = new GeometryFactory();

    public static final Polygon p1 = new Polygon(new LinearRing(new CoordinateArraySequence(new Coordinate[]{
                new Coordinate(3.166572116932842, 48.5390194687463),
                new Coordinate(3.166572116932842, 50.470470727186765),
                new Coordinate(4.180930086918854, 50.470470727186765),
                new Coordinate(4.180930086918854, 48.5390194687463),
                new Coordinate(3.166572116932842, 48.5390194687463),
    }), factory), null, factory);
    public static final Polygon p2 = new Polygon(new LinearRing(new CoordinateArraySequence(new Coordinate[]{
        new Coordinate(2.152214146946829, 50.470470727186765),
                new Coordinate(18.381941666723034, 19.567250592139274),
                new Coordinate(2.390837642830135, 49.228045261718165),
                new Coordinate(2.152214146946829, 50.470470727186765),
    }), factory), null, factory);

    public static void main(String[] args) {
        Geometry intersection = p1.intersection(p2);
        System.out.println("p1 in p2 " + intersection.equalsExact(p1));
    }
}
// output: p1 in p2 true

Is this an incorrect behavior?
jts-core 1.14
image of points:

Published Validation Suite

Was previously available at http://www.vividsolutions.com/jts/tests/index.html but no longer. Perhaps it can be published here on gh-pages?

Request for Maven Central publish

I would love to see future versions published to Maven Central under the org.locationtech namespace.

Feature suggestion: RadialDistanceSimplifier

Hi, I posted the same enhancement request here:
NetTopologySuite/NetTopologySuite#142
But I was told I should post it here or in the mailing list.
In short, a very simple algorithm to simplify a line according to distance between points.
.Net code can be found there, I'm not a very experienced Java developer so I don't really think I should do a pull request to this repository, having said that, It would be nice to get this :-)

found non-noded intersection

I posted the following problem at NetTopologySuite and was instructed to post the issue here because this also wasn't working in JTS.

I unioned the polygons from Suchfelder.zip which resulted in res2.

res2 tells me it is valid although it doesn't look valid at all. It contains lines and triangles that look into the polygon area. I don't think the triangle should exist as it lies completely within the polygon.

Trying to get the difference from res and res2 results in a non-noded intersection exception.

So is res2 really valid or does the difference function work incorrectly?

    var reader = new WKTReader();

            var res = reader.Read("MULTIPOLYGON (((-6254384.9272019733 -2428784.4316727975, -6254448.2889524475 -2428784.4324241709, -6254399.1165902149 -2428657.1297944547, -6254384.9272019733 -2428784.4316727975)), ((-6254289.7647291981 -2428374.0280918181, -6254076.9438697845 -2428906.9316744655, -6254243.0436896412 -2428910.1951122279, -6254417.483366685 -2428913.62240691, -6254463.6874999283 -2428837.6061908188, -6254325.4337456506 -2428846.8321458441, -6254362.340771623 -2428561.9206525073, -6254289.7647291981 -2428374.0280918181)), ((-6254073.3327726927 -2428940.0660867151, -6254140.5877170712 -2429108.987212894, -6254344.0507978722 -2429034.4355382724, -6254399.2597350832 -2428943.6043894938, -6254073.3327726927 -2428940.0660867151)), ((-6254753.3077126574 -2428361.1156448247, -6254698.72562374 -2428213.1250561425, -6254332.4671062678 -2428330.1534979446, -6254488.1171720289 -2428797.4138724417, -6254753.3077126574 -2428361.1156448247)), ((-6254004.2787381727 -2428950.0691508525, -6254318.7635007482 -2428263.0369477733, -6254122.8733536266 -2428231.3153878264, -6253776.8295307625 -2428881.4327149931, -6251457.7266220115 -2428679.5463844533, -6251326.4963204153 -2429188.8054935131, -6253531.782834392 -2429376.9298687372, -6254004.2787381727 -2428950.0691508525)))");
            Assert.AreEqual(true, res.IsValid);

            var res2 = reader.Read("MULTIPOLYGON (((-6254444.050800845 -2428784.4323739046, -6254448.2889524437 -2428784.4324241676, -6254444.0508008441 -2428773.4602475408, -6254438.6335666114 -2428759.4355366551, -6254428.97697854 -2428734.4355366575, -6254419.3203904629 -2428709.4355366589, -6254419.0508008488 -2428708.7375944532, -6254409.6638023909 -2428684.4355366575, -6254400.0072143227 -2428659.435536663, -6254399.1165902093 -2428657.1297944514, -6254398.85958637 -2428659.4355366565, -6254396.07302336 -2428684.4355366593, -6254394.0508008441 -2428702.5781598496, -6254393.2864603419 -2428709.4355366584, -6254390.499897331 -2428734.4355366556, -6254387.7133343164 -2428759.4355366491, -6254384.9272019733 -2428784.4316727975, -6254394.0508008422 -2428784.4317809842, -6254419.0508008394 -2428784.4320774451, -6254444.050800845 -2428784.4323739046)), ((-6254444.0507973628 -2428859.4355378593, -6254444.0507973656 -2428869.9129937063, -6254450.4191986173 -2428859.43553786, -6254463.6874999283 -2428837.6061908188, -6254444.0507973628 -2428838.9165880294, -6254419.0507973675 -2428840.58488903, -6254394.0507973628 -2428842.253190022, -6254369.0507973591 -2428843.9214910129, -6254344.0507973544 -2428845.5897920118, -6254325.4337456506 -2428846.8321458441, -6254327.0395844625 -2428834.4355378533, -6254330.2780485861 -2428809.4355378528, -6254333.5165127087 -2428784.4355378593, -6254336.7549768286 -2428759.4355378575, -6254339.993440954 -2428734.4355378621, -6254343.231905072 -2428709.4355378593, -6254344.0507973712 -2428703.1139278188, -6254346.4703691984 -2428684.4355378631, -6254349.70883332 -2428659.4355378686, -6254352.9472974436 -2428634.4355378672, -6254356.1857615709 -2428609.4355378728, -6254359.42422569 -2428584.4355378705, -6254362.340771623 -2428561.9206525073, -6254361.3808624921 -2428559.4355378714, -6254351.7242744239 -2428534.4355378784, -6254344.0507973786 -2428514.5696261721, -6254342.0676863473 -2428509.4355378719, -6254332.4110982772 -2428484.435537877, -6254322.7545102052 -2428459.435537877, -6254319.0507973842 -2428449.846973083, -6254319.0507973833 -2428459.4355378728, -6254319.0507973805 -2428449.8469730811, -6254313.09792213 -2428434.435537878, -6254303.4413340567 -2428409.4355378794, -6254294.050797388 -2428385.124319992, -6254293.7847459819 -2428384.4355378775, -6254289.7647291981 -2428374.0280918181, -6254285.6084020734 -2428384.4355378742, -6254275.6243793406 -2428409.4355378747, -6254269.0507973833 -2428425.8957917569, -6254265.6403566087 -2428434.4355378747, -6254255.6563338693 -2428459.4355378691, -6254245.6723111346 -2428484.4355378696, -6254244.0507973777 -2428488.4958094717, -6254235.6882884027 -2428509.4355378668, -6254225.7042656615 -2428534.4355378617, -6254219.0507973675 -2428551.0958271823, -6254215.7202429362 -2428559.4355378626, -6254205.7362201922 -2428584.4355378547, -6254195.752197451 -2428609.4355378523, -6254194.0507973619 -2428613.6958449022, -6254185.7681747228 -2428634.4355378537, -6254175.7841519862 -2428659.4355378547, -6254169.0507973526 -2428676.2958626165, -6254165.8001292506 -2428684.4355378463, -6254155.8161065178 -2428709.4355378477, -6254145.8320837785 -2428734.4355378472, -6254144.050797347 -2428738.8958803294, -6254135.84806104 -2428759.4355378412, -6254125.8640383054 -2428784.4355378421, -6254119.0507973451 -2428801.49589804, -6254115.8800155725 -2428809.4355378379, -6254105.8959928416 -2428834.4355378356, -6254095.9119701013 -2428859.4355378351, -6254094.0507973349 -2428864.0959157594, -6254085.9279473675 -2428884.4355378319, -6254076.9438697845 -2428906.9316744655, -6254094.0507973265 -2428907.2677819543, -6254119.05079733 -2428907.758968187, -6254144.0507973321 -2428908.2501544147, -6254169.0507973339 -2428908.7413406391, -6254194.05079734 -2428909.2325268677, -6254204.3834856767 -2428909.4355378374, -6254219.0507973414 -2428909.7237130953, -6254243.0436896412 -2428910.1951122279, -6254244.050797346 -2428910.2148993253, -6254269.0507973451 -2428910.7060855534, -6254294.0507973488 -2428911.1972717838, -6254319.0507973544 -2428911.6884580115, -6254344.050797347 -2428912.1796442387, -6254369.0507973535 -2428912.6708304686, -6254394.05079736 -2428913.1620166982, -6254417.4833666813 -2428913.6224069092, -6254419.05079736 -2428911.0436300607, -6254420.0282270536 -2428909.4355378519, -6254435.2237128373 -2428884.4355378575, -6254444.0507973637 -2428869.9129937077, -6254444.0507973628 -2428859.4355378593)), ((-6254753.3077126583 -2428361.11564482, -6254752.6880535092 -2428359.4355383315, -6254744.050797944 -2428336.0170037593, -6254743.4675197275 -2428334.4355383296, -6254734.24698594 -2428309.4355383338, -6254725.0264521576 -2428284.4355383362, -6254719.050797943 -2428268.2335093888, -6254715.8059183694 -2428259.4355383315, -6254706.5853845831 -2428234.4355383338, -6254698.72562374 -2428213.1250561425, -6254694.0507979412 -2428214.6187758865, -6254669.0507979458 -2428222.6068796609, -6254644.050797943 -2428230.5949834352, -6254632.0311903935 -2428234.4355383315, -6254619.0507979337 -2428238.583087205, -6254594.0507979393 -2428246.5711909803, -6254569.0507979374 -2428254.5592947542, -6254553.7898433041 -2428259.4355383259, -6254544.0507979337 -2428262.5473985276, -6254519.0507979309 -2428270.5355022973, -6254494.0507979263 -2428278.5236060717, -6254475.5484962119 -2428284.4355383213, -6254469.0507979272 -2428286.5117098419, -6254444.0507979225 -2428294.4998136181, -6254419.0507979235 -2428302.4879173888, -6254397.30714911 -2428309.435538311, -6254394.0507979216 -2428310.4760211641, -6254369.0507979179 -2428318.4641249366, -6254344.0507979142 -2428326.452228711, -6254332.4671062678 -2428330.1534979446, -6254333.8935055509 -2428334.4355383092, -6254342.2213070495 -2428359.4355383092, -6254344.0507979114 -2428364.9276566892, -6254350.5491085406 -2428384.4355383068, -6254358.8769100271 -2428409.4355383008, -6254367.2047115248 -2428434.4355383045, -6254369.0507979132 -2428439.9774763263, -6254375.5325130168 -2428459.4355383017, -6254383.86031451 -2428484.435538304, -6254392.1881159982 -2428509.4355383022, -6254394.0507979095 -2428515.0272959573, -6254400.515917493 -2428534.4355383036, -6254408.8437189814 -2428559.4355383026, -6254417.1715204753 -2428584.4355383003, -6254419.0507979095 -2428590.0771155925, -6254425.4993219655 -2428609.4355382971, -6254433.8271234594 -2428634.4355382989, -6254442.1549249552 -2428659.4355382989, -6254444.0507979048 -2428665.126935224, -6254450.4827264436 -2428684.435538298, -6254458.8105279356 -2428709.4355382957, -6254467.138329424 -2428734.4355382966, -6254469.050797902 -2428740.1767548565, -6254475.4661309179 -2428759.4355382994, -6254483.7939324081 -2428784.435538291, -6254488.1171720307 -2428797.4138724436, -6254494.0507978983 -2428787.6517201238, -6254496.0056557087 -2428784.4355382938, -6254511.2011414906 -2428759.4355382947, -6254519.0507979058 -2428746.521083768, -6254526.396627279 -2428734.4355383012, -6254519.0507979058 -2428734.4355382971, -6254526.39662728 -2428734.4355382989, -6254541.5921130609 -2428709.4355382994, -6254544.05079791 -2428705.3904474066, -6254556.7875988465 -2428684.4355383022, -6254569.0507979142 -2428664.2598110475, -6254571.98308463 -2428659.4355383059, -6254587.178570414 -2428634.4355383134, -6254594.0507979151 -2428623.1291746926, -6254602.3740561949 -2428609.4355383073, -6254617.5695419768 -2428584.43553831, -6254619.0507979207 -2428581.9985383344, -6254632.7650277568 -2428559.4355383161, -6254632.7650277615 -2428559.4355383161, -6254644.0507979263 -2428540.867901979, -6254647.9605135452 -2428534.4355383152, -6254663.1559993327 -2428509.4355383157, -6254669.0507979244 -2428499.7372656157, -6254678.3514851155 -2428484.4355383227, -6254693.5469708946 -2428459.4355383213, -6254694.0507979318 -2428458.6066292617, -6254694.0507979346 -2428434.4355383264, -6254708.7424566783 -2428434.435538318, -6254719.0507979384 -2428417.4759929045, -6254723.9379424639 -2428409.4355383255, -6254739.1334282458 -2428384.435538332, -6254744.0507979393 -2428376.3453565422, -6254753.3077126583 -2428361.11564482)), ((-6254708.7424566783 -2428434.4355383241, -6254694.0507979346 -2428434.4355383264, -6254694.0507979328 -2428458.6066292622, -6254708.7424566783 -2428434.4355383241)), ((-6254399.2597350832 -2428943.6043894938, -6254394.0507978816 -2428943.5478406339, -6254394.0507978844 -2428952.1742655579, -6254399.2597350832 -2428943.6043894938)), ((-6254369.05079788 -2428993.3049019151, -6254374.4417694416 -2428984.435538277, -6254369.0507978806 -2428984.435538278, -6254374.4417694416 -2428984.4355382761, -6254389.6372552253 -2428959.4355382812, -6254394.0507978816 -2428952.1742655588, -6254394.0507978816 -2428943.5478406339, -6254369.05079788 -2428943.2764375918, -6254344.0507978778 -2428943.0050345478, -6254319.05079788 -2428942.7336315047, -6254294.0507978769 -2428942.4622284621, -6254269.0507978741 -2428942.1908254218, -6254244.05079787 -2428941.9194223764, -6254219.0507978722 -2428941.648019332, -6254194.0507978741 -2428941.3766162931, -6254169.0507978676 -2428941.1052132491, -6254144.0507978639 -2428940.8338102074, -6254119.0507978648 -2428940.5624071644, -6254094.0507978611 -2428940.2910041185, -6254073.3327726927 -2428940.0660867151, -6254081.0446049273 -2428959.4355382626, -6254090.9982066322 -2428984.4355382607, -6254094.05079786 -2428992.1025901404, -6254100.951808339 -2429009.4355382593, -6254110.9054100439 -2429034.4355382589, -6254119.0507978583 -2429054.8939312571, -6254120.859011746 -2429059.4355382561, -6254130.8126134519 -2429084.4355382607, -6254140.5877170712 -2429108.987212894, -6254144.0507978536 -2429107.718292403, -6254169.0507978592 -2429098.557948139, -6254194.05079786 -2429089.397603869, -6254207.59304438 -2429084.4355382607, -6254219.0507978648 -2429080.237259604, -6254244.0507978629 -2429071.0769153368, -6254269.0507978685 -2429061.9165710746, -6254275.8219211269 -2429059.435538271, -6254294.05079787 -2429052.7562268032, -6254319.05079787 -2429043.5958825387, -6254344.0507978722 -2429034.4355382724, -6254359.246283656 -2429009.4355382756, -6254369.05079788 -2428993.3049019151)))");
            Assert.AreEqual(true, res2.IsValid);

            Assert.DoesNotThrow(delegate { res.Difference(res2); });

IndexedPointInAreaLocator Goes Into Infinite Loop with Empty Geometry

This is issue 51 on SourceForge.

The problem is here: we only check to see if the count is 1, but for an empty list of nodes, this will always be 0.

I had a patch over at SourceForge, but looking at it again, there's a more elegant solution that doesn't penalize the common case as much:

1. In org.locationtech.jts.index.intervalrtree, add another subclass of IntervalRTreeNode called something like IntervalRTreeNullNode whose query method is a no-op.
2. Right at the top of buildRoot, check to see if leaves has a size() of 0. If it does, return a new instance of IntervalRTreeNullNode.

I signed a CLA, but I think it might be faster if I just point these things out, since I'm having difficulties setting up my local environment to do development of JTS.

Reorganize JTS package structure?

The JTS package structure is showing its age. For instance:

• the operation package is not a pattern which has been continued, and it is inconsistent (e.g. linemerge)
• there are quite a few top-level packages which are related and could be grouped for more clarity (e.g. graphs and algorithms

The following is a proposal for a reorganized package structure which has the advantages:

• better indicates the functional nature of the subpackages
• makes the packaging more consistent
• reduces the number of top-level packages

It is obviously a breaking change. The upcoming release of the first LT release seems like a good time to do this.

Question: is this such a major change that it should trigger a move to a JTS 2 version number?

• algorithm
  • boundary
  • buffer
  • densify
  • dissolve
  • distance
  • distance3d
  • hull
  • linemerge
  • locate
  • match
  • overlay
  • polygonize
  • predicate
  • relate
  • simple
  • simplify
  • triangulate
  • union
  • valid
• geom
  • impl
  • linearref
  • precision
  • prep
  • util
• graph
  • edgegraph
  • geomgraph
  • planargraph
• index
• io
  • awt
  • gml2
  • kml
• math
• noding
• shape
  • fractal
  • random
• util

Is there some kind of makeValid function for converting invalid polygons into multipolygons?

Hello all,

I'm working with a complex set of generated polygons, and I've been searching for a consistent way to transform invalid polygons into sets of valid ones. So far I've found this SO post, and seen that the version of JTS that Geotools is using has a makeValid function that seems to work okay but interacts somewhat oddly with holes. I've also tried the polygon.buffer(0); trick, but that seems sub-optimal for the reasons outlined in the SO post above.

Is there a recommended approach to this? I'm pretty new to JTS in general, so any pointers in the right direction would be appreciated. Thanks!

Perf: avoid Envelope allocation in MonotoneChainEdge

  // these envelopes are created once and reused
  Envelope env1 = new Envelope();
  Envelope env2 = new Envelope();
...
    env1.init(p00, p01);
    env2.init(p10, p11);
    if (! env1.intersects(env2)) return;

Can be replaced with

if (!Envelope.intersects(p00, p01, p10, p11)) return;

Inconsistent behavior when querying Quadtree with null envelope

An empty Quadtree can be happily queried with a null envelope, but a non-empty Quadtree will throw a NullPointerException in the same case. For example:

Quadtree qt = new Quadtree();
qt.query(null); // OK
qt.insert(new Envelope(0, 10, 0, 10), "some data");
qt.query(null); // NPE

It seems like a query with a null Envelope should either always return nothing (I'd lean towards this), or always throw an Exception.

Buffering a simple geometry produces a complex geometry.

The attached file contains a simple polygon geometry in WKT format. When buffering this polygon with distance = 400 and quadrantSegments = 2, a complex geometry is returned.
The majority of the shape is buffered correctly, but there are two tiny triangle fragments outside the buffered area on the bottom-left edge which are unexpected. Similar results are seen on other comparable input geometries.

poly3.txt

JTS 1.14 Regression: CoordinateArraySequenceFactory handling of dimension 1

Working on updating GeoTools to use JTS 1.14 (see geotools/geotools#1665) and have run into a regression in the following:

    double[] ord = new double[] { x };
    int dim = 1;
    CoordinateSequence cs = csFact.create(n, dim);

This should produce a coodinate sequence with dimension 1, but it produces a coordinate sequence with dimension 3.

The JTS 1.14 implementation is:

  public CoordinateSequence create(int size, int dimension) {
    if (dimension > 3)
      dimension = 3;
      //throw new IllegalArgumentException("dimension must be <= 3");
    // handle bogus dimension
    if (dimension < 2)
    	// TODO: change to dimension = 2  ???
      return new CoordinateArraySequence(size);
    return new CoordinateArraySequence(size, dimension);
  }

You can see the return new CoordinateArraySequence(size); fails to pass in the dimension.

This is a regression, in JTS 1.13 the code was as follows:

  public CoordinateSequence create(int size, int dimension) {
    if (dimension > 3)
      throw new IllegalArgumentException("dimension must be <= 3");
    return new CoordinateArraySequence(size, dimension);
  }

Refactor TestRunner & XML tests into new module test

Makes XML tests more obvious and easier to run in Maven.

Will include Junit test to run standard XML tests

Move FAQ to GitHub Pages

There was valuable information in the FAQ hosted at the now defunct tsusiasoftware.net. The wayback machine to the rescue: https://web.archive.org/web/20160123233029/http://tsusiatsoftware.net:80/

This FAQ should be resurrected and placed into the GitHub pages.

Under the Documentation header of the main page, there should be a link to the FAQ. The FAQ should be a new page with the same style as the current GitHub pages. Bonus points for adding the proper links from the header down to each individual question.

This site is a GitHub Project Page, and the site's code is in the gh-pages branch of this repository. Please make a pull request to that branch for this feature.

[Docs] FAQ Code styling

From @dr-jts:

In the FAQ, style the JTS Javadoc references to make them look more like "code".

The simple way to do this is to wrap them in [tt] tags. Even better is to wrap them in a [span] with a CSS class 'javadoc' defined in the document.

JTS TestBuilder hits stack overflow when viewing Test Case Text for XML test case

Steps to reproduce:

• In JTS TestBuilder load an XML test case file
• Invoke View/Test Case Text
• App gets stack overflow error

Cause is unexpected overloaded method resolution at https://github.com/locationtech/jts/blob/master/modules/app/src/main/java/org/locationtech/jtstest/testbuilder/model/XMLTestWriter.java#L133

Fix is to avoid overloading method name by renaming private method.

Robustness failure in VoronoiDiagramBuilder

The following geometry (a 7-point MultiPoint) causes VoronoiDiagramBuilder to throw an exception, even with a very large tolerance value relative to the scale of the input points (such as 0.1).

01040000000700000001010000000f8b33e3d97742c038c453588d0423c001010000001171d6d1b45d42c06adc1693e78c22c001010000001c8b33e3d97742c062c453588d0423c00101000000afa5c71fda7742c04b93c61d8e0423c00101000000b0cddcb4b57942c026476887d7b122c00101000000e0678421dc7642c0f7736021e1fb22c00101000000e32fd565018d42c0c7ea1222167c22c0

Originally reported in PostGIS at https://trac.osgeo.org/postgis/ticket/3447

Move JTS FAQ into repo as md file

Current version is here: http://tsusiatsoftware.net/jts/jts-faq/jts-faq.html

Change Geometry.equals(Geometry) to have equalsExact semantics

A long-standing confusion in the JTS Geometry class is that Geometry.equals(Geometry) has the semantics of topological-equality, rather than exact-equality (which is more usual for Java). This impacts using JTS in collections or frameworks which rely on equals having standard Java semantics (for example, ORMs such as JPA). In most use cases for collections and containers the desire is for exact-equality semantics.

Even more confusingly, to mitigate this the method Geometry.equals(Object) was added, which has exact-equality semantics. This helps ensure that some container classes "do the right thing" of using the faster exact-equality, but it's hard to be sure they are doing this without close inspection.

Geometry.equals(Geometry) should be changed to have exact-equality semantics.

To compute topological-equality the Geometry.equalsTopo(Geometry) method can be used. The use cases for topological-equality seem to be fairly rare, so having a slightly more verbose method name should not be a problem. This causes a slight discrepancy with the standard OGC Spatial Predicate definition, but the benefits of comprehension and safety outweigh this.

When this change is made the existing Geometry.equalsExact(Geometry) method will be redundant and can be deprecated. EDIT: Geometry.equalsExact(Geometry) will be kept, since the name clearly indicates the semantics. equals will delegate to it.

NOTE that this is definitely a breaking API change.

NOTE 2: As pointed out below, this does not affect the implentation of hashCode(), which is currently appropriate for either definition of equality.

TopologyException when generating a VoronoiDiagram

To reproduce, use the following input in JTS TestBuilder and generate a plain VoronoiDiagram:

POLYGON ((14.7119 201.6703, 74.2154 201.6703, 74.2154 166.6391, 14.7119 166.6391, 14.7119 201.6703))

The error message:

com.vividsolutions.jts.geom.TopologyException : com.vividsolutions.jts.geom.TopologyException: found non-noded intersection between LINESTRING ( 44.46365 107.13560000000001, 44.46365 -1707.7211500000005 ) and LINESTRING ( 44.46365000000006 -1707.7211500000005, -1847.4122000000002 184.15470000000002 ) [ (44.46365, -1707.7211500000005, NaN) ]

Use generics for index classes?

What do people think about updating some of the index classes to use generics? It would be nice to not cast the return values from spatial index queries, etc.

Request: Alpha Shapes implementation

I came upon a problem to which Alpha Shapes (not Convex Hull) was the answer. I found this post on the GIS Stackexchange, where it was mentioned that this feature has been desired in JTS for a long time.

Is there any plan to implement it? Thank you kindly.

Where has jts-lab gone

In the sourceforge repository there is a module called jts-lab that contains SnapRoundOverlayFunctions:
https://sourceforge.net/p/jts-topo-suite/code/HEAD/tree/trunk/jts-lab/src/main/java/com/vividsolutions/jtslab/

I can't find this module and the in the current layout, has this approach been abandoned?

SpikeRemover for geometry cleaning

The result of geometry operations (intersection, difference, ...) may have sliver like artifacts.

Their LineStrings/LinearRings components can be tested for these by iterating over the defining coordinate sequence with three coordinates at a time (p0, p1, p2) and testing if the distance |p1-p2| + |p0-p2| is (nearly) the same as the distance |p0-p1|. The nearly has to be configured using a threshold.

If there is an interest, I can provide SliverRemover class and unit test for the jts-lab clean package.

Wrong assumption in CascadedPolygonUnion

Debugging an issue with CascadedPolygonUnion I found an unsafe assumption in unionUsingEnvelopeIntersection method of CascadedPolygonUnion class.

The method extracts, from 2 multipolygons, the ones that intersect an envelope and the ones that do not (disjointPolys). Then unions the intersecting ones togheter and finally combine the unioned intersecting polygons and the disjoint polygons, assuming that they would not be intersecting.

This is a wrong assumption, in that the union of the intersecting polygons may slightly move the envelope due to use of SnapIfNeededOverlayOp in Geometry.union().

Clarification on JTS license questions for downstream projects

Recent State of JTS presentation brought to light some questions from downstream projects around license change.

Downstream projects include both:

• ports: GEOS, JSTS, etc..
• use: GeoTools, GeoServer, etc ...

Q: JTS no longer uses LGPL, what does this mean for downstream projects?

License change gives downstream projects more options using a dual license approach:

• We have a BSD-3 license (permissive license than LGPL) in part to allow iOS use of the project for mobile development.
• We have an EPL license (similar permissive to LGPL with different wording around patents).

Q: But I thought LGPL and EPL do not mix? How does this effect the LGPL GEOS project?

For use of JTS by an LGPL project like GEOS:

• Please use the BSD-3 License (the BSD-3 License is compatible with the LGPL license used by GEOS)
• Long term the EPL license is being revised to work with GPL / LGPL allowing GEOS the choice of BSD-3 or EPL license.

Q: How can the LGPL GEOS program contribute fixes to JTS?

Using a contributor license agreement:

• The GEOS team should be sure to have permission (via osgeo CLA or similar) to relicense the work in question. The JTS team wants to be in position to distribute any fix as both BSD and EPL.

Q: Why do you keep saying BSD-3, I thought it was the Eclipse Distribution License (BSD-3)

The BSD-3 license used is called Eclipse Distribution License (as eclipse is the distributing organization.)

Should we would like to add a FAQ entry to handle these questions? Or just take to jts-dev email list (or [email protected] email list).

Increase spatial predicate accuracy by better DD number conversion?

A recent GEOS issue (https://trac.osgeo.org/geos/ticket/841) revealed an interesting shortcoming in the JTS orientation code. The issue is that currently in JTS the following happens:

LINESTRING ( 0 1, 1 0 ).intersects( POINT( 0.05, 0.95 ) = FALSE

Obviously this is incorrect, since mathematically the point lies exactly on the line.

The reason this happens is that JTS uses DoubleDouble (DD) extended precision arithmetic to compute the orientation test. In this case the determinant computed in the test computes as 4.1633363423443370265886187553405E-17. This is non-zero, so the point is reported as NOT on the line. The reason is that the double-to-DD conversion is currently rather crude - it simply zeroes out the lower-order bits of the converted number. This is correct in binary, but doesn't reflect the decimal situation. In fact, the conversion produces this DD value for 0.05: 0.050000000000000002775557561562891

It turns out that if the double-to-DD conversion is changed to use the decimal representation, then the determinant computes the value 0, which is 100% accurate! Even better, even for points which still have a non-zero computed determinant the value is much more accurate. E.g.

POINT ( 0.55 0.45 ) produces determinant value 3.0814879110195773648895647081358E-33

In this case, it's probably safe to use a very small tolerance value (say 10E-30) to decide that the point is effectively collinear with the line.

Unfortunately the simple approach to implementing a "decimal-friendly" DD conversion is very slow (convert to string and then to DD). There should be a faster way to do this, however.

So the questions are:

1. is this fix safe to implement?
2. is it useful?
3. it possible to implement with low impact on performance?

Invalid union result from valid polygon inputs

I found a case in which the union of two valid small polygons result in an invalid output.
NOTE I had to tweak the JTS testrunner slightly to get the HEXWKB printed in order to check for validity, I might send a PR to help with this in the future.

The XML test file can be found on https://trac.osgeo.org/geos/ticket/838 (WARNING: the test expects the invalid result, so you'll need more care to check the bug)

Clarify targeted Java version

I'm not able to find anything in the POM files or project documentation that states which version of Java is targeted by JTS. (Does Maven default to Java 5?).

ant build failed: jts/java/src does not exist.

There are no instructions in the README about building the code, but I remember ant used to work.
There is still a build.xml file but ant fails:

[strk@liz:/usr/src/jts/jts(master)] ant build
Buildfile: /usr/src/jts/jts/build.xml

BUILD FAILED
Target "build" does not exist in the project "JTS Buildfile". 

Total time: 0 seconds
[strk@liz:/usr/src/jts/jts(master)] ant
Buildfile: /usr/src/jts/jts/build.xml

props:

copy-source:

BUILD FAILED
/usr/src/jts/jts/build.xml:66: /usr/src/jts/jts/jts/java/src does not exist.

Total time: 0 seconds

WKBReader vulnerable to malformed input

The WKBReader class can be made to exhaust all system memory if it is provided with a very short but malformed WKB string. It can also throw unexpected exceptions, like NegativeArraySizeException. Malformed WKB strings are possible if the WKBReader is used incorrectly and shared across multiple threads, or if a malicious WKB string is provided by a client.

Prepared Geometry Thread Safety?

I have code that is running lots of polygon checks in parallel in separate threads. As far as I can tell there is no relationship between my threads, I am using a new GeometryFactory and PreparedGeometryFactory in each call stack. When I run the code with a single thread everything works as expected and I get the correct results. As soon as I start doing the calculation in multiple threads these intersection tests start to fail. In cases where it fails repeatedly calling the method will sometimes lead to different answers but not always. FWIW the failing boxes are usually near the edge of the polygons.

I have traced through the JTS code and I can't find anything that would explain this issue. I can't find any statics anywhere in the code I have stepped through but there must be something somewhere that is causing this issue. I am using version 1.13.

The code boils down to:

val pgeom = new PreparedGeometryFactory().create(target)
Seq(otherGeometries).foreach{ box : Envelope =>
  val canidateBox = new GeometryFactory().toGeometry(box)
   if(pgeom.covers(canidateBox)){
     // do something
  } else if(pgeom.insersects(candidate)){
    if(!pgeom.insersects(canidateBox)){
        throw new IllegalArgumentException("How can you intersect and not intersect?")
    }
  } else {
    if(pgeom.insersects(canidateBox)){
        throw new IllegalArgumentException("How can you intersect and not intersect?")
    }
  }
}

TopologyTestApp requires a GUI to run

On a unix system, running the following:

java org.locationtech.jtstest.testrunner.TopologyTestApp -files test.xml

Requires a working X connection:

No X11 DISPLAY variable was set, but this program performed an operation which requires it.
        at java.awt.GraphicsEnvironment.checkHeadless(GraphicsEnvironment.java:204)
        at java.awt.Window.<init>(Window.java:536)
        at java.awt.Frame.<init>(Frame.java:420)
        at java.awt.Frame.<init>(Frame.java:385)
        at javax.swing.JFrame.<init>(JFrame.java:189)
        at org.locationtech.jtstest.testrunner.TopologyTestApp.<init>(TopologyTestApp.java:188)
        at org.locationtech.jtstest.testrunner.TopologyTestApp.<init>(TopologyTestApp.java:174)
        at org.locationtech.jtstest.testrunner.TopologyTestApp.main(TopologyTestApp.java:213)

Perf: extend Coordinate with distanceSq and distance3DSq

This is simple optimization to avoid computing Math.sqrt during finding minimal distance.
Suggested method can be used for example in LineSegment, Triangle, InteriorPointPoint, InterirorPointLine, , LineString::equalsExact(Geometry other, double tolerance)

 public double distanceSq(Coordinate c) {
    double dx = x - c.x;
    double dy = y - c.y;
    return dx * dx + dy * dy;
  }

  public double distance3DSq(Coordinate c) {
    double dx = x - c.x;
    double dy = y - c.y;
    double dz = z - c.z;
    return dx * dx + dy * dy + dz * dz;
  }

Make PackedCoordinateSequence Serializable

Please make PackedCoordinateSequence serializable. Other implementations of CoordinateSequence are Serializable.

Thank you

Unexpected Intersection Result

Hi, while doing some innocent intersections I came upon a surprising result.

Attempted

Intersect LINESTRING (0 0, 1000 1, 2000 0, 3000 1, 4000 0) twice, once each with the following Polygons which represent (contrived) extents:

• POLYGON ((0 0, 0 2500, 2500 2500, 2500 0, 0 0))
• POLYGON ((2500 0, 2500 2500, 5000 2500, 5000 0, 2500 0))

Expected Result

LEFT INTERSECT: LINESTRING (0 0, 1000 1, 2000 0, 2500 0.5)
RIGHT INTERSECT: LINESTRING (2500 0.5, 3000 1, 4000 0)

Actual Result

LEFT INTERSECT: MULTILINESTRING ((0 0, 1000 1, 2000 0), (2000 0, 2500 0.5))
RIGHT INTERSECT: LINESTRING (2500 0.5, 3000 1, 4000 0)

I suppose no data has been lost per se, but the MultiLine result for the left intersect (where it doesn't happen with the right) is unexpected. Thoughts?

Perf: InteriorPointArea - bisector intersection with geometry

Geometry intersections = bisector.intersection(geometry);
in InteriorPointArea::addPolygon uses general intersection algorithm. We know that bisector is horizontal LineSegment. So there can be specialized algorithm for horizontal/vertical lines. INTERSECTION in OverlayOp can be improved to use segments that fits to horizontal/vertical Interval intersection from both geometries. I think that other segments/monotone chains can be omitted.
Example: Czech Republic polygon from OpenStreetMap
~80k nodes
-- following can be eliminated if we use only segments/monotone chains that intersects with horizontal line
~22k monotone chains
~44k Mark&Sweep events

Possible issues/regressions
I suppose that there can be some problems when SnapIfNeededOverlayOp fallback from OverlayOp to SnapOverlayOp.

Too many compile time dependencies?

Are these dependencies really necessary to build JTS? https://github.com/locationtech/jts/blob/master/pom.xml#L94-L117

junit is probably just for test scope and what about the oracle driver - should it be provided?

Classes that define equals need to implement hashCode()

A first pass at implementing hashCode. The one for Edge.java could be better, but it should be correct.

https://gist.github.com/schwehr/38252cdf8670d732de8260f2741df18e

--- old/java/com/vividsolutions/jts/geom/PrecisionModel.java
+++ new/java/com/vividsolutions/jts/geom/PrecisionModel.java
@@ -1,5 +1,3 @@
-
-
 /*
  * The JTS Topology Suite is a collection of Java classes that
  * implement the fundamental operations required to validate a given
@@ -37,6 +35,7 @@
 import java.io.Serializable;
 import java.util.HashMap;
 import java.util.Map;
+import java.util.Objects;
 
 /**
  * Specifies the precision model of the {@link Coordinate}s in a {@link Geometry}.
@@ -438,6 +437,12 @@
   	}
   	return description;
   }
+
+  @Override
+  public int hashCode()
+  {
+    return Objects.hash(modelType, scale);
+  }
 
   public boolean equals(Object other) {
     if (! (other instanceof PrecisionModel)) {
--- old/java/com/vividsolutions/jts/geom/util/AffineTransformation.java
+++ new/java/com/vividsolutions/jts/geom/util/AffineTransformation.java
@@ -35,6 +35,8 @@
 
 import com.vividsolutions.jts.geom.*;
 import com.vividsolutions.jts.util.*;
+import java.util.Objects;
+
 /**
  * Represents an affine transformation on the 2D Cartesian plane. 
  * It can be used to transform a {@link Coordinate} or {@link Geometry}.
@@ -1080,7 +1082,14 @@
     && m11 == trans.m11
     && m12 == trans.m12;
   }
+
+  @Override
+  public int hashCode()
+  {
+    return Objects.hash(m00, m01, m02, m10, m11, m12);
+  }
+
   /**
    * Gets a text representation of this transformation.
    * The string is of the form:
    * <pre>
--- old/java/com/vividsolutions/jts/geomgraph/Edge.java
+++ new/java/com/vividsolutions/jts/geomgraph/Edge.java
@@ -1,6 +1,3 @@
-
-
-
 /*
  * The JTS Topology Suite is a collection of Java classes that
  * implement the fundamental operations required to validate a given
@@ -36,14 +33,15 @@
 package com.vividsolutions.jts.geomgraph;
 
 import java.io.PrintStream;
+import java.util.Arrays;
 import java.util.Iterator;
+import java.util.Objects;
 import com.vividsolutions.jts.algorithm.LineIntersector;
 import com.vividsolutions.jts.geom.*;
 import com.vividsolutions.jts.util.*;
 import com.vividsolutions.jts.geomgraph.*;
 import com.vividsolutions.jts.geomgraph.index.*;
 
-
 /**
  * @version 1.7
  */
@@ -241,6 +239,15 @@
     }
     return true;
   }
+
+  @Override
+  public int hashCode()
+  {
+    // Correct, but not optimal.
+    Coordinate[] sorted = pts.clone();
+    Arrays.sort(sorted);
+    return Arrays.hashCode(sorted);
+  }
 
   /**
    * @return true if the coordinate sequences of the Edges are identical
--- old/java/com/vividsolutions/jts/index/strtree/Interval.java
+++ new/java/com/vividsolutions/jts/index/strtree/Interval.java
@@ -34,6 +34,7 @@
 package com.vividsolutions.jts.index.strtree;
 
 import com.vividsolutions.jts.util.*;
+import java.util.Objects;
 
 /**
  * A contiguous portion of 1D-space. Used internally by SIRtree.
@@ -75,4 +76,11 @@
     Interval other = (Interval) o;
     return min == other.min && max == other.max;
   }
+
+  @Override
+  public int hashCode()
+  {
+    return Objects.hash(min, max);
+  }
+
 }

Incorrect results with fixed-precision buffer

Copying an old issue over from the mailing list:

I confirmed this is still a bug in JTS 1.14 (trunk).

Not sure what's going on, but there's a lot of complex processing in the
buffer algorithm, and lower precision models tends to stress the robustness
of some of the processes.

On Tue, Jul 28, 2015 at 9:25 AM, Daniel Baston <dbaston@...> wrote:

Hi Martin,

I came across a strange result from a basic buffer operation today, using
a buffer distance of 3.6e-4 and the following LineString:

LINESTRING (-89.188142 48.482882, -89.186677 48.483336, -89.181966
48.483669, -89.173652 48.483456, -89.17351 48.474992, -89.167407 48.474742,
-89.171975 48.47285, -89.173831 48.471316, -89.175295 48.468853, -89.177579
48.459002, -89.178864 48.457182, -89.183325 48.454576, -89.184967
48.454683, -89.18561 48.455397, -89.193498 48.451257, -89.197424 48.454612,
-89.19878 48.455468, -89.199708 48.457039, -89.199744 48.458252, -89.2016
48.459038, -89.201814 48.460037, -89.203349 48.461001, -89.20342 48.462964,
-89.202599 48.463678, -89.202563 48.464998, -89.201171 48.465284,
-89.199958 48.466604, -89.200922 48.468817, -89.201243 48.469781,
-89.197959 48.471173, -89.194997 48.472779, -89.194854 48.473529,
-89.192641 48.475349, -89.190357 48.47592, -89.190357 48.47724, -89.188893
48.477562, -89.187716 48.479239, -89.188142 48.482882)

Running this through TestBuilder in 1.13, I get seemingly correct results
with a PrecisionModel of 1e5 or 1e7 (or full double-precision), but the
result is incorrect (missing a hole) with a PrecisionModel of 1e6. Any
thoughts on this?

Thanks,
Dan

Create JTS distro zip file

Produce artifact equivalent to current distro zip.

Includes libs, doc, tests and run scripts for apps.

Not sure where to deploy this?

Single-sided Buffer poor quality linework

Hi there,

we have a problem when creating a single sided buffer for a line string and a little digging led us to a problem with the creation of offset curves. Using the following geometry as an example:

Input: LINESTRING (6 8, 2 5, 6 5)

JTS TestBuilder 1.14 will correctly create the offset curve with a distance of 1.

Result: LINESTRING (6.6 7.2, 5 6, 6 6)

Adding another point to the lower segment leads to quite a strange resulting offset curve.

Input: LINESTRING (6 8, 2 5, 4 5, 6 5)
Result: LINESTRING (6.6 7.2, 2.6 4.2, 2.5925925925925926 4.209876543209877, 2 5.987654320987654, 2 6, 6 6)

What seems to happen is that both segments are just shifted and joined through a third segment creating a triangle.
This is not a problem for creating a regular buffer, but when creating a single sided buffer the resulting polygon covers the triangle area:

POLYGON ((2.263374485596708 5.197530864197531, 2 5.987654320987654, 2 6, 3.3333333333333335 6, 6 8, 6.6 7.2, 5 6, 6 6, 6 5, 4 5, 3.6666666666666665 5, 2.6 4.2, 2.5925925925925926 4.209876543209877, 2.3292181069958846 5, 2 5, 2.263374485596708 5.197530864197531))

This might be a duplicate of issue #25, but I am not able to verify that.

Kind reagrds,
Marko Skocibusic

PrintUsage compute prefix length with hidden options

Hi,

CmdLineParser#PrintUsage() compute prefix length take into account hidden option.
Within SampleMain.java, the print usage is formatted using the length of option hidden-str2 VAL that is not displayed.

Regards

Add a userData field to the quadedge package Vertex class

This may be useful for mapping edges and triangles back to external data objects.

Split CGAlgorithms classes into meaningful classes

CGAlgorithms is a kitchen-drawer class which has outlived its usefulness. It can be split into the following classes.

• Orientation
  • computeOrientation - deprecated in favour of index
  • index
  • isCCW
  • CLOCKWISE
  • COUNTERCLOCKWISE
  • COLLINEAR
  • RIGHT
  • LEFT
  • STRAIGHT
• PointLocation
  • isInRing
  • isOnLine
  • locateOnRing
• DistanceBetween
  • linesegToLineseg
  • pointToLineseg (x2)
  • pointToLine
• Area
  • ofRing (new)
  • ofRingSigned (x2)
• Length
  • ofLine

CGAlgorithms can be deprecated and then removed in a future version.

CGAlgorithms3D can be renamed Distance3D since it contains only distance functions.

CGAlgorithmsDD can be left for now, since it is not intended to be used directly.