You can subscribe to this list here.
2009 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}


2010 
_{Jan}
(30) 
_{Feb}
(41) 
_{Mar}
(69) 
_{Apr}
(131) 
_{May}
(67) 
_{Jun}
(24) 
_{Jul}
(28) 
_{Aug}
(52) 
_{Sep}
(9) 
_{Oct}
(24) 
_{Nov}
(36) 
_{Dec}
(24) 
2011 
_{Jan}
(20) 
_{Feb}
(53) 
_{Mar}
(31) 
_{Apr}
(74) 
_{May}
(71) 
_{Jun}
(51) 
_{Jul}
(28) 
_{Aug}
(91) 
_{Sep}
(72) 
_{Oct}
(46) 
_{Nov}
(90) 
_{Dec}
(38) 
2012 
_{Jan}
(80) 
_{Feb}
(77) 
_{Mar}
(98) 
_{Apr}
(78) 
_{May}
(56) 
_{Jun}
(85) 
_{Jul}
(53) 
_{Aug}
(87) 
_{Sep}
(74) 
_{Oct}
(67) 
_{Nov}
(85) 
_{Dec}
(66) 
2013 
_{Jan}
(50) 
_{Feb}
(34) 
_{Mar}
(45) 
_{Apr}
(36) 
_{May}
(22) 
_{Jun}
(10) 
_{Jul}
(30) 
_{Aug}
(39) 
_{Sep}
(25) 
_{Oct}
(11) 
_{Nov}
(64) 
_{Dec}
(42) 
2014 
_{Jan}
(27) 
_{Feb}
(6) 
_{Mar}
(10) 
_{Apr}
(14) 
_{May}
(25) 
_{Jun}
(6) 
_{Jul}
(25) 
_{Aug}
(3) 
_{Sep}
(22) 
_{Oct}
(12) 
_{Nov}
(34) 
_{Dec}
(15) 
2015 
_{Jan}
(24) 
_{Feb}
(20) 
_{Mar}
(11) 
_{Apr}

_{May}
(37) 
_{Jun}
(24) 
_{Jul}
(1) 
_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

From: Pepper, Jason <pepper@te...>  20150706 19:09:37

The kdtree does not correctly find existing nodes. It ignores branches that may contain matches within the tree's threshold. To demonstrate this, create a kdtree with a threshold of 1.0. Then add the following points (0.0, 0.0), (0.1, 1.0), and (0.1, 1.0). The third point should be matched to the second point. However, the code ignores the right child of the root node and does not find the match. Jason Pepper ________________________________ TERRALIGN CONFIDENTIAL: This email and its attachments contain confidential and proprietary information of The TerrAlign Group, Inc.. Disclosure is strictly prohibited. 
From: Martin Davis <mtnclimb@gm...>  20150625 22:45:37

Nice! Would be great to get this into JTS. Although having two different triangulation implementations might cause a bit of confusion. It's interesting that the other one seems so much faster. I totally agree that the QuadEdge structure is overkill for triangulations... but I thought it was still pretty fast, if memory intensive. But perhaps the CH routine accesses it in a way that exposes a performance issue. On Thu, Jun 25, 2015 at 1:25 PM, Michaël Michaud < m.michael.michaud@...> wrote: > Hi, > > Note that another concave hull implementation based on JTS is available > here, > http://www.rotefabrik.free.fr/concave_hull/ > > 
From: Michaël Michaud <m.michaud@or...>  20150625 20:26:03

Hi, Note that another concave hull implementation based on JTS is available here, http://www.rotefabrik.free.fr/concave_hull/ Michaël Le 25/06/2015 18:18, Martin Davis a écrit : > Yes, Concave Hull would be nice. That algorithm looks like it might be > a good one. Not sure of the license though  it would have to be > assigned to JTS to be included. > > On Thu, Jun 25, 2015 at 2:07 AM, Paul Meems <bontepaarden@... > <mailto:bontepaarden@...>> wrote: > > I'm using GEOS and NTS, which are direct ports of JTS and I need > to create a concave hull. > This is currently not possible with JTS, but I found this JTS > extension pack: https://github.com/skipperkongen/jtsalgorithmpack > Are there any plans to include their concave hull into JTS? > After a while it will also be available in GEOS and NTS. > > > > >  > Monitor 25 network devices or servers for free with OpManager! > OpManager is webbased network management software that monitors > network devices and physical & virtual servers, alerts via email & sms > for fault. Monitor 25 devices for free with no restriction. Download now > http://ad.doubleclick.net/ddm/clk/292181274;119417398;o > > > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser 
From: Martin Davis <mtnclimb@gm...>  20150625 16:18:53

Yes, Concave Hull would be nice. That algorithm looks like it might be a good one. Not sure of the license though  it would have to be assigned to JTS to be included. On Thu, Jun 25, 2015 at 2:07 AM, Paul Meems <bontepaarden@...> wrote: > I'm using GEOS and NTS, which are direct ports of JTS and I need to create > a concave hull. > This is currently not possible with JTS, but I found this JTS extension > pack: https://github.com/skipperkongen/jtsalgorithmpack > Are there any plans to include their concave hull into JTS? > After a while it will also be available in GEOS and NTS. > > > 
From: Paul Meems <bontepaarden@gm...>  20150625 09:08:32

I'm using GEOS and NTS, which are direct ports of JTS and I need to create a concave hull. This is currently not possible with JTS, but I found this JTS extension pack: https://github.com/skipperkongen/jtsalgorithmpack Are there any plans to include their concave hull into JTS? After a while it will also be available in GEOS and NTS. Thanks, Paul *Paul Meems * Release manager, configuration manager and forum moderator of MapWindow GIS. http://www.mapwindow.org Owner of MapWindow.nl  Support for Dutch speaking users. http://www.mapwindow.nl *We've started with the development of MapWindow v5. Read more. <http://www.mapwindow.org/documentation/mapwingis4.9/MapWindow49.html>;* 
From: Martin Davis <mtnclimb@gm...>  20150623 17:20:29

Well, as I said it's not actually that strange that the smaller polygon does not lie exactly in the larger. Whenever a vertex is introduced to a segment, it's highly unlikely that the vertex lies *exactly* on the original segment (unless the segment is rectilinear  i.e. vertical or horizontal). The only way to deal with this is to use a snapping tolerance (which essentially adds an identical vertex back into the original segment). Good that you have a solution, anyway. On Mon, Jun 22, 2015 at 11:14 PM, Paul Meems <bontepaarden@...> wrote: > Thanks Martin for your swift response. > > Good to hear it is not a bug in JTS/NTS ;) > The smaller polygon is created as a single sided buffer from a line. This > line is a copy from the border of the larger line. > It is strange that the smaller polygon doesn't lie exactly on the larger > polygon. > I'll investigate further, for now I've solved this by using a full buffer. > > Thanks, > > Paul > > > 20150622 18:42 GMT+02:00 Martin Davis <mtnclimb@...>: > >> The reason for the "extra" vertex #12 is that the bottomright vertex of >> the Lshaped polygon does not quite lie exactly on the boundary of the >> larger polygon. It lies slightly inside, and thus the result of the >> difference contains a spike running down to vertex #12. >> >> I was able to resolve this by snapping the larger to the smaller polygon, >> using GeometrySnapper with distance 1. The snapping introduces a vertex >> matching the bottom right vertex of the Lshaped polygon, and so the >> difference does not contain the spike. >> >> This isn't really a bug  the code is working as designed. This is just >> one of those tricky situations where close tolerances and the limitations >> of finite precision causes some geometric anomalies. The ultimate solution >> to this is for JTS overlay operations to incorporate snaprounding to a >> tolerance  but that has not yet been developed. >> >> I'm not sure why there is a difference between the behaviour of >> singlesided buffer VS normal buffer. You'd have to post the exact inputs >> and calls to allow seeing if there's anything odd going on. But I suspect >> that it might be due to "cutting" a line segment to create vertex 13. A >> vertex computed along a line segment is highly unlikely to lie exactly on >> the line segment, due to the limitations of finite precision. >> >> On Mon, Jun 22, 2015 at 3:37 AM, Paul Meems <bontepaarden@...> >> wrote: >> >>> I'm reposting my question below which I initial posted to the NTS group. >>> Since QGis is experiencing the same issue Diego (NTS) suggested posting >>> it to the JTS group. >>> >>> The main question is if this is a bug in JTS or not. >>> The Lshaped polygon was created using a singlesided buffer of a >>> linestring made of coordinates from the larger polygon. >>> In this case I can also use a 'normal' buffer. When I do so the >>> difference is correct. >>> >>> Thanks, >>> >>> Paul >>> >>>  Forwarded message  >>> I have two polygons which I want to subtract from each other. >>> The field polygon it the larger polygon and overlaps the smaller polygon. >>> >>> When I perform the Difference action the remaining part has one >>> additional point on the smaller point which is not expected. >>> >>> This is the WKT: >>> POLYGON ((194908.68715217288 586962.86751464731, 194881.30215215127 >>> 586952.0195146437, 194879.05315214754 586952.15151464322, >>> 194877.20115214764 586954.13551464747, 194831.95715210476 >>> 587019.88551468146, 194760.91615204382 587122.9405147346, >>> 194857.09315212426 587178.23851475632, 194858.9451521278 >>> 587178.63551475492, 194860.26815212792 587177.44451475318, >>> 194873.10015214139 587158.65951475059, 194925.75215218749 587081.797514704, >>> 194953.13715220965 587042.10951468861, 194962.79415221984 >>> 587027.42551468522, 194985.68115224215 586994.0885146677, >>> 194986.21015224193 586991.70651466073, 194985.54815224075 >>> 586989.32551465672, 194908.68715217288 586962.86751464731)) >>> >>> and >>> >>> POLYGON ((194886.66904433916 586975.65752607386, 194901.74579137619 >>> 586981.629866985, 194928.53316474415 586990.85093296878, 194935.04290785809 >>> 586971.94000373222, 194908.68715217288 586962.86751464731, >>> 194881.30215215127 586952.0195146437, 194879.05315214754 >>> 586952.15151464322, 194877.20115214764 586954.13551464747, >>> 194831.95715210476 587019.88551468146, 194821.8332618672 >>> 587034.57164674706, 194838.29986314307 587045.92290405277, >>> 194848.42375338063 587031.23677198717, 194886.66904433916 >>> 586975.65752607386)) >>> >>> Both geometries are in EPSG:28992 (RD_new/Amersfoort, The Netherlands). >>> >>> I hope you can see the screen shot: >>> >>> >>> The blue Lshaped polygon is the small polygon. The greybrown polygon >>> is the result of the Difference action. As you can see the 12th point is >>> unexpected. The border should go from 11 to 13 and so on. Now it passed >>> point 13 and created point 12 and then goes back to point 13. >>> >>> >>> >>> > 
From: Paul Meems <bontepaarden@gm...>  20150623 06:15:42

Thanks Martin for your swift response. Good to hear it is not a bug in JTS/NTS ;) The smaller polygon is created as a single sided buffer from a line. This line is a copy from the border of the larger line. It is strange that the smaller polygon doesn't lie exactly on the larger polygon. I'll investigate further, for now I've solved this by using a full buffer. Thanks, Paul 20150622 18:42 GMT+02:00 Martin Davis <mtnclimb@...>: > The reason for the "extra" vertex #12 is that the bottomright vertex of > the Lshaped polygon does not quite lie exactly on the boundary of the > larger polygon. It lies slightly inside, and thus the result of the > difference contains a spike running down to vertex #12. > > I was able to resolve this by snapping the larger to the smaller polygon, > using GeometrySnapper with distance 1. The snapping introduces a vertex > matching the bottom right vertex of the Lshaped polygon, and so the > difference does not contain the spike. > > This isn't really a bug  the code is working as designed. This is just > one of those tricky situations where close tolerances and the limitations > of finite precision causes some geometric anomalies. The ultimate solution > to this is for JTS overlay operations to incorporate snaprounding to a > tolerance  but that has not yet been developed. > > I'm not sure why there is a difference between the behaviour of > singlesided buffer VS normal buffer. You'd have to post the exact inputs > and calls to allow seeing if there's anything odd going on. But I suspect > that it might be due to "cutting" a line segment to create vertex 13. A > vertex computed along a line segment is highly unlikely to lie exactly on > the line segment, due to the limitations of finite precision. > > On Mon, Jun 22, 2015 at 3:37 AM, Paul Meems <bontepaarden@...> > wrote: > >> I'm reposting my question below which I initial posted to the NTS group. >> Since QGis is experiencing the same issue Diego (NTS) suggested posting >> it to the JTS group. >> >> The main question is if this is a bug in JTS or not. >> The Lshaped polygon was created using a singlesided buffer of a >> linestring made of coordinates from the larger polygon. >> In this case I can also use a 'normal' buffer. When I do so the >> difference is correct. >> >> Thanks, >> >> Paul >> >>  Forwarded message  >> I have two polygons which I want to subtract from each other. >> The field polygon it the larger polygon and overlaps the smaller polygon. >> >> When I perform the Difference action the remaining part has one >> additional point on the smaller point which is not expected. >> >> This is the WKT: >> POLYGON ((194908.68715217288 586962.86751464731, 194881.30215215127 >> 586952.0195146437, 194879.05315214754 586952.15151464322, >> 194877.20115214764 586954.13551464747, 194831.95715210476 >> 587019.88551468146, 194760.91615204382 587122.9405147346, >> 194857.09315212426 587178.23851475632, 194858.9451521278 >> 587178.63551475492, 194860.26815212792 587177.44451475318, >> 194873.10015214139 587158.65951475059, 194925.75215218749 587081.797514704, >> 194953.13715220965 587042.10951468861, 194962.79415221984 >> 587027.42551468522, 194985.68115224215 586994.0885146677, >> 194986.21015224193 586991.70651466073, 194985.54815224075 >> 586989.32551465672, 194908.68715217288 586962.86751464731)) >> >> and >> >> POLYGON ((194886.66904433916 586975.65752607386, 194901.74579137619 >> 586981.629866985, 194928.53316474415 586990.85093296878, 194935.04290785809 >> 586971.94000373222, 194908.68715217288 586962.86751464731, >> 194881.30215215127 586952.0195146437, 194879.05315214754 >> 586952.15151464322, 194877.20115214764 586954.13551464747, >> 194831.95715210476 587019.88551468146, 194821.8332618672 >> 587034.57164674706, 194838.29986314307 587045.92290405277, >> 194848.42375338063 587031.23677198717, 194886.66904433916 >> 586975.65752607386)) >> >> Both geometries are in EPSG:28992 (RD_new/Amersfoort, The Netherlands). >> >> I hope you can see the screen shot: >> >> >> The blue Lshaped polygon is the small polygon. The greybrown polygon is >> the result of the Difference action. As you can see the 12th point is >> unexpected. The border should go from 11 to 13 and so on. Now it passed >> point 13 and created point 12 and then goes back to point 13. >> >> >> >> 
From: Martin Davis <mtnclimb@gm...>  20150622 16:42:41

The reason for the "extra" vertex #12 is that the bottomright vertex of the Lshaped polygon does not quite lie exactly on the boundary of the larger polygon. It lies slightly inside, and thus the result of the difference contains a spike running down to vertex #12. I was able to resolve this by snapping the larger to the smaller polygon, using GeometrySnapper with distance 1. The snapping introduces a vertex matching the bottom right vertex of the Lshaped polygon, and so the difference does not contain the spike. This isn't really a bug  the code is working as designed. This is just one of those tricky situations where close tolerances and the limitations of finite precision causes some geometric anomalies. The ultimate solution to this is for JTS overlay operations to incorporate snaprounding to a tolerance  but that has not yet been developed. I'm not sure why there is a difference between the behaviour of singlesided buffer VS normal buffer. You'd have to post the exact inputs and calls to allow seeing if there's anything odd going on. But I suspect that it might be due to "cutting" a line segment to create vertex 13. A vertex computed along a line segment is highly unlikely to lie exactly on the line segment, due to the limitations of finite precision. On Mon, Jun 22, 2015 at 3:37 AM, Paul Meems <bontepaarden@...> wrote: > I'm reposting my question below which I initial posted to the NTS group. > Since QGis is experiencing the same issue Diego (NTS) suggested posting it > to the JTS group. > > The main question is if this is a bug in JTS or not. > The Lshaped polygon was created using a singlesided buffer of a > linestring made of coordinates from the larger polygon. > In this case I can also use a 'normal' buffer. When I do so the difference > is correct. > > Thanks, > > Paul > >  Forwarded message  > I have two polygons which I want to subtract from each other. > The field polygon it the larger polygon and overlaps the smaller polygon. > > When I perform the Difference action the remaining part has one additional > point on the smaller point which is not expected. > > This is the WKT: > POLYGON ((194908.68715217288 586962.86751464731, 194881.30215215127 > 586952.0195146437, 194879.05315214754 586952.15151464322, > 194877.20115214764 586954.13551464747, 194831.95715210476 > 587019.88551468146, 194760.91615204382 587122.9405147346, > 194857.09315212426 587178.23851475632, 194858.9451521278 > 587178.63551475492, 194860.26815212792 587177.44451475318, > 194873.10015214139 587158.65951475059, 194925.75215218749 587081.797514704, > 194953.13715220965 587042.10951468861, 194962.79415221984 > 587027.42551468522, 194985.68115224215 586994.0885146677, > 194986.21015224193 586991.70651466073, 194985.54815224075 > 586989.32551465672, 194908.68715217288 586962.86751464731)) > > and > > POLYGON ((194886.66904433916 586975.65752607386, 194901.74579137619 > 586981.629866985, 194928.53316474415 586990.85093296878, 194935.04290785809 > 586971.94000373222, 194908.68715217288 586962.86751464731, > 194881.30215215127 586952.0195146437, 194879.05315214754 > 586952.15151464322, 194877.20115214764 586954.13551464747, > 194831.95715210476 587019.88551468146, 194821.8332618672 > 587034.57164674706, 194838.29986314307 587045.92290405277, > 194848.42375338063 587031.23677198717, 194886.66904433916 > 586975.65752607386)) > > Both geometries are in EPSG:28992 (RD_new/Amersfoort, The Netherlands). > > I hope you can see the screen shot: > > > The blue Lshaped polygon is the small polygon. The greybrown polygon is > the result of the Difference action. As you can see the 12th point is > unexpected. The border should go from 11 to 13 and so on. Now it passed > point 13 and created point 12 and then goes back to point 13. > > > > 
From: Paul Meems <bontepaarden@gm...>  20150622 10:38:35

From: Martin Davis <mtnclimb@gm...>  20150620 15:16:12

Use ShapeWriter to convert JTS Geometry to AWT Shapes standard way of getting the shell and hole vertices from a Polygon: poly.exteriorRing().getCoordinates() poly.interiorRingN(i).getCoordinates() On Sat, Jun 20, 2015 at 12:26 AM, Jerry Swan <dr.jerry.swan@...> wrote: > How can I convert obtain a java.awt.geom.Area from a JTS Polygon? > > I see that there's a jts.awt.PolygonShape from which Area can be obtained, > so if that's the best option then what's the standard way of getting the > shell and hole vertices from a Polygon? > > > 
From: Jerry Swan <dr.swan@gm...>  20150620 07:26:31

How can I convert obtain a java.awt.geom.Area from a JTS Polygon? I see that there's a jts.awt.PolygonShape from which Area can be obtained, so if that's the best option then what's the standard way of getting the shell and hole vertices from a Polygon? Best wishes, Jerry. On Fri, Jun 19, 2015 at 4:01 PM, Jerry Swan <dr.jerry.swan@...> wrote: > How might one determine the number of connected components of a > MultiPolygon? > > Best wishes, > > Jerry. > 
From: Ram Sriharsha <sriharsha.ram@gm...>  20150620 00:58:45

Hi David Thanks for your prompt response! And thanks for pointing me to spatial4j, it is perfect for my needs. Best Ram On Fri, Jun 19, 2015 at 5:25 PM, David Smiley <david.w.smiley@...> wrote: > Hi Ram. > > FYI JTS is planning to relicense “real soon now”; I believe that was the > state a year ago too. I don’t believe it’ll be ASL but it’s one that is > compatible with ASF rules. > > If you need something in the interim, consider using Spatial4j, which > provides some capabilities of its own in addition to wrapping JTS. > Spatial4j is ASL licensed, and is used by Apache Lucene. > > ~ David Smiley > (Spatial4j committer, Apache Lucene committer) > > > > On Jun 19, 2015, at 7:44 PM, Ram Sriharsha <harsha@...> wrote: > > > > Hi > > > > I am evaluating JTS for an apache licensed open source project I am > working on, and I like the codebase a lot, it is very well written. > However, its LGPL licensing means I cannot use it in Apache Projects. > > Is it possible to dual license your software so that it is compatible > with Apache license? > > > > Best > > > > Ram > > >  > > _______________________________________________ > > Jtstoposuiteuser mailing list > > Jtstoposuiteuser@... > > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: David Smiley <david.smiley@gm...>  20150620 00:25:21

Hi Ram. FYI JTS is planning to relicense “real soon now”; I believe that was the state a year ago too. I don’t believe it’ll be ASL but it’s one that is compatible with ASF rules. If you need something in the interim, consider using Spatial4j, which provides some capabilities of its own in addition to wrapping JTS. Spatial4j is ASL licensed, and is used by Apache Lucene. ~ David Smiley (Spatial4j committer, Apache Lucene committer) > On Jun 19, 2015, at 7:44 PM, Ram Sriharsha <harsha@...> wrote: > > Hi > > I am evaluating JTS for an apache licensed open source project I am working on, and I like the codebase a lot, it is very well written. However, its LGPL licensing means I cannot use it in Apache Projects. > Is it possible to dual license your software so that it is compatible with Apache license? > > Best > > Ram >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser 
From: Ram Sriharsha <harsha@ap...>  20150619 23:44:25

Hi I am evaluating JTS for an apache licensed open source project I am working on, and I like the codebase a lot, it is very well written. However, its LGPL licensing means I cannot use it in Apache Projects. Is it possible to dual license your software so that it is compatible with Apache license? Best Ram 
From: Martin Davis <mtnclimb@gm...>  20150619 16:21:12

Well, that's an interesting little problem. I don't think there's anything in JTS which computes this, although there's code which is somewhat similar (e.g. ConsistentAreaTester). The algorithm is pretty easy to state: MultiPolygon components are connected iff they intersect. To determine the number of connected components it's necessary to group the components into connected sets. The trick of course is doing this efficiently. This could be done using the lowlevel segment intersection machinery in JTS (the classes in the noding package). But I"m always looking for ways to use higherlevel operations to make coding geometric algorithms simpler and easier. In this case I think using PreparedPolygons for each of the components is the way to go. This will require some bookkeeping classes to maintain the groups of connected polygons (say ConnectedGroup, with operations intersects(PreparedPolygon) and add(PreparedPolygon). Then it's just a matter of keeping a list of ConnectedGroups, and iterating over the Polygon components and adding them to the ConnectedGroup they intersect. There's probably a more functional/declarative way of implementing this, which would be nice to explore. One of my goals for JTS is to make it more functional, hopefully leading to simpler and more obvious implementations for algorithms such as this one. Pls post the code if you get this going. On Fri, Jun 19, 2015 at 8:01 AM, Jerry Swan <dr.jerry.swan@...> wrote: > How might one determine the number of connected components of a > MultiPolygon? > > Best wishes, > > Jerry. > > >  > > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: Jerry Swan <dr.swan@gm...>  20150619 15:01:50

How might one determine the number of connected components of a MultiPolygon ? Best wishes, Jerry. 
From: Martin Davis <mtnclimb@gm...>  20150615 00:34:14

On Sun, Jun 14, 2015 at 5:12 PM, Chris Bennight <chris@...> wrote: > > > I also went ahead and rendered a graphic of what they look like > > Excellent! In fact, this immediately reveals its value, because I see now > that the query polygon is a random star polygon with significant > concavity. Definitely better than a regular convex polygon! 8^) > > Re: Synthetic vs. natural > Completely reasonable. Probably using variable simplified coastlines > would be a good real world case analogue (with a randomly generated query > geometry  asking the question "what countries does this query window > overlap). > Um, maybe. All depends on use case. There's a pretty much infinite number of scenarios. Here's some (invented) others:  What US census blocks intersect some (larger / smaller) query area?  What ship/truck tracks intersect some area of interest? > > > Re: highly datadependent > That makes sense  what I"m hopefully trying to come up with are a set of > heuristics that I can use to determine which strategy to use (with the > caveat that I may have to collect stats/profile a data set, and it's not > going to necessarily be correct for every comparison  just hoping to > answer the "best default setting") > In absence of *any* knowledge of the characteristics of query and target, I think the heuristic is "use PreparedGeometry". Maybe there's a refinement to use raw Geometry if the query polygon is low vertex count, or if the target set size is small. And if you find a systemic performance issue with very large query PGs, that's definitely of interest. > > Re: Increasing vertex count by densifying > I think taken in reverse this might be a good analogue for expected > simplification gains? (Granted the is also a decreasing amount of > irregularity in a real simplification, but unless intersects optimizes for > colinear points I expect the cost is the same). > Lower vertex count is always good 8^) Intersects does not optimize for collinear points. In fact, using monotone chains actually penalizes collinear vertices. (An interesting question is whether adding a maximum run length to MonotoneChain construction would improve performance. But this seems to me like a highly atypical case). 
From: Chris Bennight <chris@sl...>  20150615 00:12:43

Re: Data sets The shapefile size for the large resolutions was a bit ridiculous; I generated shape files for the query and target geometries up to 360k points. It's ~28MB compressed, but ~11GB uncompressed. http://cactus.bennight.com/shapefiles.zip I have a more manageable set at http://cactus.bennight.com/shapefiles_small.zip. This includes the single query geometry up to 360k points (~5mb), and the 1000 feature collections up to ~ 2800 points (~44mb uncompressed). I also went ahead and rendered a graphic of what they look like here's the query geometry: http://cactus.bennight.com/queryfeature.png here's the target geometries: http://cactus.bennight.com/targetfeature.png and here's both superimposed http://cactus.bennight.com/queryandtargetfeature.png I'll update and add them to the repo after the tests finish running. Re: Synthetic vs. natural Completely reasonable. Probably using variable simplified coastlines would be a good real world case analogue (with a randomly generated query geometry  asking the question "what countries does this query window overlap). Re: highly datadependent That makes sense  what I"m hopefully trying to come up with are a set of heuristics that I can use to determine which strategy to use (with the caveat that I may have to collect stats/profile a data set, and it's not going to necessarily be correct for every comparison  just hoping to answer the "best default setting") Re: terminology (intersects/intersection) Fixing that now  just semantic sloppiness on my part. Re: Increasing vertex count by densifying I think taken in reverse this might be a good analogue for expected simplification gains? (Granted the is also a decreasing amount of irregularity in a real simplification, but unless intersects optimizes for colinear points I expect the cost is the same). Re: profiling I'll run this down  later on this week and post the results back. On Sun, Jun 14, 2015 at 6:42 PM, Martin Davis <mtnclimb@...> wrote: > And a couple more thoughts: > >  The performance is highly data dependent, so it would be nice to see an > image of the test datasets to aid in understanding. If this was provided > it would be easy to see that the query geometry is a regular polygon (I > think?). As mentioned, this doesn't really take advantage of monotone > chains. >  It's pretty hard to synthesize data that approximates realworld data. > You might want to try and work with real datasets. >  I think relative peformance is going to be highly datadependent. For > example, a highly convex query geometry against a lot of small target > geometries might show PG is much faster than Raw. > > On Sun, Jun 14, 2015 at 3:11 PM, Joe Amenta <airbreather@...> wrote: > >> Martin's "intersects != intersection" point is actually extremely >> relevant here... the latest version on GitHub does an applestooranges >> comparison. >> >> The initial version before the "fixed methodology" commit compared >> PreparedGeometry.intersects(Geometry) with Geometry.*intersects*(Geometry), >> whereas the latest version compares PreparedGeometry.intersects(Geometry) >> with Geometry.*intersection*(Geometry). >> >> Just wanted to point this out... >> >> On Sun, Jun 14, 2015 at 5:51 PM, Martin Davis <mtnclimb@...> wrote: >> >>> Interesting and very thorough analysis! It's definitely a surprise that >>> PreparedGeometry drops below raw Geometry for large query sizes. It's >>> maybe a bit less of a surprise that small PGs don't provide much >>> improvement. >>> >>> It's going to take me a while to fully digest this, but a few initial >>> comments: >>> >>>  In JTS the intersects and intersection operation are quite different >>> (very much so in semantics, and currently somewhat less so in >>> implementation). PreparedGeometry currently provides only the intersects >>> operation. Support for intersection might be forthcoming at some point, >>> but it's not there now. You might want to adjust your terminology to >>> reflect this, to avoid confusion. >>> >>>  Increasing vertex count by densifying lines *might* be skewing the >>> results somewhat, since it might defeat the use of monotone chains to >>> improve indexing. Not sure how easy this is to mitigate  it's hard to >>> generate large random polygons! Nevertheless, realworld datasets might >>> show different performance characteristics (hopefully better!). >>> >>>  To figure out what's going on it will probably be necessary to profile >>> the execution for large PGs. Typically in geometric algorithms performance >>> problems are due to an O(n^2) operation lurking somewhere in the code. >>> These sometimes don't show up until very large input sizes. >>> >>> Thanks for the post  if this provides better guidance on using PG vs >>> Raw, this will be very helpful. >>> >>> >>> >>> On Sun, Jun 14, 2015 at 1:38 PM, Chris Bennight <chris@...> >>> wrote: >>> >>>> >>>> I put together a quick project to try and understand some of the >>>> tradeoffs for prepared vs. nonprepared geometries (when to use a prepared >>>> geometry, when not to, etc.) >>>> >>>> The readme has a summary of the tests and results, with graphics >>>> https://github.com/chrisbennight/intersectiontest >>>> >>>> Probably the best summary is this chart: >>>> >>>> https://raw.githubusercontent.com/chrisbennight/intersectiontest/master/src/main/resources/difference%20%20prepared%20vs%20non%20prepared%20%20chart.png >>>> >>>> which shows the difference of (prepared geometry intersection time  >>>> regular geometry intersection time) as a function of the number of points >>>> in each geometry. >>>> >>>> My big takeaway is that once the target geometry starts getting around >>>> 10k or more points, using a regular geometry intersection may be faster >>>> than using a prepared geometry intersection. (Not saying 10k is a magic >>>> number, just using that as a rough estimate of when I might need to start >>>> caring) >>>> >>>> I think a typically use case of a query window (think typically WMS, >>>> WFS, etc. BBOX query) with 5 points matching against complex geometries in >>>> the database might very easily see worse performance by creating a new >>>> PreparedGeometry instance of that 5 point geometry. >>>> >>>> Which is completely fair  just trying to understand the tradeoffs and >>>> heuristics for using it. Other strategies  such as in the case above, >>>> preparing the target geometry and flipping the intersection test (since in >>>> testing preparing the geometry was orders of magnitude faster than the >>>> intersection) are also things I'm interested in. >>>> >>>> Probably my big request is a little review from the experts  have I >>>> missed something obvious, done something horribly wrong, or is this a >>>> reasonable outcome? I'd also be curious if there are any guidelines for >>>> how/when people use a prepared geometry. It looks like PostGIS might >>>> employ some heuristics in what and when to prepared the geometry? >>>> >>>> Anyway, just looking for a quick vector check as well as any >>>> thoughts/guidance. Overall I'd like to come up with a heuristic for when >>>> to used prepared geometry against arbitrary sets of polygons. >>>> >>>> >>>>  >>>> >>>> _______________________________________________ >>>> Jtstoposuiteuser mailing list >>>> Jtstoposuiteuser@... >>>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >>>> >>>> >>> >>> >>>  >>> >>> _______________________________________________ >>> Jtstoposuiteuser mailing list >>> Jtstoposuiteuser@... >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >>> >>> >> > 
From: Chris Bennight <chris@sl...>  20150614 23:56:26

Mea culpa; the change wasn't intentional, probably a tabcomplete issue. I'm rerunning the numbers now  probably should be a pretty similar result, but that's a bad oversight nonetheless  thanks! On Sun, Jun 14, 2015 at 6:11 PM, Joe Amenta <airbreather@...> wrote: > Martin's "intersects != intersection" point is actually extremely relevant > here... the latest version on GitHub does an applestooranges comparison. > > The initial version before the "fixed methodology" commit compared > PreparedGeometry.intersects(Geometry) with Geometry.*intersects*(Geometry), > whereas the latest version compares PreparedGeometry.intersects(Geometry) > with Geometry.*intersection*(Geometry). > > Just wanted to point this out... > > On Sun, Jun 14, 2015 at 5:51 PM, Martin Davis <mtnclimb@...> wrote: > >> Interesting and very thorough analysis! It's definitely a surprise that >> PreparedGeometry drops below raw Geometry for large query sizes. It's >> maybe a bit less of a surprise that small PGs don't provide much >> improvement. >> >> It's going to take me a while to fully digest this, but a few initial >> comments: >> >>  In JTS the intersects and intersection operation are quite different >> (very much so in semantics, and currently somewhat less so in >> implementation). PreparedGeometry currently provides only the intersects >> operation. Support for intersection might be forthcoming at some point, >> but it's not there now. You might want to adjust your terminology to >> reflect this, to avoid confusion. >> >>  Increasing vertex count by densifying lines *might* be skewing the >> results somewhat, since it might defeat the use of monotone chains to >> improve indexing. Not sure how easy this is to mitigate  it's hard to >> generate large random polygons! Nevertheless, realworld datasets might >> show different performance characteristics (hopefully better!). >> >>  To figure out what's going on it will probably be necessary to profile >> the execution for large PGs. Typically in geometric algorithms performance >> problems are due to an O(n^2) operation lurking somewhere in the code. >> These sometimes don't show up until very large input sizes. >> >> Thanks for the post  if this provides better guidance on using PG vs >> Raw, this will be very helpful. >> >> >> >> On Sun, Jun 14, 2015 at 1:38 PM, Chris Bennight <chris@...> >> wrote: >> >>> >>> I put together a quick project to try and understand some of the >>> tradeoffs for prepared vs. nonprepared geometries (when to use a prepared >>> geometry, when not to, etc.) >>> >>> The readme has a summary of the tests and results, with graphics >>> https://github.com/chrisbennight/intersectiontest >>> >>> Probably the best summary is this chart: >>> >>> https://raw.githubusercontent.com/chrisbennight/intersectiontest/master/src/main/resources/difference%20%20prepared%20vs%20non%20prepared%20%20chart.png >>> >>> which shows the difference of (prepared geometry intersection time  >>> regular geometry intersection time) as a function of the number of points >>> in each geometry. >>> >>> My big takeaway is that once the target geometry starts getting around >>> 10k or more points, using a regular geometry intersection may be faster >>> than using a prepared geometry intersection. (Not saying 10k is a magic >>> number, just using that as a rough estimate of when I might need to start >>> caring) >>> >>> I think a typically use case of a query window (think typically WMS, >>> WFS, etc. BBOX query) with 5 points matching against complex geometries in >>> the database might very easily see worse performance by creating a new >>> PreparedGeometry instance of that 5 point geometry. >>> >>> Which is completely fair  just trying to understand the tradeoffs and >>> heuristics for using it. Other strategies  such as in the case above, >>> preparing the target geometry and flipping the intersection test (since in >>> testing preparing the geometry was orders of magnitude faster than the >>> intersection) are also things I'm interested in. >>> >>> Probably my big request is a little review from the experts  have I >>> missed something obvious, done something horribly wrong, or is this a >>> reasonable outcome? I'd also be curious if there are any guidelines for >>> how/when people use a prepared geometry. It looks like PostGIS might >>> employ some heuristics in what and when to prepared the geometry? >>> >>> Anyway, just looking for a quick vector check as well as any >>> thoughts/guidance. Overall I'd like to come up with a heuristic for when >>> to used prepared geometry against arbitrary sets of polygons. >>> >>> >>>  >>> >>> _______________________________________________ >>> Jtstoposuiteuser mailing list >>> Jtstoposuiteuser@... >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >>> >>> >> >> >>  >> >> _______________________________________________ >> Jtstoposuiteuser mailing list >> Jtstoposuiteuser@... >> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >> > 
From: Martin Davis <mtnclimb@gm...>  20150614 22:42:52

And a couple more thoughts:  The performance is highly data dependent, so it would be nice to see an image of the test datasets to aid in understanding. If this was provided it would be easy to see that the query geometry is a regular polygon (I think?). As mentioned, this doesn't really take advantage of monotone chains.  It's pretty hard to synthesize data that approximates realworld data. You might want to try and work with real datasets.  I think relative peformance is going to be highly datadependent. For example, a highly convex query geometry against a lot of small target geometries might show PG is much faster than Raw. On Sun, Jun 14, 2015 at 3:11 PM, Joe Amenta <airbreather@...> wrote: > Martin's "intersects != intersection" point is actually extremely relevant > here... the latest version on GitHub does an applestooranges comparison. > > The initial version before the "fixed methodology" commit compared > PreparedGeometry.intersects(Geometry) with Geometry.*intersects*(Geometry), > whereas the latest version compares PreparedGeometry.intersects(Geometry) > with Geometry.*intersection*(Geometry). > > Just wanted to point this out... > > On Sun, Jun 14, 2015 at 5:51 PM, Martin Davis <mtnclimb@...> wrote: > >> Interesting and very thorough analysis! It's definitely a surprise that >> PreparedGeometry drops below raw Geometry for large query sizes. It's >> maybe a bit less of a surprise that small PGs don't provide much >> improvement. >> >> It's going to take me a while to fully digest this, but a few initial >> comments: >> >>  In JTS the intersects and intersection operation are quite different >> (very much so in semantics, and currently somewhat less so in >> implementation). PreparedGeometry currently provides only the intersects >> operation. Support for intersection might be forthcoming at some point, >> but it's not there now. You might want to adjust your terminology to >> reflect this, to avoid confusion. >> >>  Increasing vertex count by densifying lines *might* be skewing the >> results somewhat, since it might defeat the use of monotone chains to >> improve indexing. Not sure how easy this is to mitigate  it's hard to >> generate large random polygons! Nevertheless, realworld datasets might >> show different performance characteristics (hopefully better!). >> >>  To figure out what's going on it will probably be necessary to profile >> the execution for large PGs. Typically in geometric algorithms performance >> problems are due to an O(n^2) operation lurking somewhere in the code. >> These sometimes don't show up until very large input sizes. >> >> Thanks for the post  if this provides better guidance on using PG vs >> Raw, this will be very helpful. >> >> >> >> On Sun, Jun 14, 2015 at 1:38 PM, Chris Bennight <chris@...> >> wrote: >> >>> >>> I put together a quick project to try and understand some of the >>> tradeoffs for prepared vs. nonprepared geometries (when to use a prepared >>> geometry, when not to, etc.) >>> >>> The readme has a summary of the tests and results, with graphics >>> https://github.com/chrisbennight/intersectiontest >>> >>> Probably the best summary is this chart: >>> >>> https://raw.githubusercontent.com/chrisbennight/intersectiontest/master/src/main/resources/difference%20%20prepared%20vs%20non%20prepared%20%20chart.png >>> >>> which shows the difference of (prepared geometry intersection time  >>> regular geometry intersection time) as a function of the number of points >>> in each geometry. >>> >>> My big takeaway is that once the target geometry starts getting around >>> 10k or more points, using a regular geometry intersection may be faster >>> than using a prepared geometry intersection. (Not saying 10k is a magic >>> number, just using that as a rough estimate of when I might need to start >>> caring) >>> >>> I think a typically use case of a query window (think typically WMS, >>> WFS, etc. BBOX query) with 5 points matching against complex geometries in >>> the database might very easily see worse performance by creating a new >>> PreparedGeometry instance of that 5 point geometry. >>> >>> Which is completely fair  just trying to understand the tradeoffs and >>> heuristics for using it. Other strategies  such as in the case above, >>> preparing the target geometry and flipping the intersection test (since in >>> testing preparing the geometry was orders of magnitude faster than the >>> intersection) are also things I'm interested in. >>> >>> Probably my big request is a little review from the experts  have I >>> missed something obvious, done something horribly wrong, or is this a >>> reasonable outcome? I'd also be curious if there are any guidelines for >>> how/when people use a prepared geometry. It looks like PostGIS might >>> employ some heuristics in what and when to prepared the geometry? >>> >>> Anyway, just looking for a quick vector check as well as any >>> thoughts/guidance. Overall I'd like to come up with a heuristic for when >>> to used prepared geometry against arbitrary sets of polygons. >>> >>> >>>  >>> >>> _______________________________________________ >>> Jtstoposuiteuser mailing list >>> Jtstoposuiteuser@... >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >>> >>> >> >> >>  >> >> _______________________________________________ >> Jtstoposuiteuser mailing list >> Jtstoposuiteuser@... >> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >> > 
From: Joe Amenta <airbreather@li...>  20150614 22:11:32

Martin's "intersects != intersection" point is actually extremely relevant here... the latest version on GitHub does an applestooranges comparison. The initial version before the "fixed methodology" commit compared PreparedGeometry.intersects(Geometry) with Geometry.*intersects*(Geometry), whereas the latest version compares PreparedGeometry.intersects(Geometry) with Geometry.*intersection*(Geometry). Just wanted to point this out... On Sun, Jun 14, 2015 at 5:51 PM, Martin Davis <mtnclimb@...> wrote: > Interesting and very thorough analysis! It's definitely a surprise that > PreparedGeometry drops below raw Geometry for large query sizes. It's > maybe a bit less of a surprise that small PGs don't provide much > improvement. > > It's going to take me a while to fully digest this, but a few initial > comments: > >  In JTS the intersects and intersection operation are quite different > (very much so in semantics, and currently somewhat less so in > implementation). PreparedGeometry currently provides only the intersects > operation. Support for intersection might be forthcoming at some point, > but it's not there now. You might want to adjust your terminology to > reflect this, to avoid confusion. > >  Increasing vertex count by densifying lines *might* be skewing the > results somewhat, since it might defeat the use of monotone chains to > improve indexing. Not sure how easy this is to mitigate  it's hard to > generate large random polygons! Nevertheless, realworld datasets might > show different performance characteristics (hopefully better!). > >  To figure out what's going on it will probably be necessary to profile > the execution for large PGs. Typically in geometric algorithms performance > problems are due to an O(n^2) operation lurking somewhere in the code. > These sometimes don't show up until very large input sizes. > > Thanks for the post  if this provides better guidance on using PG vs Raw, > this will be very helpful. > > > > On Sun, Jun 14, 2015 at 1:38 PM, Chris Bennight <chris@...> wrote: > >> >> I put together a quick project to try and understand some of the >> tradeoffs for prepared vs. nonprepared geometries (when to use a prepared >> geometry, when not to, etc.) >> >> The readme has a summary of the tests and results, with graphics >> https://github.com/chrisbennight/intersectiontest >> >> Probably the best summary is this chart: >> >> https://raw.githubusercontent.com/chrisbennight/intersectiontest/master/src/main/resources/difference%20%20prepared%20vs%20non%20prepared%20%20chart.png >> >> which shows the difference of (prepared geometry intersection time  >> regular geometry intersection time) as a function of the number of points >> in each geometry. >> >> My big takeaway is that once the target geometry starts getting around >> 10k or more points, using a regular geometry intersection may be faster >> than using a prepared geometry intersection. (Not saying 10k is a magic >> number, just using that as a rough estimate of when I might need to start >> caring) >> >> I think a typically use case of a query window (think typically WMS, WFS, >> etc. BBOX query) with 5 points matching against complex geometries in the >> database might very easily see worse performance by creating a new >> PreparedGeometry instance of that 5 point geometry. >> >> Which is completely fair  just trying to understand the tradeoffs and >> heuristics for using it. Other strategies  such as in the case above, >> preparing the target geometry and flipping the intersection test (since in >> testing preparing the geometry was orders of magnitude faster than the >> intersection) are also things I'm interested in. >> >> Probably my big request is a little review from the experts  have I >> missed something obvious, done something horribly wrong, or is this a >> reasonable outcome? I'd also be curious if there are any guidelines for >> how/when people use a prepared geometry. It looks like PostGIS might >> employ some heuristics in what and when to prepared the geometry? >> >> Anyway, just looking for a quick vector check as well as any >> thoughts/guidance. Overall I'd like to come up with a heuristic for when >> to used prepared geometry against arbitrary sets of polygons. >> >> >>  >> >> _______________________________________________ >> Jtstoposuiteuser mailing list >> Jtstoposuiteuser@... >> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >> > > >  > > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: Martin Davis <mtnclimb@gm...>  20150614 21:51:46

Interesting and very thorough analysis! It's definitely a surprise that PreparedGeometry drops below raw Geometry for large query sizes. It's maybe a bit less of a surprise that small PGs don't provide much improvement. It's going to take me a while to fully digest this, but a few initial comments:  In JTS the intersects and intersection operation are quite different (very much so in semantics, and currently somewhat less so in implementation). PreparedGeometry currently provides only the intersects operation. Support for intersection might be forthcoming at some point, but it's not there now. You might want to adjust your terminology to reflect this, to avoid confusion.  Increasing vertex count by densifying lines *might* be skewing the results somewhat, since it might defeat the use of monotone chains to improve indexing. Not sure how easy this is to mitigate  it's hard to generate large random polygons! Nevertheless, realworld datasets might show different performance characteristics (hopefully better!).  To figure out what's going on it will probably be necessary to profile the execution for large PGs. Typically in geometric algorithms performance problems are due to an O(n^2) operation lurking somewhere in the code. These sometimes don't show up until very large input sizes. Thanks for the post  if this provides better guidance on using PG vs Raw, this will be very helpful. On Sun, Jun 14, 2015 at 1:38 PM, Chris Bennight <chris@...> wrote: > > I put together a quick project to try and understand some of the > tradeoffs for prepared vs. nonprepared geometries (when to use a prepared > geometry, when not to, etc.) > > The readme has a summary of the tests and results, with graphics > https://github.com/chrisbennight/intersectiontest > > Probably the best summary is this chart: > > https://raw.githubusercontent.com/chrisbennight/intersectiontest/master/src/main/resources/difference%20%20prepared%20vs%20non%20prepared%20%20chart.png > > which shows the difference of (prepared geometry intersection time  > regular geometry intersection time) as a function of the number of points > in each geometry. > > My big takeaway is that once the target geometry starts getting around 10k > or more points, using a regular geometry intersection may be faster than > using a prepared geometry intersection. (Not saying 10k is a magic > number, just using that as a rough estimate of when I might need to start > caring) > > I think a typically use case of a query window (think typically WMS, WFS, > etc. BBOX query) with 5 points matching against complex geometries in the > database might very easily see worse performance by creating a new > PreparedGeometry instance of that 5 point geometry. > > Which is completely fair  just trying to understand the tradeoffs and > heuristics for using it. Other strategies  such as in the case above, > preparing the target geometry and flipping the intersection test (since in > testing preparing the geometry was orders of magnitude faster than the > intersection) are also things I'm interested in. > > Probably my big request is a little review from the experts  have I > missed something obvious, done something horribly wrong, or is this a > reasonable outcome? I'd also be curious if there are any guidelines for > how/when people use a prepared geometry. It looks like PostGIS might > employ some heuristics in what and when to prepared the geometry? > > Anyway, just looking for a quick vector check as well as any > thoughts/guidance. Overall I'd like to come up with a heuristic for when > to used prepared geometry against arbitrary sets of polygons. > > >  > > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: Chris Bennight <chris@sl...>  20150614 21:06:48

I put together a quick project to try and understand some of the tradeoffs for prepared vs. nonprepared geometries (when to use a prepared geometry, when not to, etc.) The readme has a summary of the tests and results, with graphics https://github.com/chrisbennight/intersectiontest Probably the best summary is this chart: https://raw.githubusercontent.com/chrisbennight/intersectiontest/master/src/main/resources/difference%20%20prepared%20vs%20non%20prepared%20%20chart.png which shows the difference of (prepared geometry intersection time  regular geometry intersection time) as a function of the number of points in each geometry. My big takeaway is that once the target geometry starts getting around 10k or more points, using a regular geometry intersection may be faster than using a prepared geometry intersection. (Not saying 10k is a magic number, just using that as a rough estimate of when I might need to start caring) I think a typically use case of a query window (think typically WMS, WFS, etc. BBOX query) with 5 points matching against complex geometries in the database might very easily see worse performance by creating a new PreparedGeometry instance of that 5 point geometry. Which is completely fair  just trying to understand the tradeoffs and heuristics for using it. Other strategies  such as in the case above, preparing the target geometry and flipping the intersection test (since in testing preparing the geometry was orders of magnitude faster than the intersection) are also things I'm interested in. Probably my big request is a little review from the experts  have I missed something obvious, done something horribly wrong, or is this a reasonable outcome? I'd also be curious if there are any guidelines for how/when people use a prepared geometry. It looks like PostGIS might employ some heuristics in what and when to prepared the geometry? Anyway, just looking for a quick vector check as well as any thoughts/guidance. Overall I'd like to come up with a heuristic for when to used prepared geometry against arbitrary sets of polygons. 
From: Martin Davis <mtnclimb@gm...>  20150614 21:06:24

Hmm, that's a bit of a shocker... amazing this bug hasn't surfaced before. The problem is that Translater implements CoordinateFilter, which is not able to mutate nonCoordinate based CoordinateSequences. The fix may be simple. I'm thinking about creating a MutatingCoordinateFilter which implements CoordinateSequenceFilter. With any luck this can just be dropped in and will fix the problem. An alternative is to change the semantics of CoordinateFilter to force mutations into the source geometry in a way which works with general CoordinateSequences. This might be a bit slower, however, since it will have to do a lot of checking to see if the coordinate should be updated, or else update even if the Coordinate was not modified. Better I think to make the ability to be mutated explicit. On Fri, Jun 12, 2015 at 7:07 AM, Kay, Jim <Kay.J@...> wrote: > I have an incorrect from the union of two Polygons. > The first Polygon (g0) is created from a PackedCoordinateSequence. > The second Polygon (g1) is created from a CoordinateArray. > > The two Polygons are nearly on top of each other. > During the unioning process, 'OverlayOp.overlayOp' fails and so the code > defaults to 'SnapOverlayOp.overlayOp'. > In the subsequent code the removal of common bits using > 'removeCommonBits(Geometry geom)' fails to successfully apply the > translation to the geometry created from (g0) PackedCoordinateSequence. > Subsequently the code unions the unshifted g0 geometry with the shifted g1 > geometry, incorrectly producing a MultiPolygon. > > Java test code attached (with plotting; please maximise Window) > > I have copied some of the relevant method calls below. > > Jim Kay > > >  > > SnapIfNeededOverlayOp > getResultGeometry(int opCode) > > Normal: > result = OverlayOp.overlayOp(geom[0], geom[1], opCode); > > Fails: > savedException = (com.vividsolutions.jts.geom.TopologyException) > com.vividsolutions.jts.geom.TopologyException: found nonnoded intersection > between LINESTRING ( 0.08528230009449685 4.82017814227853, > 0.110460580710986 4.81977663231897 ) and LINESTRING ( 0.0909282486242289 > 4.820088108149497, 0.090682719052808 4.82011418579351 ) [ > (0.09092824862422651, 4.820088108149497, NaN) ] > > If fails the alternative is: > result = SnapOverlayOp.overlayOp(geom[0], geom[1], opCode); > > SnapOverlayOp.overlayOp(Geometry g0, Geometry g1, int opCode) > return op.getResultGeometry(opCode); > public Geometry getResultGeometry(int opCode) > Geometry[] prepGeom = snap(geom); > private Geometry[] snap(Geometry[] geom) > Geometry[] remGeom = removeCommonBits(geom); > private Geometry[] removeCommonBits(Geometry[] geom) > cbr commonCoord identified (0.0, 4.75) > remGeom[0] = cbr.removeCommonBits((Geometry) geom[0].clone()); > public Geometry removeCommonBits(Geometry geom) // for g0 > Translater trans = new Translater(invCoord); // setup > (0.0, 4.75) > geom.apply(trans); > geom.geometryChanged(); > return geom; // NO CHANGE IN COORDINATE > VALUES FOR g0 from PackedCoordinateSequence > > remGeom[1] = cbr.removeCommonBits((Geometry) geom[1].clone()); > public Geometry removeCommonBits(Geometry geom) // for g1 > Translater trans = new Translater(invCoord); // setup > (0.0, 4.75) > geom.apply(trans); > geom.geometryChanged(); > return geom; // OK y values shifted down by > 4.75 FOR g1 > > > g0 created from PackedCoordinateSequence > POLYGON ((0.0100573988512497 4.78384542541783, 0.0254790503435339 > 4.7853680160678, 0.0257229583365779 4.8203671661845, 0.0432753661791916 > 4.82084801337078, 0.110460580710986 4.81977663231897, 0.125859513580305 > 4.81803925397127, 0.125615605587261 4.78304010385457, 0.0100573988512497 > 4.78384542541783)) > > g1 created from CoordinateArray > POLYGON ((0.0852823000943891 4.820178142278531, 0.0432753661791916 > 4.82084801337078, 0.034111552138555 4.820784151034586, 0.0234947209409801 > 4.82090988483611, 0.0455036035747894 4.82042903764982, 0.0452596955817454 > 4.78542988753313, 0.0344169517745771 4.78443089375864, 0.101266578492074 > 4.78396502078076, 0.110216672717942 4.78477748220227, 0.110460580710986 > 4.81977663231897, 0.0909282486242289 4.820088108149497, 0.090682719052808 > 4.82011418579351, 0.0852823000943891 4.820178142278531)) > > Incorrect result > MULTIPOLYGON (((0.0100573988512497 9.53384542541783, 0.125615605587261 > 9.533040103854571, 0.125859513580305 9.568039253971271, 0.110460580710986 > 9.56977663231897, 0.0432753661791916 9.57084801337078, 0.0257229583365779 > 9.5703671661845, 0.0254790503435339 9.5353680160678, 0.0100573988512497 > 9.53384542541783)), ((0.0852823000943891 4.820178142278531, > 0.0432753661791916 4.82084801337078, 0.034111552138555 4.820784151034586, > 0.0234947209409801 4.82090988483611, 0.0455036035747894 4.82042903764982, > 0.0452596955817454 4.78542988753313, 0.0344169517745771 4.78443089375864, > 0.101266578492074 4.78396502078076, 0.110216672717942 4.78477748220227, > 0.110460580710986 4.81977663231897, 0.0909282486242289 4.820088108149497, > 0.090682719052808 4.82011418579351, 0.0852823000943891 > 4.820178142278531))) > > Correct result > POLYGON ((0.0153233378632719 4.784365335331955, 0.0100573988512497 > 4.78384542541783, 0.125615605587261 4.78304010385457, 0.125859513580305 > 4.81803925397127, 0.110460580710986 4.81977663231897, 0.0909282486242289 > 4.820088108149497, 0.090682719052808 4.82011418579351, 0.0852823000943891 > 4.820178142278531, 0.0432753661791916 4.82084801337078, 0.034111552138555 > 4.820784151034586, 0.0234947209409801 4.82090988483611, 0.0455036035747894 > 4.82042903764982, 0.0452596955817454 4.78542988753313, 0.0344169517745771 > 4.78443089375864, 0.0153233378632719 4.784365335331955)) > > > >  > > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: Kay, Jim <Kay.J@Interfleet.co.uk>  20150612 14:29:53

I have an incorrect from the union of two Polygons. The first Polygon (g0) is created from a PackedCoordinateSequence. The second Polygon (g1) is created from a CoordinateArray. The two Polygons are nearly on top of each other. During the unioning process, 'OverlayOp.overlayOp' fails and so the code defaults to 'SnapOverlayOp.overlayOp'. In the subsequent code the removal of common bits using 'removeCommonBits(Geometry geom)' fails to successfully apply the translation to the geometry created from (g0) PackedCoordinateSequence. Subsequently the code unions the unshifted g0 geometry with the shifted g1 geometry, incorrectly producing a MultiPolygon. Java test code attached (with plotting; please maximise Window) I have copied some of the relevant method calls below. Jim Kay  SnapIfNeededOverlayOp > getResultGeometry(int opCode) Normal: result = OverlayOp.overlayOp(geom[0], geom[1], opCode); Fails: savedException = (com.vividsolutions.jts.geom.TopologyException) com.vividsolutions.jts.geom.TopologyException: found nonnoded intersection between LINESTRING ( 0.08528230009449685 4.82017814227853, 0.110460580710986 4.81977663231897 ) and LINESTRING ( 0.0909282486242289 4.820088108149497, 0.090682719052808 4.82011418579351 ) [ (0.09092824862422651, 4.820088108149497, NaN) ] If fails the alternative is: result = SnapOverlayOp.overlayOp(geom[0], geom[1], opCode); SnapOverlayOp.overlayOp(Geometry g0, Geometry g1, int opCode) return op.getResultGeometry(opCode); public Geometry getResultGeometry(int opCode) Geometry[] prepGeom = snap(geom); private Geometry[] snap(Geometry[] geom) Geometry[] remGeom = removeCommonBits(geom); private Geometry[] removeCommonBits(Geometry[] geom) cbr commonCoord identified (0.0, 4.75) remGeom[0] = cbr.removeCommonBits((Geometry) geom[0].clone()); public Geometry removeCommonBits(Geometry geom) // for g0 Translater trans = new Translater(invCoord); // setup (0.0, 4.75) geom.apply(trans); geom.geometryChanged(); return geom; // NO CHANGE IN COORDINATE VALUES FOR g0 from PackedCoordinateSequence remGeom[1] = cbr.removeCommonBits((Geometry) geom[1].clone()); public Geometry removeCommonBits(Geometry geom) // for g1 Translater trans = new Translater(invCoord); // setup (0.0, 4.75) geom.apply(trans); geom.geometryChanged(); return geom; // OK y values shifted down by 4.75 FOR g1 g0 created from PackedCoordinateSequence POLYGON ((0.0100573988512497 4.78384542541783, 0.0254790503435339 4.7853680160678, 0.0257229583365779 4.8203671661845, 0.0432753661791916 4.82084801337078, 0.110460580710986 4.81977663231897, 0.125859513580305 4.81803925397127, 0.125615605587261 4.78304010385457, 0.0100573988512497 4.78384542541783)) g1 created from CoordinateArray POLYGON ((0.0852823000943891 4.820178142278531, 0.0432753661791916 4.82084801337078, 0.034111552138555 4.820784151034586, 0.0234947209409801 4.82090988483611, 0.0455036035747894 4.82042903764982, 0.0452596955817454 4.78542988753313, 0.0344169517745771 4.78443089375864, 0.101266578492074 4.78396502078076, 0.110216672717942 4.78477748220227, 0.110460580710986 4.81977663231897, 0.0909282486242289 4.820088108149497, 0.090682719052808 4.82011418579351, 0.0852823000943891 4.820178142278531)) Incorrect result MULTIPOLYGON (((0.0100573988512497 9.53384542541783, 0.125615605587261 9.533040103854571, 0.125859513580305 9.568039253971271, 0.110460580710986 9.56977663231897, 0.0432753661791916 9.57084801337078, 0.0257229583365779 9.5703671661845, 0.0254790503435339 9.5353680160678, 0.0100573988512497 9.53384542541783)), ((0.0852823000943891 4.820178142278531, 0.0432753661791916 4.82084801337078, 0.034111552138555 4.820784151034586, 0.0234947209409801 4.82090988483611, 0.0455036035747894 4.82042903764982, 0.0452596955817454 4.78542988753313, 0.0344169517745771 4.78443089375864, 0.101266578492074 4.78396502078076, 0.110216672717942 4.78477748220227, 0.110460580710986 4.81977663231897, 0.0909282486242289 4.820088108149497, 0.090682719052808 4.82011418579351, 0.0852823000943891 4.820178142278531))) Correct result POLYGON ((0.0153233378632719 4.784365335331955, 0.0100573988512497 4.78384542541783, 0.125615605587261 4.78304010385457, 0.125859513580305 4.81803925397127, 0.110460580710986 4.81977663231897, 0.0909282486242289 4.820088108149497, 0.090682719052808 4.82011418579351, 0.0852823000943891 4.820178142278531, 0.0432753661791916 4.82084801337078, 0.034111552138555 4.820784151034586, 0.0234947209409801 4.82090988483611, 0.0455036035747894 4.82042903764982, 0.0452596955817454 4.78542988753313, 0.0344169517745771 4.78443089375864, 0.0153233378632719 4.784365335331955)) 