Re: [jts-devel] Overlapping or penetration depth
I haven't come across the notion of "penetration depth" before - very interesting! It seems that the usual definition is: The (overall) penetration depth, (A;B) is defined as the minimum amount of translational motion required in any direction required to make the interior of A disjoint from B (from this paper: http://www.cs.duke.edu/courses/spring07/cps296.2/course_projects/shashi_proj.pdf ) It looks like this is a non-trivial computation, except possibly in the case of both polygons being convex. There's nothing in JTS at the moment which computes this value. The technique used by the distance algorithm to compute distance = 0 is quite different and much simpler, and can't be amended to compute penetration depth (As you might see, there's a big difference between computing a 0 value for something, and computing a non-zero value which describes a complex situation) The survey paper lists the current best algorithms for various cases (both convex, one convex). I'm not sure if they're similar to the GJK algorithm. Seems like they'd be fairly complex to implement (unless perhaps some existing code can be found and adapted to JTS). Jim Kay wrote: Is there an easy way to calculate by how much geometries (say polygons) overlap? I am thinking of the collision-detection problem of 'penetration depth'. The distance method returns zero for overlapping polygons - could this be amended to give a negative distance? Would my request require something like the GJK algorithm, and would that be difficult to implement? */Jim/* Jim Kay Senior Engineer Interfleet Technology Ltd email: ka...@interfleet.co.uk tel:+44 (0) 1332 223229 fax:+44 (0) 1332 223181 mobile: +44 (0) 7715 536828 web:_www.interfleet.co.uk_ Interfleet Technology Ltd Interfleet House Pride Parkway Derby DE24 8HX ** Interfleet Technology Ltd Interfleet Technology's email disclaimer is found via the following URL: http://www.interfleet-technology.com/disclaimer.asp Registered Offices: http://www.interfleet-technology.com/offices.asp Please consider the environment before printing this e-mail. ** ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] [Fwd: Re: Book]
Actually I talked to Tyler a couple of years ago, when I was first thinking about a book and he had just finished his book. He was the one who warned me that a book was a HUGE undertaking and was likely to consume a full year of life... 8^) Hence my wondering about partnering with someone, so it would only take 6 months of life from two people 8^) @Michael: thx for the link to the Pragmatic site. They sound very encouraging. Now all I have to do is to write 20 pages of the book to show them... 8^) I'll keep thinking abou this... Sunburned Surveyor wrote: Martin, I think the idea for a book on JTS is great! You should talk to Tyler Mitchell at the OSGeo, who has some experience with publishing books on geospatial topics. Let me know if you want his e-mail. I'd be willing to help review any material you and your eventual partner put together on a JTS book. If you decide to go with a self-publishing option like Lulu, I can help set-up the layout for a book in something like Scribus. I hope things will work out for a book! I'd definitely buy a copy. Landon On Thu, Oct 8, 2009 at 11:22 AM, Martin Davis wrote: Mike? You mean Michael Bedward? It would certainly be motivating to have a partner to write with... And yeah, Wrox would be good, or there are some other publishers as well I think. JTS for Dummies? JTS in Action? Essential JTS? I'm game if someone else is keen to collaborate... Martin Lee Goddard wrote: Martin Davis wrote: No book yet unfortunately... I did approach O'Reilly at one time, but nothing came of it. It would be nice to have for sure... Nice? Essential! This is such a powerful and well-supported library, it deserves a book. O'Reilly are good (I'm from Perl), but there are others: Wrox sprigns to mind. From watching the list for a while, you and Mike would seem to be a good pair to write it, no? ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Reducing precision in Coordinates
Have a look at SimpleGeometryPrecisionReducer. The only downside to using this class is that it doesn't absolutely guarantee that the reduced polygon willl be valid (in certain situations moving coordinates by a small amount can produce self-intersections). If you're just exporting to KML this probably doesn't matter - in my experience, Google tools are pretty tolerant of "slightly invalid" polygons. Or you can always use buffer(0) to clean up the problem. Lee Goddard wrote: To try and reduce the size of my KML export, I would like to reduce the precision of my coordinates, which are currently to 13 decimal places. Is there a JTS way to do this, or will I have to pre-process my data? Thanks in anticipation Lee ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] book on JTS
Stefan, thanks for the reminder about the JTS presentation. I'll add it to the JTS web site that I maintain (http://tsusiatsoftware.net/jts/main.html) I'll have a look for the test suite doc - it might be of interest to some people. And yes, there's lots of potential publishers. I really need to have a partner to work with though - it's a huge job putting together a book, from what I've heard from other authors. And I still have a day job... and a young child to look after! Martin Stefan Steiniger wrote: Hei Martin, well.. doesn't need to be O'Reily. It could be also published with one of the smaller publishers or as self publisher, i.e. - lulu.com (publish on your own) or one of the publishers used by - Regina Obe for the PostGIS book (http://www.manning.com/obe/ ) - Gary Sherman for the "QGIS book" (http://www.pragprog.com/titles/gsdgis/desktop-gis) and you may even get a bit help from us? (Michael Michaud and David Zwiers are probably one of the true other experts in using JTS) However, for now, it may still be worthwhile to point people to your 2007 presentation (although some of the newer stuff is not mentioned): http://jump-pilot.sourceforge.net/pdfs/jts_secrets_foss4g2007.pdf mhm.. I wonder, wasn't there a doc on JTS that came with JUMP once (that described also the test suite for the intersection model)? thanks for all your work stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Book
Mike? You mean Michael Bedward? It would certainly be motivating to have a partner to write with... And yeah, Wrox would be good, or there are some other publishers as well I think. JTS for Dummies? JTS in Action? Essential JTS? I'm game if someone else is keen to collaborate... Martin Lee Goddard wrote: Martin Davis wrote: No book yet unfortunately... I did approach O'Reilly at one time, but nothing came of it. It would be nice to have for sure... Nice? Essential! This is such a powerful and well-supported library, it deserves a book. O'Reilly are good (I'm from Perl), but there are others: Wrox sprigns to mind. From watching the list for a while, you and Mike would seem to be a good pair to write it, no? ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Merging many polygons
Great! No book yet unfortunately... I did approach O'Reilly at one time, but nothing came of it. It would be nice to have for sure... Lee Goddard wrote: Wow. I love JTS. Is there a book on the library you would recommend? Martin Davis wrote: Nope, union is quite happy accepting disjoint polygons. The output will be a MultiPolygon containing the disjoint polys as components. Lee Goddard wrote: That's a good idea, and makes sense. But won't I still need to check that the polygons are able to merge? If I supply two disconnected polygons to the union function, I imagine it won't be happy? Martin Davis wrote: One way you can speed this up is to use a spatial index on your processed polygon set. You'll be updating it as you merge polygons, so it needs to be a Quadtree. Do you have attributes attached to your polygons? If *not*, then you could cluster polygons together (ie spatially by proximity) and then use UnaryUnion to merge them all together at once (ie GeometryCollection.union()) One way to cluster the polygons is to make a coarse grid over the extent of the polygons, assign each polygon to the grid cell containing it's centroid, then take each grid cell group as a cluster. Lee Goddard wrote: I have several million points that compose several thousand polygons, and I'm outputting KMZ. The KMZ is about 2MB, and I'm trying to reduce the size by merging polygons that have adjecent edges, and drop those that are contained within others. I have created to arrays of polygons: one of all unprocessed, one empty. For each unprocessed polygon, I try to compare it the processed, dropping the unprocessed or merging it, as appropriate. This seems frr from ideal. This must be a common task, but being new to JTS and topology in general, I'm not sure if I should be able to find a method to do this for me, or if I should continue trying to do it my own way? ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.409 / Virus Database: 270.14.2/2408 - Release Date: 10/01/09 18:23:00 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Merging many polygons
Nope, union is quite happy accepting disjoint polygons. The output will be a MultiPolygon containing the disjoint polys as components. Lee Goddard wrote: That's a good idea, and makes sense. But won't I still need to check that the polygons are able to merge? If I supply two disconnected polygons to the union function, I imagine it won't be happy? Martin Davis wrote: One way you can speed this up is to use a spatial index on your processed polygon set. You'll be updating it as you merge polygons, so it needs to be a Quadtree. Do you have attributes attached to your polygons? If *not*, then you could cluster polygons together (ie spatially by proximity) and then use UnaryUnion to merge them all together at once (ie GeometryCollection.union()) One way to cluster the polygons is to make a coarse grid over the extent of the polygons, assign each polygon to the grid cell containing it's centroid, then take each grid cell group as a cluster. Lee Goddard wrote: I have several million points that compose several thousand polygons, and I'm outputting KMZ. The KMZ is about 2MB, and I'm trying to reduce the size by merging polygons that have adjecent edges, and drop those that are contained within others. I have created to arrays of polygons: one of all unprocessed, one empty. For each unprocessed polygon, I try to compare it the processed, dropping the unprocessed or merging it, as appropriate. This seems frr from ideal. This must be a common task, but being new to JTS and topology in general, I'm not sure if I should be able to find a method to do this for me, or if I should continue trying to do it my own way? ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Merging many polygons
One way you can speed this up is to use a spatial index on your processed polygon set. You'll be updating it as you merge polygons, so it needs to be a Quadtree. Do you have attributes attached to your polygons? If *not*, then you could cluster polygons together (ie spatially by proximity) and then use UnaryUnion to merge them all together at once (ie GeometryCollection.union()) One way to cluster the polygons is to make a coarse grid over the extent of the polygons, assign each polygon to the grid cell containing it's centroid, then take each grid cell group as a cluster. Lee Goddard wrote: I have several million points that compose several thousand polygons, and I'm outputting KMZ. The KMZ is about 2MB, and I'm trying to reduce the size by merging polygons that have adjecent edges, and drop those that are contained within others. I have created to arrays of polygons: one of all unprocessed, one empty. For each unprocessed polygon, I try to compare it the processed, dropping the unprocessed or merging it, as appropriate. This seems frr from ideal. This must be a common task, but being new to JTS and topology in general, I'm not sure if I should be able to find a method to do this for me, or if I should continue trying to do it my own way? Thanks Lee ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] JTS KML?
Lee,
One common cause of slowness in string generation is to use string
concatenation ("+") rather than appending to a StringBuffer. Could that
be what you're experiencing?
Lee Goddard wrote:
Thanks, Martin. I just hoped that there might be a faster in-built
mechanism, but I don't see how that's possible.
Cheers
Lee
Martin Davis wrote:
You mean you want a way to convert JTS objects to KML?
This is pretty straightforward - just write out the text of the KML,
producing the geometry elements by traversing the JTS geometry.
Check out GMLWriter for an example. In fact, as long as you don't
need to use the KML elements which are embedded in the geometry, you
can probably use the GMLWriter directly (or with minor modification).
Hard to see how the efficiency of this process can vary by much. How
are you doing it?
Lee Goddard wrote:
Could someone please recommend a good starting-point for KML from
JTS objects?
Conversion is very slow the way I'm doing it.
Thanks in anticipation
Lee
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] JTS KML?
You mean you want a way to convert JTS objects to KML? This is pretty straightforward - just write out the text of the KML, producing the geometry elements by traversing the JTS geometry. Check out GMLWriter for an example. In fact, as long as you don't need to use the KML elements which are embedded in the geometry, you can probably use the GMLWriter directly (or with minor modification). Hard to see how the efficiency of this process can vary by much. How are you doing it? Lee Goddard wrote: Could someone please recommend a good starting-point for KML from JTS objects? Conversion is very slow the way I'm doing it. Thanks in anticipation Lee ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Obtain rings.
One way to do this is: - create a LineString from the Coordinates - run union() on the LineString - Polygonize the result (using Polygonizer) - extract the shells from the resulting polygons Aritz Dávila wrote: Hi list, I would like to know, if there is any way to do the next: I got a list of Coordinates. Those coordinates form a closed lineString like it is shown on Image1.png I want to obtain the rings that are formed by this lineString (Image2.png). Is there any way to get it, for example using PlanarGraph or other object? -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Performance problem in "intersects"
Glad that worked out for you, Jeff.
Jeff Adams wrote:
So, using SimplePointInAreaLocater for my points improved performance
by a factor of 100!
This is the best mailing list ever ;-). Thanks again!
The polygon-polygon case occurs rarely enough that it isn't a problem,
I just happen to always know one will be small and one will be huge so
I figured it was easy enough to order the arguments if it would make a
difference.
On Tue, Oct 6, 2009 at 3:30 PM, Martin Davis <mailto:mbda...@refractions.net>> wrote:
The order of arguments in the intersects call doesn't make any
difference to performance.
You should be better off using SimplePointInAreaLocater for every
Pt-in-poly call, no matter what the size of the polygon.
Obviously you'll have to use intersects for the polygon-polygon
case (or possibly covers(), if you are really wanting to determine
proper intersection (ie containment))
Jeff Adams wrote:
Thanks, I'm trying that now.
It turns out the time is definitely not evenly spread, I have
a couple large polygons (~1800 points) where the intersection
call takes as much as a second or more, and the majority of
calls take under 50 ms.
Does it matter which way I do the intersection? Would either
of these be faster:
bigGeom.intersects(smallGeom) vs
smallGeom.intersects(bigGeom)
I'm still curious because I have a small subset of cases where
the "search point" is not a point but a small polygon.
Thanks again,
Jeff
On Tue, Oct 6, 2009 at 2:36 PM, Martin Davis
mailto:mbda...@refractions.net>
<mailto:mbda...@refractions.net
<mailto:mbda...@refractions.net>>> wrote:
Try using SimplePointInAreaLocater rather than intersects.
intersects computes a lot of extra information which is not
relevant for simple PiP tests.
And yes, this is an obvious optimization which should be
made to
the code base. Hopefully it will happen soon...
Jeff Adams wrote:
I'm doing a check for intersection and it is going
extremely
slowly, and I was wondering whether anyone might have some
advice for how I could speed it up.
I have a process that iterates over 700,000 points and
determines what polygons they intersect in a group of
polygons.
I'm already using an STRtree to reduce the number of
polygons
I'm actually calling intersects on (typically for each
point
it is only 1 or 2 polygons). Are there any tricks for
point-in-poly lookups?
I'm currently checking whether the time (average 200
ms/intersection) is actually evenly spread, or if I have a
couple polygons in particular that are taking all the
time (it
is possible I have one polygon with a million points
mixed in
there or something).
Thanks,
Jeff
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Jeff Adams
Avencia, Inc.
215-701-7717
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Performance problem in "intersects"
The order of arguments in the intersects call doesn't make any difference to performance. You should be better off using SimplePointInAreaLocater for every Pt-in-poly call, no matter what the size of the polygon. Obviously you'll have to use intersects for the polygon-polygon case (or possibly covers(), if you are really wanting to determine proper intersection (ie containment)) Jeff Adams wrote: Thanks, I'm trying that now. It turns out the time is definitely not evenly spread, I have a couple large polygons (~1800 points) where the intersection call takes as much as a second or more, and the majority of calls take under 50 ms. Does it matter which way I do the intersection? Would either of these be faster: bigGeom.intersects(smallGeom) vs smallGeom.intersects(bigGeom) I'm still curious because I have a small subset of cases where the "search point" is not a point but a small polygon. Thanks again, Jeff On Tue, Oct 6, 2009 at 2:36 PM, Martin Davis <mailto:mbda...@refractions.net>> wrote: Try using SimplePointInAreaLocater rather than intersects. intersects computes a lot of extra information which is not relevant for simple PiP tests. And yes, this is an obvious optimization which should be made to the code base. Hopefully it will happen soon... Jeff Adams wrote: I'm doing a check for intersection and it is going extremely slowly, and I was wondering whether anyone might have some advice for how I could speed it up. I have a process that iterates over 700,000 points and determines what polygons they intersect in a group of polygons. I'm already using an STRtree to reduce the number of polygons I'm actually calling intersects on (typically for each point it is only 1 or 2 polygons). Are there any tricks for point-in-poly lookups? I'm currently checking whether the time (average 200 ms/intersection) is actually evenly spread, or if I have a couple polygons in particular that are taking all the time (it is possible I have one polygon with a million points mixed in there or something). Thanks, Jeff ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Performance problem in "intersects"
Try using SimplePointInAreaLocater rather than intersects. intersects computes a lot of extra information which is not relevant for simple PiP tests. And yes, this is an obvious optimization which should be made to the code base. Hopefully it will happen soon... Jeff Adams wrote: I'm doing a check for intersection and it is going extremely slowly, and I was wondering whether anyone might have some advice for how I could speed it up. I have a process that iterates over 700,000 points and determines what polygons they intersect in a group of polygons. I'm already using an STRtree to reduce the number of polygons I'm actually calling intersects on (typically for each point it is only 1 or 2 polygons). Are there any tricks for point-in-poly lookups? I'm currently checking whether the time (average 200 ms/intersection) is actually evenly spread, or if I have a couple polygons in particular that are taking all the time (it is possible I have one polygon with a million points mixed in there or something). Thanks, Jeff ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] GeometryCollection boundary
Smaller bounding boxes should make the index run faster, not slower. Possibly the re-indexing is taking up a lot of time - although it seems like this should still be faster than brute force search. You might try and look for a kdtree implementation. kdTrees are the fastest way to index sets of points. JTS 1.11 (in CVS) now has a kdtree, but it is not dynamic (ie doesn't support deletion). Justin York wrote: Adding the spatial indexing didn't speed things up -- it actually slowed things down slightly. Could it be that I implemented it poorly? Does the size of the bounding boxes impact it much? I use rather small envelopes. On Mon, Sep 28, 2009 at 9:49 AM, Martin Davis <mailto:mbda...@refractions.net>> wrote: You need to delete the original version and reinsert the new one. Quadtree cannot tell if the member objects have changed while they're in the tree. Justin York wrote: If I move the agents after inserting them into the Quadtree, does the index update itself or do I need to re-insert them with a new envelope? On Mon, Sep 21, 2009 at 9:56 AM, Martin Davis mailto:mbda...@refractions.net> <mailto:mbda...@refractions.net <mailto:mbda...@refractions.net>>> wrote: Further to what Dave said, the updateable spatial index JTS provides is the Quadtree. Using a spatial index for determining neighbours within a given distance is absolutely the way to go - it should speed things up a lot. As David said, you use the spatial index as a primary filter using an appropriate bounding box, and then apply the distance test as a secondary filter. You should use Geometry#withinDistance rather than distance - that allows some further optimization to take place. And Michael was right about why boundary doesn't work on GeometryCollections, and how you might use union to get around that. But for the problem you describe, your approach works just as well. A spatial index would help to speed up testing whether the point lies inside a polygon boundary, but if the operation isn't time critical it may not matter that much. A more sophisticated approach for placing agents might be to create a conformal TIN on the polygonal coverage, and then place the points into a random TIN facet of one of the countries. But that is a LOT more work to code, so almost certainly not worth it. Sometimes brute force is best! Martin David Zwiers wrote: Hi Justin, For part two you can use the index to extract a set of candidate points using a bbox (rectangle) then just test the subset for your circular constraint – this should be faster. You can also select one of the updateable indexes (don’t have the class name off the top of my head), which means you can remove or add the points from the index – you’ll just have to include a little housekeeping code around these operations. David *From:* jts-devel-boun...@lists.jump-project.org <mailto:jts-devel-boun...@lists.jump-project.org> <mailto:jts-devel-boun...@lists.jump-project.org <mailto:jts-devel-boun...@lists.jump-project.org>> [mailto:jts-devel-boun...@lists.jump-project.org <mailto:jts-devel-boun...@lists.jump-project.org> <mailto:jts-devel-boun...@lists.jump-project.org <mailto:jts-devel-boun...@lists.jump-project.org>>] *On Behalf Of *Justin York *Sent:* September 18, 2009 1:09 PM *To:* jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> <mailto:jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org>> *Subject:* Re: [jts-devel] GeometryCollection boundary I had no idea that spatial indexes even existed. Thanks for bringing that to my attention. It doesn't quite work for this specific problems but I'm sure it will help me optimize my model in the future. I'm designing a model which begins by loading any shapefile which defines the borders of countries. Then it randomly places a specified amount of agents within the borders of any of the countries. I s
Re: [jts-devel] need of an advanced "GeomUnion"
Thomas, I did get the full dataset - thanks. I have to say, that is an extremely challenging dataset to process! Many almost- coincident lines, many overlaps, and not much spatial partitioning possible. The last aspect - limited spatial partitioning - is probably why the UnaryUnion is so memory-intensive and takes so long. UnaryUnion doesn't really provide any optimization for overlaying sets of linestrings, in the realm of both performance and memory footprint. I have done some preliminary testing with my new overlay algorithm, and so far it looks promising - it noded the entire dataset at full precision in about 250 sec, using less than 1 GB of memory. I have not yet tried the polygon formation step, however. This will be an excellent test case to have during my algorithm development! 8^) Martin Thomas Leduc wrote: good morning, To be able to process all the 865 polygons (104872 nodes), I have to set those JVM options : -Xmx3072m -XX:+AggressiveHeap, but I also have to reduce the PrecisionModel scale value up to 1 ! Things seem now ok (4th step is quite heavy and still not finished !). I'll then have to evaluate the result... -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] GeometryCollection boundary
You need to delete the original version and reinsert the new one. Quadtree cannot tell if the member objects have changed while they're in the tree. Justin York wrote: If I move the agents after inserting them into the Quadtree, does the index update itself or do I need to re-insert them with a new envelope? On Mon, Sep 21, 2009 at 9:56 AM, Martin Davis <mailto:mbda...@refractions.net>> wrote: Further to what Dave said, the updateable spatial index JTS provides is the Quadtree. Using a spatial index for determining neighbours within a given distance is absolutely the way to go - it should speed things up a lot. As David said, you use the spatial index as a primary filter using an appropriate bounding box, and then apply the distance test as a secondary filter. You should use Geometry#withinDistance rather than distance - that allows some further optimization to take place. And Michael was right about why boundary doesn't work on GeometryCollections, and how you might use union to get around that. But for the problem you describe, your approach works just as well. A spatial index would help to speed up testing whether the point lies inside a polygon boundary, but if the operation isn't time critical it may not matter that much. A more sophisticated approach for placing agents might be to create a conformal TIN on the polygonal coverage, and then place the points into a random TIN facet of one of the countries. But that is a LOT more work to code, so almost certainly not worth it. Sometimes brute force is best! Martin David Zwiers wrote: Hi Justin, For part two you can use the index to extract a set of candidate points using a bbox (rectangle) then just test the subset for your circular constraint – this should be faster. You can also select one of the updateable indexes (don’t have the class name off the top of my head), which means you can remove or add the points from the index – you’ll just have to include a little housekeeping code around these operations. David *From:* jts-devel-boun...@lists.jump-project.org <mailto:jts-devel-boun...@lists.jump-project.org> [mailto:jts-devel-boun...@lists.jump-project.org <mailto:jts-devel-boun...@lists.jump-project.org>] *On Behalf Of *Justin York *Sent:* September 18, 2009 1:09 PM *To:* jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> *Subject:* Re: [jts-devel] GeometryCollection boundary I had no idea that spatial indexes even existed. Thanks for bringing that to my attention. It doesn't quite work for this specific problems but I'm sure it will help me optimize my model in the future. I'm designing a model which begins by loading any shapefile which defines the borders of countries. Then it randomly places a specified amount of agents within the borders of any of the countries. I solved that problem by combining the envelopes of all the countries, calculating the centroid, then randomly creating a point away from the centroid but still within the envelope, and then making sure that point lies within the borders of one of the countries. That is all just initialization of the model. The placement of 600 agents in Southeast Asia and some of the Indonesian islands took 3445 attempts in a matter of seconds. I'm not too concerned about that, but if anyone has a cleaner idea please do share. Spatial indexing doesn't seem as though it would quite work from the limited amount of understanding I could gain in a few minutes. What now concerns me is the speed of running the model. Each turn, all agents move and interact with other agents within a specified radius (neighbors). Currently to calculate the neighbors I iterate over all agents and calculate the distance between them. I imagine this is where spatial indexing could make a huge difference, however it seems to only work with rectangles. In addition, since the agents move, it seems as though I'd have to reconstruct the index each turn. If that is true, would it still be worth rebuilding the index? I imagine there's a certain threshold where it would be worth it -- I guess I would just have to find it. Hi Justin, > When I try to use the getBoundary() method on a GeometryCollection I > get the following error: > java.lang.IllegalArgumentException: This metho
Re: [jts-devel] need of an advanced "GeomUnion"
Thomas Leduc wrote: Yes, indeed, a CoordinatePrecisionReduceFilter applied to each boundary is enough. What remains annoying is that the polygonization output (I mean the number of output polygons) is a function of the scale of the PrecisionModel : scale = 1.0E4 -> 77 polygons, scale = 1E5 -> 93 polygons... Visually, both results seem correct. I think that's because there's a lot of precision in the data, and a lot of "noise" - eg linework which is almost but not quite coincident. This linework will tend to create lots of sliver polygons at high precision values. What you have to decide is how relevant those sliver polygons are to your actual use case. (To help decide this, you might want to use a tool like JUMP to have a look at the extra polygons which are created) When I try to apply this process to the real set of polygons, I face an out of memory error (even with a -XX:+AggressiveHeap JVM option) during the UnaryUnionOp.union task (with a scale equals to 1E5 - I'll retry with a shorter value). Hmmm. How many polygons and vertices are in the input? Do you have the JVM -Xmx memory size parameter set as high as you can? Other than that, there may not be much that can be done using the current code. However, if you can send me the full dataset off-list, I can try and see whether my new overlay algorithm can handle this. Concerning the SimpleSnapRounder I don't know how to use it. Is it possible for you to tell me more ? Thomas, are you able to download the current codebase from CVS? I've been adding some code today to allow trying out Snap Rounding on your sample data. The easiest thing would be for you to look at the new code - I can point you to where it is. Best regards et "/merci beaucoup/", -- Thomas LEDUC ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] need of an advanced "GeomUnion"
Thomas Leduc wrote: Good morning, I've implemented the 4 steps mentioned above. On a really simple example (the one of the image sent yesterday), result is ok if I test with an interior point as written in step 4. Problem is indeed with the noding step. What I've tried to do in the linework extraction is : - for each input polygon boundary called "boundary", - instead of just adding it as it is to the linework collection, - use : GeometrySnapper snapper = new GeometrySnapper(boundary); double snapTolerance = GeometrySnapper.computeSizeBasedSnapTolerance(boundary); and add the "snapper.snapTo(boundary, snapTolerance)" result to the linework collection. I still have the exception even if I increase the snapTolerance value up to 0.01 What I am doing wrong ? Thomas, The GeometrySnapper is really only intended for a very specific use case, so it isn't too surprising that it doesn't help in this situation. It doesn't implement full-blown snap rounding. There is a SimpleSnapRounder class which you could try and use (although it might be slowish) Or, have you tried reducing the precision of the input coordinates? Many thanks for your help, once again. -- Thomas LEDUC ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] need of an advanced "GeomUnion"
Polygonizer only operates on properly noded input, so you need to node the linework of the input polygons first. So the steps are: 1) Extract the linework (boundaries) of the source polygons 2) Node the linework. UnaryUnionOp is a convenient way to do this (Union on a set of LineStrings has the effect of noding them) 3) Pass the noded linework into Polygonizer and polygonize it 4) For each resultant polygon, determine an interior point and then find the source polygons which contain this point. You will definitely want a spatial index for this. Using a PreparedGeometry would improve speed further, at the cost of using more memory. Two caveats: 1. When I tried UnaryUnionOp on your sample data, I got a TopologyException during noding, caused by rounding error. One easy way to avoid this is to reduce the precision of the input linework (essentially snap it to a grid). I tried reducing precision to 5 decimal places and it then worked fine (A more theoretically correct approach is to use snap-rounding during noding - but there's no convenient way to do this in JTS yet. Also my new coverage noding code doesn't exhibit this problem, so this may just be an overly-cautious QA check in the current union code.) 2. The Point-In-Polygon test is theoretically subject to error for some pathological input polygons (eg very skinny ones). Hopefully this won't matter - or if it does cause a problem there's probably a workaround using a filter step and a more exact test (ie test if the interiors intersect using relate, which is expensive but accurate). Of course, reducing precision complicates this a bit more, since the output is then slightly shifted from the input. But if you're requiring that level of accuracy, you need a more sophisticated approach anyway. Thomas Leduc wrote: Hi Martin, I'm glad to read your answer. On Wed, Sep 23, 2009 at 6:48 PM, Martin Davis <mailto:mbda...@refractions.net>> wrote: 2) Use Noding and Polygonization to create a polygonal coverage from the linework of the input polygons, and then determine the parent count of the polygons in the coverage by running Point-In-Polygon tests against the input dataset (using a spatial index for performance) To rephrase your advice, I should : - call the Polygonizer.add(Collection) method with the collection of input polygons as argument, - and, then, for each Polygonizer.getPolygons() item, increment the counter each time it is included in an input Polygon (using a STRtree on the input data set - that I can 1st convert into a set of PreparedPolygon so as to take benefit from its contains() method). That's it ? I am working on new code to perform a true polygon coverage overlay, but this is not ready for release yet. Out of curiosity, could you provide a sample dataset of your polygons? Yes, please see attached zip file. Thank you for your help. -- Thomas LEDUC ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] need of an advanced "GeomUnion"
Thomas, To rephrase your problem in a more standard terminology, what you're looking for is a way of building a polygonal coverage from a set of overlapping input polygons. (The step of attributing the resultant polygons with the count of their parents is a minor extension to this basic algorithm). Unfortunately currently JTS does not offer such a capability directly. It is possible to simulate this functionality in a couple of different ways: 1) Use the Polygon overlay operations to compute intersections and differences. However, this is complicated and very inefficient 2) Use Noding and Polygonization to create a polygonal coverage from the linework of the input polygons, and then determine the parent count of the polygons in the coverage by running Point-In-Polygon tests against the input dataset (using a spatial index for performance) I would recommend trying #2. I am working on new code to perform a true polygon coverage overlay, but this is not ready for release yet. Out of curiosity, could you provide a sample dataset of your polygons? Martin Thomas Leduc wrote: Dear JTS members, Many thanks for this lib and all functionalities it provides. Vitality of this mailing list is a proof of the strong interest of the community for it. I'm used to use the JTS-1.10 static method "UnaryUnionOp.union(Geometry geom)". It is indeed incredibly efficient. I wonder whether it exists an implementation able to : - process a java.util.Collection as input data, - so as to return a new java.util.Map as output data respecting following conditions : + the output Collection of polygons must be a partition of the global geometry union of the input polygons (I mean: overlap areas dimension are equals to 1: MultiLineString), + for each output polygon, the integer value (key of the Map) corresponds to a counter : number of occurrences of the current ouput Polygon in the input Collection of Polygon (each time it is included in an input Polygon, I increment the counter). To sum up, let me present you a small example with just 3 polygons (please see attached image) : - let A, B and C the input polygons, - what I want as output result is a Map composed of the following 7 items : A.difference(B).difference(C) ; counter = 1 B.difference(A).difference(C) ; counter = 1 C.difference(A).difference(B) ; counter = 1 A.intersection(B).difference(C) ; counter = 2 A.intersection(C).difference(B) ; counter = 2 B.intersection(C).difference(A) ; counter = 2 A.intersection(B).intersection(C) ; counter = 3 Thanks a lot for your ideas, PS : I've about thousands polygons to process (several times). -- Thomas LEDUC ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Geometry#isValid
Ok, John, I see what's going on now. You've found a sneaky little bug
in JTS. The Point#isValid method was not checking for ordinate values
of NaN.
Lineal and Polygonal geometries are not affected by this bug.
I've fixed this in CVS, and it will appear in JTS 1.11
Martin
john.c.cartwri...@noaa.gov wrote:
Hi Martin,
a little further investigation showed that the comma was being stripped
out before WKTReader got to the String, but it still looks like NaN is
being treated as valid - is this correct?
Thanks for your help!
--john
public void testWktParse() throws ParseException{
String wkt = null;
Geometry geometry = null;
wkt = "POINT (10 10)";
geometry = wktReader.read(wkt);
assertNotNull(geometry);
assertTrue(geometry.isValid());
wkt = "POINT (10, 10)";
try {
geometry = wktReader.read(wkt);
fail("should have seen ParseException");
} catch (ParseException e) {
}
wkt = "POINT (10 NaN)";
geometry = wktReader.read(wkt);
assertNotNull(geometry);
assertFalse("NaN coordinate",geometry.isValid());
}
- Original Message -
From: Martin Davis
Date: Monday, September 21, 2009 6:14 pm
Subject: Re: [jts-devel] Geometry#isValid
If you're using 1.10 then I'm puzzled by what you're seeing.
Can you post code that exhibits the problem?
John Cartwright wrote:
Thanks for the prompt reply and sorry I omitted the version - 1.10.
--john
Martin Davis wrote:
What version of JTS are you using?
"POINT(1,2)" should not parse as correct WKT. And for several
versions now isValid() has checked for Coordinates with NaN
ordinate>> values.
John Cartwright wrote:
Hello All,
I notice that if I create a invalid geometry using a WKT string
like>>> "POINT(1,2)", the resulting Geometry still returns true on
a call to
it's isValid() method. point.getCoordinate.y in this case
shows NaN.
Is the isValid procedure supposed to do this? Is there another
way to
determine whether a Geometry does not contain NaN or a better
way to
protect against invalid WKT strings?
Thanks!
--john
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Geometry#isValid
If you're using 1.10 then I'm puzzled by what you're seeing. Can you post code that exhibits the problem? John Cartwright wrote: Thanks for the prompt reply and sorry I omitted the version - 1.10. --john Martin Davis wrote: What version of JTS are you using? "POINT(1,2)" should not parse as correct WKT. And for several versions now isValid() has checked for Coordinates with NaN ordinate values. John Cartwright wrote: Hello All, I notice that if I create a invalid geometry using a WKT string like "POINT(1,2)", the resulting Geometry still returns true on a call to it's isValid() method. point.getCoordinate.y in this case shows NaN. Is the isValid procedure supposed to do this? Is there another way to determine whether a Geometry does not contain NaN or a better way to protect against invalid WKT strings? Thanks! --john ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Geometry#isValid
What version of JTS are you using? "POINT(1,2)" should not parse as correct WKT. And for several versions now isValid() has checked for Coordinates with NaN ordinate values. John Cartwright wrote: Hello All, I notice that if I create a invalid geometry using a WKT string like "POINT(1,2)", the resulting Geometry still returns true on a call to it's isValid() method. point.getCoordinate.y in this case shows NaN. Is the isValid procedure supposed to do this? Is there another way to determine whether a Geometry does not contain NaN or a better way to protect against invalid WKT strings? Thanks! --john ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] GeometryCollection boundary
not union my polygons, instead, I would use a spatial index (STRTree). I see two benefits: * you iterate only over good candidates, not all polygons * for each point, you do within tests with a few simple polygon, not with a huge one Hope that helps Micha?l ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] [Fwd: Re: UnionOP for huge polygon collection]
And if you really just want the coordinates of the outer shell of the
polygon, and are willing to ignore any multipolygon output, you could use:
return ( (Polygon) allinOnePolygon.getGeometryN(0)
).getExteriorRing().getCoordinates();
Martin Davis wrote:
Markus,
Thanks for the test data. I ran this with no problems in JTS, in
about 2.7 sec on my machine. (See the attached image)
One thing I noticed about the code you provide is the line in
UnionWithUnionOp:
return allinOnePolygon.getCoordinates();
This will not give you useful results if the allinOnePolygon geometry
is a MultiPolygon and/or has holes. getCoordinates() concatenates all
coordinate sequences together, which when display will have an
appearance which I think looks like what you're seeing. I think you
need more checks for the actual polygon structure in that routine.
Really you're better off returning the actual geometry created, not
the list of vertices in it.
Martin
Markus Eichhorn wrote:
Hi Martin,
I already got an workaround. With a combination of
CascadedPolygonUnion and the Polygonizer I found a workaround.
But this is more slowly than it could be.
Appending a test shape.
In short, the following code is the on giving me the incorrect
result, which looks like the picture (the picture is from another
test case, but explains what I suppose).
...
DataStore dataStore =
DataStoreFinder.getDataStore(connectParameters); // getting the shape
FeatureSource featureSource;
FeatureCollection collection;
FeatureIterator iterator;
featureSource = dataStore.getFeatureSource(typeName);
collection = featureSource.getFeatures();
iterator = collection.features();
ArrayList allPolygons= new ArrayList();
Geometry onePoly;
while (iterator.hasNext()) {
SimpleFeature feature = iterator.next();
onePoly= (Geometry)
feature.getDefaultGeometry();
allPolygons.add(onePoly);
}
return UnionWithUnionOp(allPolygons);
}
With
private Coordinate[] UnionWithUnionOp(ArrayList allPolygons){
Geometry allinOnePolygon = UnaryUnionOp.union(allPolygons);
return allinOnePolygon.getCoordinates();
}
So, you needn't to go into it. I can work with myworkaround. But if
you want to, you're welcome!
Greets & Thanks
Markus
2009/9/15 Martin Davis <mailto:mbda...@refractions.net>>
Markus,
Your approach is exactly right - that's what UnaryUnionOp is
designed to do. I'm not sure why you're seeing incorrect results
- the output seems very strange. If you can post some test data or
even better a simple test case I can dig into this to see what's
going on.
Another post suggested noding first. This is not necessary,
UnaryUnionOp does any noding required.
Martin
Markus Eichhorn wrote:
Hi list,
I've been trying to union a collection of Geometry-object (all
elements are polygons). But with the
geometry.union(other); it is much to slow for huge collection.
So I used the UnaryUnionOp (see code).
private Coordinate[] UnionWithUnionOp(ArrayList
allPolygons){
Geometry allinOnePolygon =
UnaryUnionOp.union(allPolygons);
return allinOnePolygon.getCoordinates();
}
After union the polygons with the UnaryUnionOp the order of
coordinates of the result polygon is not right ( I think,
because of the polygons are not ordered and distributed all
over the space). So I get an self overlapping polygon which
makes lots of problems for the visualisation.
Is my handling of the UnaryUnionOp false? Or can't I handle
such spread polygons with it?
Thanks for answers or hints!
Greets
Markus
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
-- Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
----
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] UnionOP for huge polygon collection
Markus,
Your approach is exactly right - that's what UnaryUnionOp is designed to
do. I'm not sure why you're seeing incorrect results - the output seems
very strange. If you can post some test data or even better a simple
test case I can dig into this to see what's going on.
Another post suggested noding first. This is not necessary, UnaryUnionOp
does any noding required.
Martin
Markus Eichhorn wrote:
Hi list,
I've been trying to union a collection of Geometry-object (all
elements are polygons). But with the
geometry.union(other); it is much to slow for huge collection.
So I used the UnaryUnionOp (see code).
private Coordinate[] UnionWithUnionOp(ArrayList allPolygons){
Geometry allinOnePolygon = UnaryUnionOp.union(allPolygons);
return allinOnePolygon.getCoordinates();
}
After union the polygons with the UnaryUnionOp the order of
coordinates of the result polygon is not right ( I think, because of
the polygons are not ordered and distributed all over the space). So I
get an self overlapping polygon which makes lots of problems for the
visualisation.
Is my handling of the UnaryUnionOp false? Or can't I handle such
spread polygons with it?
Thanks for answers or hints!
Greets
Markus
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Welcome & buffering
Welcome, Paul. Glad you spoke up - I'll add your products to the list I'm keeping of clients of JTS/GEOS: http://tsusiatsoftware.net/jts/jts-links.html As for your question, at the moment JTS assumes a Cartesian (planar) coordinate system. So there is no provision for processing geometries in spheroidal coordinate systems, as would be required to produce the kind of output you're talking about. If you only need buffers around points, then it would be relatively straightforward to implement this as a custom function. You would have to obtain code to compute distance and azimuth on the spheroid in order to do this - there is code for this in PostGIS, I believe. We have been discussing the possibility of extending JTS operations to allow spherical coordinate systems. This is feasible, but would involve a bit of work. If you're interested in discussing this further let me know. Martin Paul Meems wrote: I'm new to this mailing list so I do a quick introduction of myself. I'm Paul Meems. I live in The Netherlands and I am active in the MapWindow GIS community (www.mapwindow.org <http://www.mapwindow.org>) With MapWindow we don't use JTS directly but use NTS and GEOS. With both libraries we've got issues. Because they both implement JTS I thought the best way to get answers and/or fixes is at the source ;) The first issue we have is when we create a very large buffer on a shapefile with a projection bases on an ellipsoide (WGS84) we expect a buffer more as an ellipse instead of a circle. Using these coordinates: -102,040052163025, 36,9876952244059 a distance of 18 (degrees) and this projection: GEOGCS["WGS 84" ,DATUM["WGS_1984" ,SPHEROID["WGS 84" ,6378137,298.257223563 ,AUTHORITY["EPSG","7030"]] ,TOWGS84[0,0,0,0,0,0,0] ,AUTHORITY["EPSG","6326"]] ,PRIMEM["Greenwich",0,AUTHORITY["EPSG","8901"]] ,UNIT["degree",0.0174532925199433,AUTHORITY["EPSG","9108"]] ,AUTHORITY["EPSG","4326"]] This would create a buffer starting at the center of USA and almost as wide as the total width of USA and higher as the total height of the USA. Is my assumption wrong and should it not create an ellipse? Or should I not use the Buffer method but a different one? I'm sorry if this is already documented. I tried searching for it but couldn't find it. Thanks, Paul ---- ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] LineString gap repair and noding
Adding some indexing would probably make an improvement. LineStringSnapper was not designed for bulk operations on large sets of geometries, so it doesn't necessarily take the most efficient approach in this situation. Since you'll be modifying the geometries which are in the index, you'll have to take some care in how you implement this. You could either index the geometries with a bounding box which is enlarged by the maximum tolerance you might modify geometries, or use an updatable index like Quadtree and replace the geometries when they are modified. Using a noder rather than a cascaded union would also probably make a difference. The cascaded union is likely doing a lot of repeat indexing and noding, which using a noder directly would avoid. Since you're dealing with linestrings you have a relatively easy task - they do not have the same requirements for topological consistency as would polygons. So it should be straightforward for you to implement the above changes. Martin Björn Harrtell wrote: Hi, I'm using JTS to repair collections of 2D LineString geometries that have gaps. To to this I use the LineStringSnapper class looping through all lines against all coordinates for all linestrings. At first I experimented with the snap rounding noders, but afaik their purpose is not to repair gaps below a certain tolerance as in my case. LineStringSnapper seem to do what I want but since it seem to be brute force it is understandably slow with large datasets. Is there any obvious way to to what I want to get done in a more effective manner or should I try to improve the LineStringSnapper with indexing? Also, since I'm noding the result I have been wondering if should dig into the noders of JTS instead of using "cascading" unions for performance reasons? With regards, /Björn Harrtell ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Adding geometry to a planar graph
See http://tsusiatsoftware.net/jts/main.html for a link to the download site on Sourceforge. The most current download archive will have all the source in it. The docs you list are all there is, and they're pretty old unfortunately. The Javadoc is much more current, however. Mark Coletti wrote: On Thu, Aug 27, 2009 at 5:00 PM, Martin Davis wrote: First of all, use PlanarGraph, not GeometryGraph. The latter is really only suitable for internal use. Ah ha. That would explain the weird undocumented GeometryGraph ctor. I was pulling my hair out wondering why it wanted an integer argument. Your best bet is to look at existing source code to see how to use PlanarGraphs. Have a look at the source in the com.vividsolutions.jts.operation.polygonize pacakge. I suppose part of the problem here is that I have a jar file and not much source. This is all the source I have: ./src/com/vividsolutions/jts/JTSVersion.java ./src/com/vividsolutions/jtsexample/operation/polygonize/PolygonizeExample.java ./src/com/vividsolutions/jtsexample/operation/linemerge/LineMergeExample.java ./src/com/vividsolutions/jtsexample/operation/distance/ClosestPointExample.java ./src/com/vividsolutions/jtsexample/precision/EnhancedPrecisionOpExample.java ./src/com/vividsolutions/jtsexample/geom/ExtendedCoordinateSequenceFactory.java ./src/com/vividsolutions/jtsexample/geom/BasicExample.java ./src/com/vividsolutions/jtsexample/geom/ExtendedCoordinateSequence.java ./src/com/vividsolutions/jtsexample/geom/SimpleMethodsExample.java ./src/com/vividsolutions/jtsexample/geom/ExtendedCoordinateExample.java ./src/com/vividsolutions/jtsexample/geom/PrecisionModelExample.java ./src/com/vividsolutions/jtsexample/geom/ConstructionExample.java ./src/com/vividsolutions/jtsexample/geom/ExtendedCoordinate.java ./src/com/vividsolutions/jtsexample/technique/LineStringSelfIntersections.java ./src/com/vividsolutions/jtsexample/technique/PolygonUnionUsingBuffer.java ./src/com/vividsolutions/jtsexample/linearref/LinearRefExample.java ./jtsio/src/com/vividsolutions/jts/io/oracle/OraWriter.java ./jtsio/src/com/vividsolutions/jts/io/oracle/OraReader.java ./jtsio/src/com/vividsolutions/jts/io/oracle/Constants.java ./jtsio/src/com/vividsolutions/jts/io/gml2/GeometryStrategies.java ./jtsio/src/com/vividsolutions/jts/io/gml2/GMLWriter.java ./jtsio/src/com/vividsolutions/jts/io/gml2/GMLHandler.java ./jtsio/src/com/vividsolutions/jts/io/gml2/GMLConstants.java ./jtsio/src/com/vividsolutions/jts/io/gml2/GMLReader.java ./jtsio/test/com/vividsolutions/jts/io/oracle/ConnectedTestCase.java ./jtsio/test/com/vividsolutions/jts/io/oracle/StaticPolygonTest.java ./jtsio/test/com/vividsolutions/jts/io/oracle/StaticMultiPointTest.java ./jtsio/test/com/vividsolutions/jts/io/oracle/StaticPointTest.java ./jtsio/test/com/vividsolutions/jts/io/oracle/StaticMultiLineStringTest.java ./jtsio/test/com/vividsolutions/jts/io/oracle/StaticMultiPolygonTest.java ./jtsio/test/com/vividsolutions/jts/io/oracle/StaticLineStringTest.java ./jtsio/test/com/vividsolutions/jts/io/gml2/GMLReaderTestCase.java ./jtsio/test/com/vividsolutions/jts/io/gml2/StaticPolygonTest.java ./jtsio/test/com/vividsolutions/jts/io/gml2/StaticMultiPointTest.java ./jtsio/test/com/vividsolutions/jts/io/gml2/StaticPointTest.java ./jtsio/test/com/vividsolutions/jts/io/gml2/StaticMultiLineStringTest.java ./jtsio/test/com/vividsolutions/jts/io/gml2/WritingTestCase.java ./jtsio/test/com/vividsolutions/jts/io/gml2/StaticMultiPolygonTest.java ./jtsio/test/com/vividsolutions/jts/io/gml2/StaticLineStringTest.java ./jtsio/test/com/vividsolutions/jts/generator/PointGenerator.java ./jtsio/test/com/vividsolutions/jts/generator/PolygonGenerator.java ./jtsio/test/com/vividsolutions/jts/generator/LineStringGenerator.java ./jtsio/test/com/vividsolutions/jts/generator/GeometryGenerator.java ./jtsio/test/com/vividsolutions/jts/generator/GridGenerator.java ./jtsio/test/com/vividsolutions/jts/generator/MultiGenerator.java I'm not sure where I got my JTS stuff, so maybe I just blundered into an ancient download page. Can you could point me to a better source for getting the source? You're no doubt right that the Javadoc for PlanarGraph needs work, and I'm happy to add to it if you can provide some specific things that could be improved. No problem, I'll be happy to do so. But really the PlanarGraph API is a suite of classes that all need to work together, and this situation is usually better understood by examples or more general purpose doc than simply the Javadoc (e.g. ever tried to learn Swing from the Javadoc?) Well, I *did* try to get guidance from reading the ancillary documentation, but didn't have much joy there. However, it may be that I as looking at stale documentation or missed some other relevant JTS document. Or I could have just missed a relevant section of the documents I have. These are the documents I read that were included in the distr
Re: [jts-devel] Adding geometry to a planar graph
First of all, use PlanarGraph, not GeometryGraph. The latter is really
only suitable for internal use.
Your best bet is to look at existing source code to see how to use
PlanarGraphs. Have a look at the source in the
com.vividsolutions.jts.operation.polygonize pacakge.
You're no doubt right that the Javadoc for PlanarGraph needs work, and
I'm happy to add to it if you can provide some specific things that
could be improved. But really the PlanarGraph API is a suite of classes
that all need to work together, and this situation is usually better
understood by examples or more general purpose doc than simply the
Javadoc (e.g. ever tried to learn Swing from the Javadoc?)
Martin
Mark Coletti wrote:
I have a set of LineStrings from which I would like to create a
PlanarGraph. Seems straightforward enough, but I cannot see in the
existing set of JTS classes any mechanism for doing so. So I'm left
with handcrafting Edges and Nodes from LineStrings, which doesn't seem
to be working out too well:
ArrayList edges = new ArrayList();
for (int i = 0; i < geometries.numObjs; i++)
{
if ( geometries.get(i) instanceof LineString )
{
LineString lineString = (LineString) geometries.get(i);
Edge edge = null;
for (LinearIterator it = new LinearIterator(lineString);
it.hasNext(); it.next())
{
graph_.addNode(it.getSegmentStart());
graph_.addNode(it.getSegmentEnd());
Coordinate [] edgeCoords =
{it.getSegmentStart(),it.getSegmentEnd()};
edge = new Edge(edgeCoords);
try
{
edges.add(edge);
}
catch (Exception e)
{
System.err.println("Unable to add edge: " + e);
break;
}
}
}
}
graph_.addEdges(edges); // EXCEPTION THROWN HERE
I suspect I'm going about this all wrong, but there is no or little
high level documentation on planar nor geometry graphs. Indeed many
of the member functions have no documentation. E.g., the
GeometryGraph ctor takes an integer argument and there is no
corresponding explanation for this argument.
Anyone have suggestions on what I should do?
Cheers!
Mark
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] CVS JTS 1.10
I'm happy using ant, but if you want to provide a maven pom and someone else says they want it too I will stuff it into CVS. Jody Garnett wrote: Sure you don't want a maven pom.xml (I think we could produce that faster). Jody On Thu, Aug 20, 2009 at 1:53 AM, Martin Davis wrote: Good idea about moving this thread to the JTS list - I'm sending it over there with this email. The duplicate IndexedPointInAreaLocator is a bug in the src image extracted for JTS 1.10. The fix is to delete the one in the algorithm package. Then you should be able to compile. I agree it would be nice to have an ant script which builds the distro. If you make one I'd be happy to add it to CVS. And you're able to commit to maintaining it, that would even better! It's too late to tag CVS for 1.10, obviously, but I'll tag the 1.11 release when it's ready to go (hopefully very soon - there's just one code enhancement it's waiting on). Does this cover everything? Martin Alex Djioev wrote: Hi Martin, First quiesion: should we move this discussion to the mailing list? I tried to do what you suggested, but code is still not compilable. I get compile errors for example IndexedPointInAreaLocator.java is in jts.algorithm and jts.algorithm.locate packages, also they are different in sizes and jts.geomgraph.GeometryGraph class breaks as it doesn't know which one to pick. I can fix it, but I'm afraid documentation might look bad, i.e.: get source code package and unzip, chechout code from cvs and move ant file, patch ant script, clean source tree by removing some java files. Its too much... Another solution I can see is to make a new JTS release (version 1.13) *and* tag the code for this release. Alex Jody Garnett wrote: I am suer we could; there is an email thread on the jts list on this topic. We had also thought of just build the source download; supplemented with the ant file from CVS. But we thought we should at least warn you that the tags are broken in CVS. If you did want to create a new tag (or perhaps Alex can tell me if one of the other tags works?) we would be happy to give you feedback. Jody -Original Message- From: Martin Davis [mailto:mbda...@refractions.net] Sent: Wednesday, 19 August 2009 1:43 AM To: Jody Garnett Cc: Alexandre Djioev Subject: Re: CVS JTS 1.10 Hi, Jody. Today at 6 pm doesn't work for me, I"m afraid. Perhaps we can try and do this by email? If the issue is building JTS 1.10, then the best way to do this is to get the src from the distro archive, and then build it. It's just a Java compile - pretty simple, really. Alternatively, grab the ant file from CVS and use it (probably with some hacking) to get it to gen the build. The reason the ant file is not included in the distro is that not all src files are included - so it doesn't run on the src image in the distro. HTH - Martin Jody Garnett wrote: Hi Martin: If we could talk briefly tomorrow - Here is a meeting planner: - http://www.timeanddate.com/worldclock/meetingtime.html?month=8&day=19&year=2009&p1=240&p2=256&p3=-1&p4=-1 It looks like 6pm PST would be perfect? Jody -Original Message- From: Martin Davis [mailto:mbda...@refractions.net] Sent: Tuesday, 18 August 2009 4:42 AM To: Jody Garnett Cc: Alexandre Djioev Subject: Re: CVS JTS 1.10 Jody, I'm happy to skype about this, but I can't do that from Refractions, due to our antiquated infrastructure. How about I talk from home? That might work better for your time zone anyway. Evenings PST are best for me. What would work for you? M Jody Garnett wrote: Hi Martin: Do you have time for a skype chat? We are trying to build (for a customer) all the dependencies of uDig and write down the steps. Right now we are using JTS 1.10 and the structure of CVS seems to have lost that particular tag. Our best workaround seems to be: 1. Download jts 1.10 2. Check out the ant script 3. And run? Jody Garnett Geospatial Systems Architect http://www.lisasoft.com/docroot/lisasoft/images/lisasoftlogo.jpg Ph: +61 2 8570 5050 Fax: +61 2 8570 5099 Suite 112, Jones Bay Wharf 19-21 Pirrama Rd Pyrmont NSW 2009 LISAsoft is part of the A2end Group of Companies http://www.lisasoft.com/ -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] CVS JTS 1.10
Good idea about moving this thread to the JTS list - I'm sending it over there with this email. The duplicate IndexedPointInAreaLocator is a bug in the src image extracted for JTS 1.10. The fix is to delete the one in the algorithm package. Then you should be able to compile. I agree it would be nice to have an ant script which builds the distro. If you make one I'd be happy to add it to CVS. And you're able to commit to maintaining it, that would even better! It's too late to tag CVS for 1.10, obviously, but I'll tag the 1.11 release when it's ready to go (hopefully very soon - there's just one code enhancement it's waiting on). Does this cover everything? Martin Alex Djioev wrote: Hi Martin, First quiesion: should we move this discussion to the mailing list? I tried to do what you suggested, but code is still not compilable. I get compile errors for example IndexedPointInAreaLocator.java is in jts.algorithm and jts.algorithm.locate packages, also they are different in sizes and jts.geomgraph.GeometryGraph class breaks as it doesn't know which one to pick. I can fix it, but I'm afraid documentation might look bad, i.e.: get source code package and unzip, chechout code from cvs and move ant file, patch ant script, clean source tree by removing some java files. Its too much... Another solution I can see is to make a new JTS release (version 1.13) *and* tag the code for this release. Alex Jody Garnett wrote: I am suer we could; there is an email thread on the jts list on this topic. We had also thought of just build the source download; supplemented with the ant file from CVS. But we thought we should at least warn you that the tags are broken in CVS. If you did want to create a new tag (or perhaps Alex can tell me if one of the other tags works?) we would be happy to give you feedback. Jody -Original Message- From: Martin Davis [mailto:mbda...@refractions.net] Sent: Wednesday, 19 August 2009 1:43 AM To: Jody Garnett Cc: Alexandre Djioev Subject: Re: CVS JTS 1.10 Hi, Jody. Today at 6 pm doesn't work for me, I"m afraid. Perhaps we can try and do this by email? If the issue is building JTS 1.10, then the best way to do this is to get the src from the distro archive, and then build it. It's just a Java compile - pretty simple, really. Alternatively, grab the ant file from CVS and use it (probably with some hacking) to get it to gen the build. The reason the ant file is not included in the distro is that not all src files are included - so it doesn't run on the src image in the distro. HTH - Martin Jody Garnett wrote: Hi Martin: If we could talk briefly tomorrow - Here is a meeting planner: - http://www.timeanddate.com/worldclock/meetingtime.html?month=8&day=19&year=2009&p1=240&p2=256&p3=-1&p4=-1 It looks like 6pm PST would be perfect? Jody -Original Message- From: Martin Davis [mailto:mbda...@refractions.net] Sent: Tuesday, 18 August 2009 4:42 AM To: Jody Garnett Cc: Alexandre Djioev Subject: Re: CVS JTS 1.10 Jody, I'm happy to skype about this, but I can't do that from Refractions, due to our antiquated infrastructure. How about I talk from home? That might work better for your time zone anyway. Evenings PST are best for me. What would work for you? M Jody Garnett wrote: Hi Martin: Do you have time for a skype chat? We are trying to build (for a customer) all the dependencies of uDig and write down the steps. Right now we are using JTS 1.10 and the structure of CVS seems to have lost that particular tag. Our best workaround seems to be: 1. Download jts 1.10 2. Check out the ant script 3. And run? Jody Garnett Geospatial Systems Architect http://www.lisasoft.com/docroot/lisasoft/images/lisasoftlogo.jpg Ph: +61 2 8570 5050 Fax: +61 2 8570 5099 Suite 112, Jones Bay Wharf 19-21 Pirrama Rd Pyrmont NSW 2009 LISAsoft is part of the A2end Group of Companies http://www.lisasoft.com/ -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] No outgoing dirEdge found
271170.57245635585,2667992.4131387016 271004.52606006869,2667988.6785943792 271000.84408189094,2667901.8857915569 270917.48856856587,2667881.9930221392 270920.08801217284,2667863.4959993367 270925.2169905582,2667855.1220021732 270928.3499937749,2667838.6 25982428 270938.80800250638,2667820.9199819015 270953.36301544425,2667806.3129979977 270970.4890199888,2667795.9379977765 270985.53802300256,2667783.4849807783 271005.16999501467,2667774.1379904393 271026.77101398323,2667769.2479818077 271045.0920123324,2667766.6218780275 271057.94761583704,2667853.60586295 271141.48673980223,2667853.6992265582 271141.57878925663,2668022.3196221939 271312.24299189146,2668052.261867119 271338.76327167032)),((2668621.8039101921 271893.83875994524,2668708.5939935953 271980.05501039221,2668758.5100035211 272029.43202096823,2668999.5870229555 272266.36499642872,2669047.6259866212 272313.83401989029,2669169.9609996877 272433.26798945636,2669156.2770201415 272447.82701503631,2669152.384353 272452.05899871938,2669047.580358685 272566.76951774844,2669059.07927251 272577.26455523784,2669061.0325510185 272579.0239182724,2669252.65517089 272749.35514644865,2669259.3896421669 272755.61424267356,2669363.4889845452 272657.6209937259,2669382.50097919 27 2639.72398176993,2669193.6269822605 272456.27198278415,2669204.2892292626 272445.46197270078,2669190.583504057 272433.27910509938,2669190.5346720945 272433.23512102355,2669061.6806792449 272315.63031884894,2669061.5622499352 272315.51864117954,2668863.199813955 272122.26866321731,2668675.0644291034 271945.38048871764,2668675.012292074 271945.33075597486,2668621.8039101921 271893.83875994524)),((2667820.9199819015 270953.36301544425,2667877.4616753059 270894.2136172601,2667635.9867241122 270668.63822003675,2667473.0777259022 270511.76294403907,2667362.1654696316 270399.89460570336,2667351.0318503459 270386.53424639819,2667353.1057906118 270369.25130332157,2667392.7496305276 270194.23836177919,2667395.9369028728 270176.48686356761,2667397.0768031054 270167.93769603857,2667415.6516704997 270142.56719073287,2667424.7677217149 270128.98345668329,2667443.7916398924 270097.9655711946,2667460.9152091327 270062.69574068469,2667470.8289512005 270024.762967441,2667473.1518865474 269985 .6249831,2667472.2402227214 269979.01544618892,2667256.0940110106 270163.54399970663,2667188.550996427 270221.29698959459,2667193.956992148 270197.8109957719,2667199.9469964928 270171.37498487829,2667197.4917207863 270173.56755541946,2667160.6962249437 270336.00610770396,2667154.6189217232 270386.65061629307,2667153.6210496165 270424.57026852213,2667159.480942999 270447.03316277458,2667172.3362285104 270476.69919561408,2667217.7565692873 270531.20367048145,2667336.1911747726 270650.65920193074,2667501.7915902673 270810.12621217291,2667742.68823009 271035.16137606534,2667746.4119876497 271031.17597637954,2667762.7910122895 271013.92398454424,2667820.9199819015 270953.36301544425)),((2668471.402630189 271748.28909579659,2668336.326873967 271888.93079307029,2668479.6639016406 272027.64408219588,2668614.8836596967 271887.14174157265,2668471.402630189 271748.28909579659)),((2667359.7395684123 269814.11183598818,2667282.6020077355 269888.61299626593,2667303.5420043604 269910.6 3901687448,2667383.91728911 269827.49620502215,2667377.8672984857 269822.91288313258,2667359.7395684123 269814.11183598818)),((2667019.9392894655 270027.29829661967,2667034.2579968879 270013.355981313,2667225.6779910154 269826.80501405016,2667259.2924584779 269794.41253668105,2667226.6875763042 269798.90977695456,2667189.6398480511 269811.74112135114,2667155.8072526185 269831.55356829794,2667126.4899576749 269857.58573656977,2667102.8146104235 269888.83722453896,2667088.07071314 269912.87667389616,2667061.3971756008 269949.30875770538,2667061.3971756008 269949.30875770526,2667045.1710985317 269975.48515655525,2667026.2287774868 270012.06309929845,2667026.2287774868 270012.06309929834,2667019.9392894655 270027.29829661967))) When I call triangle.intersection(big_multipolygon) I get a TopologyException: "no outgoing dirEdge found [ (523.939289465547, 7883.29829661967, NaN) ]" I'm using NTS, I was wondering if someone could check if this is still a problem in the latest JTS? Also, any suggestions for what I can do to my data to try and prevent this? -- Jeff Adams Avencia, Inc. 215-701-7717 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] STRtree index persistence
Do you just need to serialize the tree (and all its contents), or do you need to maintain and access the tree on disk? I think these two things require very different designs. Serializing should be easy - just make everything Serializable. (And let me know if it works and what the patch is). Although then I have to ask - why not just rebuild the tree as you read in the underlying data? Does it really take that long? Hmm... and the STRtree has two phases of construction, the build phase and the indexed phase. You'll have to think about whether you persist both phases, or whether you force an index build before serializing. Martin Tomko wrote: Hi All, I am using JTS through Geotools. I am trying to create a spatial index on my shapefile polygon data, unhomogenously distributed over space (read only) for a point in polygon type of queries, and I have two options - either use a qix (that's a quadree, right?) or use final SpatialIndex index = new STRtree(); using the JTS functionalities. I like the second option, but am wondering how I could save the results of the indexing for future use. In other words, I need to introduce persistence. Alternatively, I guess I could just generate a qix index and use that, but I wanted to try the STRtree, as I think it is better suited for my data. Cheers Martin ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Intersection results, are they in order?
It occurs to me that an even more efficient way of doing this
computation is simply to scan the line segments of the polygons and
compute their intersection (if any) with the line. This requires a bit
more low-level coding, but should be faster than either of the
approaches discussed so far.
Martin Davis wrote:
Sure, buffer(0) should work (that was the recommended way to do unary
union in JTS prior to the introduction of the union() method).
Just be aware that buffer is not 100% robust, and can produce some
peculiar results in some situations. However, these are fairly rare.
If you do encounter robustness exceptions, you can alway drop back to
the slower method for that particular case.
Jeff Adams wrote:
Unfortunately I'm actually using NTS, which is I think on level with
JTS 1.8... so no unary Union method.
What about using buffer(0.0) instead of union? Will that eliminate
the internal linework?
I realize it's a bit of a hack, but it is a handy one in lots of
other situations.
On Thu, Jul 30, 2009 at 3:11 PM, Martin Davis
mailto:mbda...@refractions.net>> wrote:
If you have a lot of overlapping polygons, it's probably faster to
union them all together. This will get rid of internal linework,
which should speed things up.
JTS 1.9 and above have a Geometry.union() (unary union) method,
which uses a fast algorithm to merge geometries. So you can just
call multipoly.union() to get the union.
Note that a MultiPolygon with overlapping components is actually
an invalid geometry. JTS will let you build this, tho, and will
let you run unary union() on it (for just this kind of situation).
But you can't run binary overlay operations successfully on an
invalid geometry.
To answer your last question, the boundary of a MultiPolygon is
just a collection of the boudaries of the components. So
boundary() by itself won't reduce the amount of linework you are
processing.
Jeff Adams wrote:
Thanks, I'll try that.
What is the fastest way of boiling down the polygon outlines?
I do not need to know the one that intersected, and in fact I
don't even need them to remain distinct (many of the polygons
are touching or even overlapping). I could union them into a
non-overlapping multipolygon and use that boundary, which
would give me the fewest intersecting points to test. I was
making a multipolygon with them already (but not unioning
them), is the fastest thing to do
multipoly.union(multipoly.getSomePoint()).getBoundary()? Or
will the boundary of a multipolygon already go around
overlapping/touching polygons inside it?
I am calculating distance from a point to the polygon group
repeatedly (probably 50 -100 times on average) for each
polygon group so it is probably worth it do as much prep as
possible before I start figuring distances.
On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis
mailto:mbda...@refractions.net>
<mailto:mbda...@refractions.net
<mailto:mbda...@refractions.net>>> wrote:
How about this?
Intersect the line with the *boundaries* of the polygons.
Then
take the resulting point set and compute the distance
between each
point and your start point. The smallest distance is the
one you
want.
That will have the nice side effect of being faster, too.
If you need to know the actual polygon which is closest,
iterate
over the polygons individually, and keep track of the one
with the
closest intersection point.
Jeff Adams wrote:
Perhaps it would be helpful if I said WHY I was doing
this
;-). Often you guys suggest much better alternatives
to what
I'm trying anyway.
I have a starting point and a direction. I want to
find the
nearest point on any of the polygons along that
direction.
What I'm trying to do in my previous email is make a
linestring that goes in the direction I want, using my
starting point and a point I generate an arbitrary
distance
out, then take the intersection results and use the first
(hopefully nearest) point.
Is there a "first intersection along line" method that I
overlooked? Or a cleaner way of doing this?
Thanks,
Jeff
On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams
mailto:jad...@avencia.com>
<mailto:jad...@avencia.com <mailto:jad...@avencia.com>>
<mailto:jad...@avencia.com <mailto:jad...@avencia.com>
Re: [jts-devel] Intersection results, are they in order?
Sure, buffer(0) should work (that was the recommended way to do unary
union in JTS prior to the introduction of the union() method).
Just be aware that buffer is not 100% robust, and can produce some
peculiar results in some situations. However, these are fairly rare.
If you do encounter robustness exceptions, you can alway drop back to
the slower method for that particular case.
Jeff Adams wrote:
Unfortunately I'm actually using NTS, which is I think on level with
JTS 1.8... so no unary Union method.
What about using buffer(0.0) instead of union? Will that eliminate
the internal linework?
I realize it's a bit of a hack, but it is a handy one in lots of other
situations.
On Thu, Jul 30, 2009 at 3:11 PM, Martin Davis <mailto:mbda...@refractions.net>> wrote:
If you have a lot of overlapping polygons, it's probably faster to
union them all together. This will get rid of internal linework,
which should speed things up.
JTS 1.9 and above have a Geometry.union() (unary union) method,
which uses a fast algorithm to merge geometries. So you can just
call multipoly.union() to get the union.
Note that a MultiPolygon with overlapping components is actually
an invalid geometry. JTS will let you build this, tho, and will
let you run unary union() on it (for just this kind of situation).
But you can't run binary overlay operations successfully on an
invalid geometry.
To answer your last question, the boundary of a MultiPolygon is
just a collection of the boudaries of the components. So
boundary() by itself won't reduce the amount of linework you are
processing.
Jeff Adams wrote:
Thanks, I'll try that.
What is the fastest way of boiling down the polygon outlines?
I do not need to know the one that intersected, and in fact I
don't even need them to remain distinct (many of the polygons
are touching or even overlapping). I could union them into a
non-overlapping multipolygon and use that boundary, which
would give me the fewest intersecting points to test. I was
making a multipolygon with them already (but not unioning
them), is the fastest thing to do
multipoly.union(multipoly.getSomePoint()).getBoundary()? Or
will the boundary of a multipolygon already go around
overlapping/touching polygons inside it?
I am calculating distance from a point to the polygon group
repeatedly (probably 50 -100 times on average) for each
polygon group so it is probably worth it do as much prep as
possible before I start figuring distances.
On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis
mailto:mbda...@refractions.net>
<mailto:mbda...@refractions.net
<mailto:mbda...@refractions.net>>> wrote:
How about this?
Intersect the line with the *boundaries* of the polygons. Then
take the resulting point set and compute the distance
between each
point and your start point. The smallest distance is the
one you
want.
That will have the nice side effect of being faster, too.
If you need to know the actual polygon which is closest,
iterate
over the polygons individually, and keep track of the one
with the
closest intersection point.
Jeff Adams wrote:
Perhaps it would be helpful if I said WHY I was doing this
;-). Often you guys suggest much better alternatives
to what
I'm trying anyway.
I have a starting point and a direction. I want to
find the
nearest point on any of the polygons along that direction.
What I'm trying to do in my previous email is make a
linestring that goes in the direction I want, using my
starting point and a point I generate an arbitrary distance
out, then take the intersection results and use the first
(hopefully nearest) point.
Is there a "first intersection along line" method that I
overlooked? Or a cleaner way of doing this?
Thanks,
Jeff
On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams
mailto:jad...@avencia.com>
<mailto:jad...@avencia.com <mailto:jad...@avencia.com>>
<mailto:jad...@avencia.com <mailto:jad...@avencia.com>
<mailto:jad...@avencia.com <mailto:jad...@avencia.com>>>> wrote:
If I have a linestring, and I do an intersection
with a large
random collection of polygons such that the result
Re: [jts-devel] Intersection results, are they in order?
If you have a lot of overlapping polygons, it's probably faster to union them all together. This will get rid of internal linework, which should speed things up. JTS 1.9 and above have a Geometry.union() (unary union) method, which uses a fast algorithm to merge geometries. So you can just call multipoly.union() to get the union. Note that a MultiPolygon with overlapping components is actually an invalid geometry. JTS will let you build this, tho, and will let you run unary union() on it (for just this kind of situation). But you can't run binary overlay operations successfully on an invalid geometry. To answer your last question, the boundary of a MultiPolygon is just a collection of the boudaries of the components. So boundary() by itself won't reduce the amount of linework you are processing. Jeff Adams wrote: Thanks, I'll try that. What is the fastest way of boiling down the polygon outlines? I do not need to know the one that intersected, and in fact I don't even need them to remain distinct (many of the polygons are touching or even overlapping). I could union them into a non-overlapping multipolygon and use that boundary, which would give me the fewest intersecting points to test. I was making a multipolygon with them already (but not unioning them), is the fastest thing to do multipoly.union(multipoly.getSomePoint()).getBoundary()? Or will the boundary of a multipolygon already go around overlapping/touching polygons inside it? I am calculating distance from a point to the polygon group repeatedly (probably 50 -100 times on average) for each polygon group so it is probably worth it do as much prep as possible before I start figuring distances. On Thu, Jul 30, 2009 at 2:27 PM, Martin Davis <mailto:mbda...@refractions.net>> wrote: How about this? Intersect the line with the *boundaries* of the polygons. Then take the resulting point set and compute the distance between each point and your start point. The smallest distance is the one you want. That will have the nice side effect of being faster, too. If you need to know the actual polygon which is closest, iterate over the polygons individually, and keep track of the one with the closest intersection point. Jeff Adams wrote: Perhaps it would be helpful if I said WHY I was doing this ;-). Often you guys suggest much better alternatives to what I'm trying anyway. I have a starting point and a direction. I want to find the nearest point on any of the polygons along that direction. What I'm trying to do in my previous email is make a linestring that goes in the direction I want, using my starting point and a point I generate an arbitrary distance out, then take the intersection results and use the first (hopefully nearest) point. Is there a "first intersection along line" method that I overlooked? Or a cleaner way of doing this? Thanks, Jeff On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams mailto:jad...@avencia.com> <mailto:jad...@avencia.com <mailto:jad...@avencia.com>>> wrote: If I have a linestring, and I do an intersection with a large random collection of polygons such that the result will be a bunch of little linestrings in a row, I.E. original linestring: --- Intersection results: --- -- Will the MultiLineString or GeometryCollection (since I suppose some of the results could just be points where a polygon touches my linestring) result that I get back from the Intersection call be in order? Assuming the original was something like: LINESTRING(0 0, 100 0) Will the results be: MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0)) Or could they be in any order? Will the direction of the linestrings be the same as the original, or could I get one that was (75 0, 70 0)? ___ jts-devel mailing list jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> http://lists.ref
Re: [jts-devel] Intersection results, are they in order?
How about this? Intersect the line with the *boundaries* of the polygons. Then take the resulting point set and compute the distance between each point and your start point. The smallest distance is the one you want. That will have the nice side effect of being faster, too. If you need to know the actual polygon which is closest, iterate over the polygons individually, and keep track of the one with the closest intersection point. Jeff Adams wrote: Perhaps it would be helpful if I said WHY I was doing this ;-). Often you guys suggest much better alternatives to what I'm trying anyway. I have a starting point and a direction. I want to find the nearest point on any of the polygons along that direction. What I'm trying to do in my previous email is make a linestring that goes in the direction I want, using my starting point and a point I generate an arbitrary distance out, then take the intersection results and use the first (hopefully nearest) point. Is there a "first intersection along line" method that I overlooked? Or a cleaner way of doing this? Thanks, Jeff On Thu, Jul 30, 2009 at 2:07 PM, Jeff Adams <mailto:jad...@avencia.com>> wrote: If I have a linestring, and I do an intersection with a large random collection of polygons such that the result will be a bunch of little linestrings in a row, I.E. original linestring: --- Intersection results: --- -- Will the MultiLineString or GeometryCollection (since I suppose some of the results could just be points where a polygon touches my linestring) result that I get back from the Intersection call be in order? Assuming the original was something like: LINESTRING(0 0, 100 0) Will the results be: MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0)) Or could they be in any order? Will the direction of the linestrings be the same as the original, or could I get one that was (75 0, 70 0)? ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Intersection results, are they in order?
Afraid the answer is no and no. Linestrings returned from an intersection may be in any order and any orientation, relative to the input. I can see that it might be useful to have the intersection operation preserve input order and orientation for LineStrings. Currently this information isn't maintained, in order to make the algorithm simpler and improve efficiency. At the moment I can't think of a simple way of doing this, but perhaps it's not that difficult with the right internal structures. Jeff Adams wrote: If I have a linestring, and I do an intersection with a large random collection of polygons such that the result will be a bunch of little linestrings in a row, I.E. original linestring: --- Intersection results: --- -- Will the MultiLineString or GeometryCollection (since I suppose some of the results could just be points where a polygon touches my linestring) result that I get back from the Intersection call be in order? Assuming the original was something like: LINESTRING(0 0, 100 0) Will the results be: MULTILINESTRING((5 0, 15 0), (35 0, 60 0), (70 0, 75 0)) Or could they be in any order? Will the direction of the linestrings be the same as the original, or could I get one that was (75 0, 70 0)? ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Efficient searching - point in list of polygons
Merging into one index *might* produce better performance - you'd have to try it and see. Using userData to store ancillary data (like cost) is a reasonable approach. Alternatively, the objects that are entered into the spatial index don't have to be Geometries - they can be any Object as long as it can provide an Envelope for its extent. So you could store custom Feature objects which contain a Geometry and some ancillary data. I"m a bit surprised that PreparedGeometry isn't making any performance difference - but it's possible that the difference is not enough to be worth bothering about. If only a few points are being compared against any individual polygon, the overhead of building the PreparedGeometry would swamp any gain from caching. Another option - don't use Geometry.intersects() for your predicate, but use SimplePointInAreaLocator. Or, you could use IndexedPointInAreaLocator, but this would only be worth doing if you cached the index object (saving it either in the custom object you are storing in the spatial index, or in an external map) Dorrington, Albert wrote: I needed to upgrade our jts.jar from the 1.8 version to 1.10. I tried using the PreparedGeometry/PreparePolygon classes to see if there was any noticable change in performance, but the numbers looked about the same for each run. The problem I think I'm starting to run into tho, is I am not encountering more overhead from the profiling tool, than I am gaining from the code optimizations, so I'm no longer getting completely accurate timing results. For instance it takes about 45 seconds for the routine to run while being profiles, and about 2 seconds to run normally. I think we may need to alter our design approach in order to gain some more performance. From what I've been reading about the Geometry class, I'm thinking instead of maintaining four different layers, that we could use the Geometry's setUserData() method to store our 'cost' values for the layer and merge all polygon's as geometry objects, into one index. Maybe the prepared geometry approach would work better with that? Not sure, very new to JTS at this point :) -Original Message- As you have now experienced, the biggest speedup you will find comes from using spatial indexes. You may also find that using PreparedGeometry helps to reduce the time even further, since it avoids recomputing topology for the input polygons. To do this, store a PreparedGeometry in the spatial index, rather than the original Polygons. Please let the list know how this works out if you try it - this is potentially of interest to lots of people. Martin ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Efficient searching - point in list of polygons
As you have now experienced, the biggest speedup you will find comes
from using spatial indexes.
You may also find that using PreparedGeometry helps to reduce the time
even further, since it avoids recomputing topology for the input
polygons. To do this, store a PreparedGeometry in the spatial index,
rather than the original Polygons.
Please let the list know how this works out if you try it - this is
potentially of interest to lots of people.
Martin
Dorrington, Albert wrote:
Hello everyone,
I am involved with a project that is using the JTS package (currently
1.8) to implement some path finding algorithms.
As currently implemented, we have several layers, each of which
contains a List of Polygon objects. Our search algorithm
looks to see if our current location (a Point object) intersects with
any of the Polygons defined in each layer/list, if it does, a cost
associated with that intersection is returned.
Initially our code was rather inefficient, considering that once the
list of polygons is defined, it does not change for the duration
of our search.
For example most layers are implemented like this:
protected double calculateCost(Point point) {
ret = costValue;
for (Polygon polygon : polygons ) {
if (point.intersects(polygon)) {
ret = 0;
break;
}
}
return ret;
}
I refined this, trying to merge all of the polygons once, into a
Geometry class, so that we could query the intersections against the
geomerty collection, instead.
protected double calculateCost(Point point) {
if ( ! loaded ) {
loaded = true;
geom = new Geometry[ polygons.size()];
polygons.toArray(geom);
geoFact = geom[0].getFactory();
geomColl = geoFact.createGeometryCollection(geom);
union = geomColl.buffer(0);
buffColl = union.buffer(1);
}
if ( buffColl.intersects(point) ) { return 0; }
else { return costValue; }
}
These 'calculateCost' methods are being called hundreds of thousands,
if not millions of times in our application, so any refinement we can
get would be worthwhile.
The biggest problem I have had, is not being able to locate sources of
docmentation (other than the Javadoc) and examples. So I'm really not
sure what else is available within the API, although I've been reading
that the PreparedGeometry classes in 1.9/1.10 of JTS may help to
improve our performance (if I can understand how to use them) ;-)
If anyone can provide some suggestions/advice, I'd be greatful.
Thanks!
Al Dorrington
Embedded S/W Engineer Sr
Aerospace Simulation Software Development
Lockheed Martin, Systems Integration-Owego
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] How to find the outer points in a group?
The simplest way to construct a polygon enclosing a set of points is to comnpute the convex hull (Geometry.convexHull). If you need a non-convex shape there are various ways to do this (alpha shapes, concave hulls, etc) but JTS currently doesn't provide this. I've often thought it would be nice to be able to use number of points as a simplification criteria, as opposed to distance. I think this is a minor extension to the current algorithm - just have to find the time to do this. Also, I'd like to provide an "outer simplification" option, which will simplify a polygon in such a way that the original vertices are always contained within the simplified boundary. Some day... Jeff Adams wrote: I have a bunch of semi-random points, but they're all "nearby" each other. I'd like to somehow get the list of only the "outside" points (I.E. if you were going to draw a polygon that contained all the points, which points would be the vertices). Then, just to make it fun, I actually have a maximum number of points that I want (I.E. no more than 25 points). I am willing to lose a few points from within the polygon if it is necessary to keep the number of points in the outline below the max. For example, if I had 100 points in a pseudo circle, that would be the worst case scenario because there is no way to draw a polygon with less than the full 100 without "losing" (being outside the outline) points. But that's OK for my purposes because the points are going to tend to be in rectangular clouds so I won't lose very many in practice. My current idea is to somehow draw the outline as a polygon, but then just simplify with larger and larger simplify distances until the number of vertices is below my max, then use the list of vertices as my list of "outline" points. But how do I draw the outline polygon in the first place? -- Jeff Adams Avencia, Inc. 215-701-7717 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Noding polygons
Polygonizer is also a possible approach. As you note, it returns
polygons "filling in" holes, so it requires a bit more work than my
approach. Also, it's probably a bit less efficient than my approach,
since there is a cost to doing a full-scale polygonization. But working
tested code is valuable in its own right...
Sandro Zacchino wrote:
Thank you Martin.
I developed the method below. I've tested it and it seems to be quite
efficient. Now the input parameters are Polygons since Geometry does
not have methods to know if it contains holes or not. The check on
holes presence is made since Polygonizer returns both polygons with
holes and holes. I will inspect the GeometryEditor you suggested to
see if it is more efficient than Polygonizer.
Bye
Sandro Zacchino
/**
* This method splits edges of two (possibly) overlapping polygons
for each intersection found
* @param g1 Polygon
* @param g2 Polygon
*/
public static List noder(Polygon g1, Polygon g2){
GeometryFactory gf = g1.getFactory();
//A list of NodedSegmentStrings to compute intersections
List list = new ArrayList();
//A NodedSegmentString is added with userdata:
//+1 for the 1st polygon, if it does not contain holes
//-1 for the 1st polygon, if it contains holes
//+2 for the 2nd polygon, if it does not contain holes
//-2 for the 2nd polygon, if it contains holes
Integer g1Data = new Integer(1);
if (g1.getNumInteriorRing()>=1){
g1Data = new Integer(-1);
}
list.add(new NodedSegmentString(g1.getCoordinates(), g1Data));
Integer g2Data = new Integer(2);
if (g2.getNumInteriorRing()>=1){
g2Data = new Integer(-2);
}
list.add(new NodedSegmentString(g2.getCoordinates(), g2Data));
//Create a noder and computes the nodes
MCIndexNoder noder = new MCIndexNoder();
noder.setSegmentIntersector(new IntersectionAdder(new
RobustLineIntersector()));
noder.computeNodes(list);
//Rebuild original polygons with splitted edges
Collection nodedSegStrings = noder.getNodedSubstrings();
// Map: Key is NodedSegmentString.UserData, Value is a list of
polygons
// this map is used to store all the noded linestrings for a given
input polygon
// using the Data inside the NodedSegmentString
HashMap> polygons = new HashMapList>();
for (Iterator i = nodedSegStrings.iterator(); i.hasNext(); ){
NodedSegmentString segString = (NodedSegmentString)i.next();
Integer userData = (Integer)segString.getData();
LineString ls = gf.createLineString(segString.getCoordinates());
if (!polygons.containsKey(userData)){
polygons.put(userData, new ArrayList());
}
polygons.get(userData).add(ls);
}
// The polygonizer is used to build polygons from noded linestrings
// if the original polygon contains holes polygonizer returns two
// (or more) polygons one for polygon with holes and one for each
// hole. So i use the sign of the data stored in NodedegmentStrings,
// and here used as key for the map, to discard the "holes polygons"
// from the polygonizer result.
ArrayList result = new ArrayList();
for(Entry> e: polygons.entrySet()){
Polygonizer polygonizer = new Polygonizer();
polygonizer.add(e.getValue());
for(Polygon p: (Collection)polygonizer.getPolygons()){
if (e.getKey()<0){
if (p.getNumInteriorRing()>=1)
result.add(p);
}
else
result.add(p);
}
//result.addAll(polygonizer.getPolygons());
}
return result;
}
Martin Davis ha scritto:
Yes, MCIndexNoder is the most efficient way to determine the
intersections between geometries.
Generally you're heading in the right direction. Where you go from
there depends on exactly what you want your output to be. If I
understand your use case, you want to recreate the original
geometries, but with vertices inserted where the intersection points
occur. This is not something which is currently directly supported
by NodedSegmentString, but it's easy to add (either by extension or
by external code). A NodedSegmentString contains a list of the nodes
along the SegmentString, as SegmentNodes. Each SegmentNode records
its location and which segment it occurs in. So all that is required
is to build a new CoordinateSequence including the new nodes as
vertices in the appropriate places.
You can then reform your original geometry by replacing each
CoordinateSequence by the corresponding noded one. One trick is to
"tag" the NodedSegmentStrings you create by setting the data field to
be the original CoordinateSequence. Then you can create a map from
the orig CS to the noded sequence, and then use something like
GeometryEditor to replace the sequences.
Sandro Zacchino wrote:
Hi all,
I need an efficient algorithm to node all the edges of a set
Re: [jts-devel] Noding polygons
Yes, MCIndexNoder is the most efficient way to determine the
intersections between geometries.
Generally you're heading in the right direction. Where you go from
there depends on exactly what you want your output to be. If I
understand your use case, you want to recreate the original geometries,
but with vertices inserted where the intersection points occur. This is
not something which is currently directly supported by
NodedSegmentString, but it's easy to add (either by extension or by
external code). A NodedSegmentString contains a list of the nodes along
the SegmentString, as SegmentNodes. Each SegmentNode records its
location and which segment it occurs in. So all that is required is to
build a new CoordinateSequence including the new nodes as vertices in
the appropriate places.
You can then reform your original geometry by replacing each
CoordinateSequence by the corresponding noded one. One trick is to
"tag" the NodedSegmentStrings you create by setting the data field to be
the original CoordinateSequence. Then you can create a map from the
orig CS to the noded sequence, and then use something like
GeometryEditor to replace the sequences.
Sandro Zacchino wrote:
Hi all,
I need an efficient algorithm to node all the edges of a set of
overlapping geometries with the intersections found.
Currently i'm following this algorithm (for two geometries) but the
last step i need is how to rebuild the original geometry (including
its holes):
public static void noder(Geometry g1, Geometry g2){
//GeometryFactory gf = new GeometryFactory();
// add the linestrings to a list of NodedSegmentString;
List list = new ArrayList();
list.add(new NodedSegmentString(g1.getCoordinates(), null));
list.add(new NodedSegmentString(g2.getCoordinates(), null));
// create a noder and computes the nodes
MCIndexNoder noder = new MCIndexNoder();
noder.setSegmentIntersector(new IntersectionAdder(new
RobustLineIntersector()));
noder.computeNodes(list);
...
At this point which is the most efficient way to recreate the original
polygons (with holes) having their edges noded properly?
Is MCIndexNoder the best method to get all the intersections?
Thank you
Sandro Zacchino
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] IGNORE - Test msg
-- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Polygonizer not symetric?
Well, this was never a design constraint on the Polygonizer, so this is neither a feature nor a bug. It is a bit surprising, however - I think all the code in the Polygonizer is deterministic, so the output should be identical for identical input. If you want a consistent ordering you can always normalize the output geometries and then sort them. If you provide a test program exhibiting the behaviour I can try and see what might be causing this behaviour. Janusz Dalecki wrote: Hi, I am surprised that the Polygonizer does not return Polygons in the same order every time I make a call to getPolygons method, although I am passing the same MultiLineString to the function add() – is this a feature or bug. I am not sure whether this is correct forum for JTS questions. Regards, Janusz ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Minimum Area bounding box
On the MinimumDiameter class there is a method getMininumRectangle(). That should give you what you need. Martin triplederby100-pro...@yahoo.com wrote: I need to find a minimum area bounding box for a given polygon - which could be convex or concave. Is this something possible to find using JTS? I see that there is a MinimumDiameter class but I am not sure if/how it can be used for this purpose. Any pointers are highly appreciated. Jatin ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] PrecisionModel semantics
Anke, Yes, the PrecisionModel is integrated into some geometrical operations of JTS. As I said in an earlier post, the PM is used in all operations which compute a new geometry. The operations ensure that new geometry meets the PM which is supplied with the input geometries (or independently, in some cases). This is useful, since sometimes JTS is used to process geometry which comes from systems which have a more restricted PM than double-precision. By using an appropriate PM, JTS will compute new geometry which can be stored back into those systems with no problems of topology collapse. JTS currently does not support using a tolerance for the spatial predicates. This could be a useful extension - I'd certainly be interested in exploring this possibility, especially if there was a funded project to support it. Anke Trittenbach wrote: Is the PrecisionModell integrated in the geometrical operations of JTS? If this is the case, for what is the PrecisionModell used in these operations? For which use is the PrecisionModell in general exactly? Many have also suggested that I could work with a tolerance. Thereby the renewed queries could be answered with true whether an educated intersection lies on one of the lines. Why does JTS not use such a tolerance? -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] (no subject)
Anke, As others have pointed out, the reason you are seeing the apparent inconsistency in your example 2 is due to the finite precision of the floating point representation used by JTS. JTS uses Java doubles, which follow the IEEE 754 standard and provide about 16 decimal digits of precision. When JTS computes an intersection point, this is the maximum precision it can compute. (In fact, for some kinds of inputs the actual accuracy of the computed intersection point will be even less than that, due to the cascading of round-off error in the internal computations). So the point POINT (-20301.268838372802 24498.858366300974) is only a 16-digit approximation to the true intersection point. However, for spatial *predicates* (such as intersects) JTS can compute the test *exactly* (by virtue of a clever algorithms for computing exact signs of determinants of FP numbers). So this test can detect that the computed point does not lie precisely on either of the input line segments - and hence intersects returns false. One thing to be aware of is that the spatial predicates do not incorporate the geometry precision model in any way - they always compute the *exact* relationship between the precise data specified by the floating point numbers in the vertices of the input geometry. (This was a design decision made in JTS - it's not the only possible way to do it, but at the moment there is no other strategy available). The precision model is used only for determining the precision of geometry results computed by JTS operations (such as intersection). Hope that helps to clear this up. This is a common point of confusion - so I'm going to add your case to the JTS FAQ! Anke Trittenbach wrote: Hello all together, I have tried to understand as JTS handles with the inaccuracy from doubles. As already mentioned there still appear mistakes with my calculations, because some values differ around 0.0004, although they are same. To solve this problem I have carried out some tests with JTS and tried to comprehend. On this occasion, I found the following difference between two equal geometrical cases: 1. Fall: Linestring1: "LINESTRING(4 1, 4 7)"; Linestring2: "LINESTRING(1 4, 7 4)"; With the intersection „linestring1.intersection(linestring2)“ the point „POINT (4 4)“ came out as expected. The question „linestring1.intersects(linestring1.intersection(linestring2))” delivered true. 2.Fall: Linestring3: "LINESTRING(-27611.19260069567 25315.392403581718, -11080.415853237311 23468.8694690252)"; Linestring4: "LINESTRING(-21456.11615217394 29272.22726334569, -18818.226245664628 18368.948983107195)"; With the intersection „Linestring3.intersection(linestring4)“ the point „POINT (-20301.268838372802 24498.858366300974) „ came out. However the question „Linestring3.intersects(linestring3.intersection(linestring4))” returns false. In fact it should return true? Does one of you know an explanation of this? Maybe someone does know who about JTS I can contact or who knows a lot about it? Or should I announce this as a bug? With kind regards, Anke Trittenbach -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Alpha version of JTS 1.11 updated
I've done a bit more work on the Delaunay/Voronoi code in JTS 1.11, to increase performance and (dramatically!) reduce the memory requirements. An updated version is available here: http://tsusiatsoftware.net/jts/files/jts-1.11-alpha2.zip -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] RE: Associating Voronoi cells with external site data
Thanks for the feedback, Stefan. Of course, your original PIP solution will still work. Hashmaps are seductively easy... c'mon down! By the way, I have been doing some performance/volume tests of the Delaunay code. I can run 200K points in 25 sec, on a 3-yr old machine. So that seems pretty good, and will hopefully be able to handle a lot of use cases. Stefan Steiniger wrote: Hei Martin, > Can anyone comment on whether this seems like a good approach? Is > this done any differently or better in the current JUMP Voronoi code? should work. I use the current DT/Voronoi implementation by LP Chew as Black box to retrieve the geometries only - so assigning attributes from original points to Voronoi polygons was done by a point in polygon test. So.. your option seems to be then faster (although I never used a HashMap so far - so need to learn it). thanks stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Associating Voronoi cells with external site data
One thing I'm adding to the Voronoi API is to set the userData for each computed cell Polygon to be the Coordinate of the original site point. This should allow easily associating the polygons with external data that was associated with the sites. A HashMap or TreeMap on the original site coordinates would allow data to be looked up using the saved coordinate attached to each output Voronoi polygon. E.g., if the sites were JUMP Features, then the site feature attributes over to new Features for the polygons. This saves doing a bunch of Point-in-Polygon lookups to do the same thing. Can anyone comment on whether this seems like a good approach? Is this done any differently or better in the current JUMP Voronoi code? -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] voronoi / thiessen polygons
Stefan Steiniger wrote: Hei Martin, > It's almost done, actually - so if you have a definite use case for > it, that would be great. yep we have. I used it in my research (pattern recognition) but Nacho Uve was using it too for some hydrological calculations if I remember correctly, Ravi (for Geologist GIS training) and I think Hisaiji are using it as well (he just asked recently). I got several times responses by people that at least tested it. Great, those all sound like good use cases. > Do you have examples of input data that caused problems with the > existing code? It would be nice to be able to test my code against > them. As far as I recognized the reason for this problem are collinear points - i.e. points on a regular grid. I send an example where it doesn't work with the implementation I used offlist to you. This doesn't seem to be a problem for the JTS code - it runs your datasets fine. I agree that collinear points are a known issue for some Delaunay implementations. Probably the use of an incremental algorithm helps here. > Also, how does the current OJ code "close off" or bound the > constructed > Voronoi diagram? Do you give it a bounding box, or is there some > other way? Actually the approach the triangulation used was a bit different from what you probably did. Because it starts with an initial triangle and uses and point-insert approach (a Simplex Insert algorithm developerd and implemented by L Paul Chew). So I basically deliver the bounds for the initial triangle. Ok, so nothing out of the ordinary then. The JTS code requires an envelope of the input points, and builds the frame triangle automatically. It's easy to clip the Voronoi polygons as required when they are generated. There is a VoronoiDiagramBuilder that provides a simple interface for doing this, or it's easy to deal with the raw outputs as well. stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: jts-devel Digest, Vol 64, Issue 1
Works for me, and others as well it sounds like. If you continue to have problems let me know and we can look for another way to get it to you. lee brian wrote: Martin I can not download the JTS1.11 from the link. http://tsusiatsoftware.net/jts/files/jts-1.11-alpha2.zip Is it broken? brian *From:* "jts-devel-requ...@lists.jump-project.org" *To:* jts-devel@lists.jump-project.org *Sent:* Saturday, May 2, 2009 3:01:04 AM *Subject:* jts-devel Digest, Vol 64, Issue 1 Send jts-devel mailing list submissions to jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> To subscribe or unsubscribe via the World Wide Web, visit http://lists.refractions.net/mailman/listinfo/jts-devel or, via email, send a message with subject or body 'help' to jts-devel-requ...@lists.jump-project.org <mailto:jts-devel-requ...@lists.jump-project.org> You can reach the person managing the list at jts-devel-ow...@lists.jump-project.org <mailto:jts-devel-ow...@lists.jump-project.org> When replying, please edit your Subject line so it is more specific than "Re: Contents of jts-devel digest..." Today's Topics: 1. JTS 1.11 with Delaunay triangulation API now availablein beta (Martin Davis) 2. Question on use cases of JTS, trianguation API (Martin Tomko) -- Message: 1 Date: Thu, 30 Apr 2009 14:01:44 -0700 From: Martin Davis <mailto:mbda...@refractions.net>> Subject: [jts-devel] JTS 1.11 with Delaunay triangulation API now availablein beta To: JTS Topology Suite Development <mailto:jts-devel@lists.jump-project.org>> Cc: OpenJUMP Dev <mailto:jump-pilot-de...@lists.sourceforge.net>> Message-ID: <49fa11b8.9000...@refractions.net <mailto:49fa11b8.9000...@refractions.net>> Content-Type: text/plain; charset=ISO-8859-1; format=flowed For those interested, an alpha version of JTS 1.11 including the new Delaunay triangulation API is now available here: http://tsusiatsoftware.net/jts/files/jts-1.11-alpha2.zip Documentation is provided in the Javadoc, but as always source code provides the best guide to use. Check out the classes TriangulationFunctions DelaunayTriangulationBuilder ConformingDelaunayTriangulationBuilder for examples of how to use the API. Also, the JTSTestBuilder is a great way to experiment with the capabilities of the code. Thanks to all who responded with requirements and use cases. I intend to summarize them soon, with notes on whether and how the JTS API supports them. Feedback from users is welcome (preferably on the JTS list). Martin -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 -- Message: 2 Date: Fri, 01 May 2009 11:33:15 +0200 From: Martin Tomko <mailto:martin.to...@geo.uzh.ch>> Subject: [jts-devel] Question on use cases of JTS, trianguation API To: jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> Message-ID: <49fac1db.6000...@geo.uzh.ch <mailto:49fac1db.6000...@geo.uzh.ch>> Content-Type: text/plain; charset=ISO-8859-1; format=flowed From my side, I would love to be able to get the inverse - voronoi polygons. While this is relatively simple, what I am desperately looking for would be a java implementation of the CGAL algorithm for segment voronois (I really don't speak C :( ): http://www.cgal.org/Manual/3.1/doc_html/cgal_manual/Segment_Voronoi_diagram_2/Chapter_main.html Thanks, Martin -- ___ jts-devel mailing list jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> http://lists.refractions.net/mailman/listinfo/jts-devel End of jts-devel Digest, Vol 64, Issue 1 _______ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Question on use cases of JTS, trianguation, API
It's almost done, actually - so if you have a definite use case for it, that would be great. Do you have examples of input data that caused problems with the existing code? It would be nice to be able to test my code against them. Also, how does the current OJ code "close off" or bound the constructed Voronoi diagram? Do you give it a bounding box, or is there some other way? M Stefan Steiniger wrote: Hei Martin, > Voronoi polygons are in the works - hopefully to be finalized this week. oh wow! that would be great to have - so I can replace the Thiessen polygon stuff in OpenJUMP (which had some flaws for certain point configurations). However if it needs more time, thats fine too :) stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Question on use cases of JTS trianguation API
Michael, The triangulation code uses a Quad-Edge Subdivision as its underlying structure. This is a topological structure which directly supports the kind of navigation that you require. It's a wee bit tricky to understand, however. Alternatively, you could load the generated edges into a PlanarGraph and traverse them that way. That might have an easier API to use. If you end up doing this, consider contributing the code back into JTS - it might be generally useful. Martin Michael Bedward wrote: 2009/4/30 Martin Davis : INPUT: - Geometry (from which the site/vertex coordinates are extracted) - Collection of Coordinates OUTPUT: - MultiLineString containing triangulation edges - GeometryCollection of Polygons containing triangles One of my common needs is to navigate between neighbouring points, akin to a (highly) constrained random walk. To do this with the above outputs I guess I would build data structure(s) that related input coords to output triangles, allowing forward and reverse lookup. If such a thing is generally useful it would be nice to have it as an output, possibly optional. Unless, of course, there is already an easier and more elegant way of accomplishing this. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Question on use cases of JTS, trianguation API
Voronoi polygons are in the works - hopefully to be finalized this week. Unfortunately for you, these will be based on a point Voronoi diagram, not a line Voronoi (which I assume is the equivalent of the CGAL "segment Voronoi"?). Line Voronois are a much trickier beast to handle. Without a good chunk of funding and time I don't see them appearing in JTS any time soon. Martin Tomko wrote: From my side, I would love to be able to get the inverse - voronoi polygons. While this is relatively simple, what I am desperately looking for would be a java implementation of the CGAL algorithm for segment voronois (I really don't speak C :( ): http://www.cgal.org/Manual/3.1/doc_html/cgal_manual/Segment_Voronoi_diagram_2/Chapter_main.html Thanks, Martin ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Adding a z coordinate
Yes, you need to rebuild the geometry using a 3D PackedCoordinateSequence. The easiest way to do this is to make a new GeometryFactory based on a 3D PCS, and then use the GeometryFactory.createGeometry method on the original geometry. This will return a new geometry using the new PCS. You can then update the Z ordinate as required. Fernando González wrote: Hi all, I'm trying to add a z coordinate to a 2D geometry and I'm using a CoordinateSequenceFilter without a total success. It doesn't work when the geometry has been built using a PackedCoordinateSequence and I get an ArrayIndexOutOfBoundsException when I set the z ordinate. I understand that PackedCS for 2d geometries doesn't have enough space to store 3d geometries. This issue is related with another one I had some time ago[1]. The solution has worked fine until I've tried to add 3d ordinates to a 2D PackedCoordinateSequence. Is there a general method to transform a 2d geometry into a 3d geometry? Mayeb is it possible to change the coordinate sequences a geometry uses? Maybe kind of clonning? I'm thinking of analyzing recursively the Geometry and producing another one with the 3d coordinates. Has anyone done this before? Thanks in advance. [1]http://lists.refractions.net/pipermail/jts-devel/2008-June/002539.html ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] triangulation area
I think you'll have to do the latter - triangulate, and then clip/discard edges which are outside your polygons. If I understand your use case, I think that should work - but if it doesn't, post some more details and we can try and think of a different approach. Tore Halset wrote: Hello. I have some points that I want to do triangulation with. In addition, I have some polygons defining the valid area for triangulation. So the triangulation should not create lines outside of the valid area. Is that possible with jts? Or should I just do triangulation and then only use those lines that are inside the valid areas? Regards, - Tore. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] JTS 1.11 with Delaunay triangulation API now available in beta
For those interested, an alpha version of JTS 1.11 including the new Delaunay triangulation API is now available here: http://tsusiatsoftware.net/jts/files/jts-1.11-alpha2.zip Documentation is provided in the Javadoc, but as always source code provides the best guide to use. Check out the classes TriangulationFunctions DelaunayTriangulationBuilder ConformingDelaunayTriangulationBuilder for examples of how to use the API. Also, the JTSTestBuilder is a great way to experiment with the capabilities of the code. Thanks to all who responded with requirements and use cases. I intend to summarize them soon, with notes on whether and how the JTS API supports them. Feedback from users is welcome (preferably on the JTS list). Martin -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Question on use cases of JTS trianguation API
To those that are interested in the upcoming JTS triangulation API, a question: What type of input and output structures would you find useful? Currently I'm developing the following: INPUT: - Geometry (from which the site/vertex coordinates are extracted) - Collection of Coordinates OUTPUT: - MultiLineString containing triangulation edges - GeometryCollection of Polygons containing triangles You can also work directly with the internal datastructures of the triangulation (Vertices, QuadEdges, etc), but this requires a higher level of understanding. Is there any other option I haven't though of? -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Delaunay triangulation code in JTS 1.11
Ok, I'll make a beta version available shortly, and post the location to the list. Johnathan Kool wrote: Hi Martin - I'd be interested in taking a look at the API. I've been doing a lot of work with triangulations lately (been using a modified version of the code from VisAd), and have a number of features I've been working with. Thanks, Johnathan -Original Message- From: jts-devel-boun...@lists.jump-project.org [mailto:jts-devel-boun...@lists.jump-project.org] On Behalf Of Martin Davis Sent: Wednesday, April 29, 2009 1:59 AM To: OpenJUMP Dev; jts Topology Suite Development Subject: [jts-devel] Delaunay triangulation code in JTS 1.11 Some might be interested to know that the JTS 1.11 will contain code for building Delaunay triangulations. The code is quite robust and is very fast. It might be interesting to compare this to the code in the OpenJUMP JTin API and see if there's any advantage to using one or the other. I also would like to get feedback about the JTS triangulation API (ie to see if there are enhancements which would be useful). If anyone is interested in a pre-release version I can provide that on request. -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Delaunay triangulation code in JTS 1.11
Some might be interested to know that the JTS 1.11 will contain code for building Delaunay triangulations. The code is quite robust and is very fast. It might be interesting to compare this to the code in the OpenJUMP JTin API and see if there's any advantage to using one or the other. I also would like to get feedback about the JTS triangulation API (ie to see if there are enhancements which would be useful). If anyone is interested in a pre-release version I can provide that on request. -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Acme.JPM.Encoders ...
Thanks, fixed in CVS. strk wrote: On Mon, Apr 20, 2009 at 09:00:48AM -0700, Martin Davis wrote: Sounds like you need to add the acme.jar to your classpath. It's distributed with JTS. Yup, that was it, thanks. Attached is a patch for build.xml, where Acme.jar was added to the classpath, while 'acme.jar' is the name of the file in repository. --strk; strk wrote: Hello, I'm trying to build JTS on an Ubuntu 8.10 GNU/Linux system, failing on use of the Acme stuff: jts-test-jar: [delete] Deleting directory /home/src/jts/jts/build/classes [mkdir] Created dir: /home/src/jts/jts/build/classes [javac] Compiling 175 source files to /home/src/jts/jts/build/classes [javac] /home/src/jts/jts/src/com/vividsolutions/jtstest/testbuilder/model/HtmlWriter.java:54: package Acme.JPM.Encoders does not exist [javac] import Acme.JPM.Encoders.GifEncoder; [javac] ^ Is that a strict requirement ? How can I install it ? TIA --strk; Free GIS & Flash consultant/developer () ASCII Ribbon Campaign http://foo.keybit.net/~strk/services.html /\ Keep it simple! ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Acme.JPM.Encoders ...
Sounds like you need to add the acme.jar to your classpath. It's distributed with JTS. strk wrote: Hello, I'm trying to build JTS on an Ubuntu 8.10 GNU/Linux system, failing on use of the Acme stuff: jts-test-jar: [delete] Deleting directory /home/src/jts/jts/build/classes [mkdir] Created dir: /home/src/jts/jts/build/classes [javac] Compiling 175 source files to /home/src/jts/jts/build/classes [javac] /home/src/jts/jts/src/com/vividsolutions/jtstest/testbuilder/model/HtmlWriter.java:54: package Acme.JPM.Encoders does not exist [javac] import Acme.JPM.Encoders.GifEncoder; [javac] ^ Is that a strict requirement ? How can I install it ? TIA --strk; Free GIS & Flash consultant/developer () ASCII Ribbon Campaign http://foo.keybit.net/~strk/services.html /\ Keep it simple! ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: concave hull ref
Believe me, even given the dependence on Delaunay Triangulation this algorithm is simple compared to most that appear in papers! There's lots of public code for DT out there (as always, the trick is finding high quality, robust, performant code! ) I do have DT code which I'm hoping to roll into JTS in a month or two. Stay tuned... Thanks for the offer about papers - sometimes it's very hard to get your hands on academic papers, so that could be very useful. M Stefan Steiniger wrote: Martin, I love your comment: >> How refreshing to have a paper which >> contains an algorithm which is actually easy to implement! as I am not sure if this one would give me a head-ache or not (i - pseudo code looks nice..but still, ii - do you have a delauney triangulation already implemented in JTS? - I didn't know that) I am glad that there are people out there like you that are a) into programming and b) still understand all that computational geometry stuff - I wished I would be a 'math' person sometimes. stefan PS: if somebody needs the original/final version from a paper mentioned - ask me. We have pretty good access to all the major journals/publishers here at UofC. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: concave hull ref
Now that I've had a chance to browse the Duckham paper, it looks like it is proposing exactly the idea of a "weeded Delaunay triangulation". Lucky them - first into a journal with this radical new concept! I think I saw this mentioned on the FME wiki a while ago - I wonder if they are aware of this? They do lots of investigation into the properties of the shape, however. How refreshing to have a paper which contains an algorithm which is actually easy to implement! Martin Davis wrote: Also interesting... It looks to me like the LoCoH approach is not raster based, it's vector. Basic idea seems to be unioning convex hulls of the k nearest neighbours of each data point. So k is a parameter - not sure if they have some way of choosing the best value of k. Shapes vary quite a bit as k gets bigger, of course. They also call this the k-NNCH algorithm - not sure how Moreria et al can claim prior art since this seems similar to what they are talking about. Lots of different ways to skin this one, obviously, depending on what your goal is. Pretty amusing to see the same basic problem tackled in so many different ways and domains. I still like the idea of a "weeded Delaunay triangulation" - it has a nice computational-geometric basis, and should be pretty efficient to compute. I might try and give this a go when I have some time. Stefan Steiniger wrote: ... Actually what I should add - I would need a concave hull implementation too for my research but didn't found the time yet to work on such thing (and doubt I will find it any time soon). We should have made this a Google Summer of Code project. However - I recently saw a presentation by a student of our department who calculated "hulls" that are supposed to be animal habitats from GPS tracks. She used Convex hull, kernel density (raster based), and a further method - minimum convex hulls (LoCoH). Informations on the latter method by Getz and Wilmers (2004) and Getz et al (2007) can be found here: http://locoh.cnr.berkeley.edu/ and http://locoh.cnr.berkeley.edu/images/article.pdf I haven't read the article yet - so it may be a raster based approach. I have seen that derived polygons may contain holes. The info says it is available for ArcGIS and R (which may indicate that for R the source code is availble???). On the webpage you can even upload you shp files. maybe that is f interest too - or gives some more ideas for concave hulls. stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: concave hull ref
Also interesting... It looks to me like the LoCoH approach is not raster based, it's vector. Basic idea seems to be unioning convex hulls of the k nearest neighbours of each data point. So k is a parameter - not sure if they have some way of choosing the best value of k. Shapes vary quite a bit as k gets bigger, of course. They also call this the k-NNCH algorithm - not sure how Moreria et al can claim prior art since this seems similar to what they are talking about. Lots of different ways to skin this one, obviously, depending on what your goal is. Pretty amusing to see the same basic problem tackled in so many different ways and domains. I still like the idea of a "weeded Delaunay triangulation" - it has a nice computational-geometric basis, and should be pretty efficient to compute. I might try and give this a go when I have some time. Stefan Steiniger wrote: ... Actually what I should add - I would need a concave hull implementation too for my research but didn't found the time yet to work on such thing (and doubt I will find it any time soon). We should have made this a Google Summer of Code project. However - I recently saw a presentation by a student of our department who calculated "hulls" that are supposed to be animal habitats from GPS tracks. She used Convex hull, kernel density (raster based), and a further method - minimum convex hulls (LoCoH). Informations on the latter method by Getz and Wilmers (2004) and Getz et al (2007) can be found here: http://locoh.cnr.berkeley.edu/ and http://locoh.cnr.berkeley.edu/images/article.pdf I haven't read the article yet - so it may be a raster based approach. I have seen that derived polygons may contain holes. The info says it is available for ArcGIS and R (which may indicate that for R the source code is availble???). On the webpage you can even upload you shp files. maybe that is f interest too - or gives some more ideas for concave hulls. stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] basic questions
#1: as others have replied, JTS operates purely on a Cartesian plane. It does not perform calculations in a spherical or spheroidal space. #2: as mentioned by others, easiest way is to modify the underlying Coordinate of a Point geometry. If you do this, you need to call geiometryChanged() to update the cached information in the Geometry (the Envelope at the moment). Be aware that of course any references to this geometry will not be aware of this change, so you will have to update them as required (e.g. JTS indexes are not aware of changes to contained geometries). Generally it's not encouraged to modify Geometry objects, since this can lead to nasty aliasing bugs, but it's not prevented for just this reason - in some cases it's more efficient to modify geometry objects in place. roberto.cal...@gmail.com wrote: I'm a beginner and have two questions I couldn't find the answer in documentation: - Is it possible to define a projection system for my calculations? Example, I want to calculate the distance in km between two points that has coordinates in latitude/longitude degrees in a given projection system for Earth. - I made a class that represents a moving object, so I used Coordinate implement its location (that changes all the time). I wanted to use Point, but Coordinate is the best class for dynamic info. So I'm instantiating a new Geometry everytime I need to perform calculation using this objects, is that right? Thank you. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] polygonizer and line strings
Two possibilities: 1. bug in Polygonizer 2. your input is not fully noded. I would suspect #2. Can you post sample data? (to the list or to me directly). I'd like to see the concave hull paper you mention as well - I'm quite interested in an implementation of this. Although as pointed out there is no single interpretation of how concave hull should be defined - so there could be several ways to compute something reasonable) As for a user guide to JTS, I realize this would be very nice to have. I'd very much like to provide something for this. Unfortunately it's quite time-consuming to create, and it's been hard for me to find the time to put to it. For the time being I try and keep enhancing the Javadoc whenever it looks like it could be improved. Martin Dragan Blagojevic wrote: Hi, I have question regarding proper use of Polygonizer class (I'm using NTS, but it shouldn't matter I hope) I'm working on utility to create convex hull of a point set. Result of first step of that utility is whole bunch of line strings representing convex hull or point set. Then I'm using Polygonizer to transform list of line strings to polygon. Problem is that sometime result of polygonizer is not one 'Big' outlining polygon (having potentially some holes in it), but instead lot of small polygons. I suspect that problem is when some line segments lie on the boundary and as well form smaller hole in polygon that somehow create probelm. It's a bit difficult to describe, but I'll try to simplify it as much as possible. Imagine chess board (8x8 square) having line segments of lenght 1 all arround. If it happens that there are line segments arroung some of little squares arround the edges (e.g. field C1) then instead or returning big polygon (8x8) polygonizer return only small one (1x1 C1 square). My guess is that line segment on the edge get assigned to that small polygon, and then rest of the line segments do not form closed ring. That is of course totaly different of what I need, as I want to get back largest possible polygon, potentially discarding all those smaller but it seem that they take precedence and mess up desired output. Is there any way to control how polygonizer work so that i get my big polygon back. Thanks Dragan Blagojevic -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] concave hull ref
That's an interesting idea too. It's always nice to look for ways to remove "magic numbers" from algorithms, and this one seems like a good candidate for doing that. Galton's approach of looking for some sort of minima on the "Pareto front" sounds like it's heading in this direction (although I admit I don't fully understand it, or how it leads to a workable algorithm). Larry Becker wrote: Everyone seems to use length as a parameter to determine the solution set. Length is dataset dependent. I wonder if this dependency could be factored out by specifying a percent of extent, or perhaps a target fractal dimension. Larry On Fri, Apr 3, 2009 at 10:48 AM, Martin Davis <mailto:mbda...@refractions.net>> wrote: Fascinating stuff... Here's a couple of the Galton papers Stefan refers to. http://www.comp.leeds.ac.uk/ontology/FOGI-WS/statements/Antony-Galton.pdf http://www.latingeo.net/datos_latingeo/noticias_doc/108Polyhulls-Galton.pdf He appears to be taking a psycho-computational approach to the problem. Interesting, but hard to see how this will translate into a concrete algorithm. (Although I guess the Duckham et al paper might have ideas on this). There was a thread on this on the PostGIS a while back, I think. There's definitely some non-patented approaches out there. See this for instance: http://n2.nabble.com/Concave-hull-of-a-set-of-points-(alphashapes)-td1880426.html#a1880426 <http://n2.nabble.com/Concave-hull-of-a-set-of-points-%28alphashapes%29-td1880426.html#a1880426> Stefan Steiniger wrote: Hi, anothe recent artile by Matt Duckham on Concave Hulls. The draft (not the final version) is here: http://www.geosensor.net/papers/duckham08.PR.pdf But I am not sure if these authors will chare their code. More articles on that have been published by one of the authors - Anthony Galton. Furthermore if you read the stuff you will see that there is no unique solution. stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org <mailto:jts-devel@lists.jump-project.org> http://lists.refractions.net/mailman/listinfo/jts-devel -- http://amusingprogrammer.blogspot.com/ ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] concave hull ref
Fascinating stuff... Here's a couple of the Galton papers Stefan refers to. http://www.comp.leeds.ac.uk/ontology/FOGI-WS/statements/Antony-Galton.pdf http://www.latingeo.net/datos_latingeo/noticias_doc/108Polyhulls-Galton.pdf He appears to be taking a psycho-computational approach to the problem. Interesting, but hard to see how this will translate into a concrete algorithm. (Although I guess the Duckham et al paper might have ideas on this). There was a thread on this on the PostGIS a while back, I think. There's definitely some non-patented approaches out there. See this for instance: http://n2.nabble.com/Concave-hull-of-a-set-of-points-(alphashapes)-td1880426.html#a1880426 Stefan Steiniger wrote: Hi, anothe recent artile by Matt Duckham on Concave Hulls. The draft (not the final version) is here: http://www.geosensor.net/papers/duckham08.PR.pdf But I am not sure if these authors will chare their code. More articles on that have been published by one of the authors - Anthony Galton. Furthermore if you read the stuff you will see that there is no unique solution. stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Empty geometry collection when simplifying polygon
Can you post the polygon and the simplification tolerances? And which simplification algorithm were you using? This could be a bug, of course. AFAIK, there's no standard about what should be returned by simplification in limit cases. I can imagine several possible requirements, all of which I can see be wanted in different situations: 1. return an empty geometry of the same dimension as the input 2. return a "minimal" geometry of the same dimension as the input (e.g. return a triangle at the limit of simplifying a polygon) (Some systems have constraints of the type of geometry they can accept, and/or expect the same type for the result as for the input) 3. return a line segment as you suggest 4. return an empty GEOMETRYCOLLECTION, signifying "null result" It might be nice to provide a flag to let the user choose his desired behaviour. BTW, the semantics of TopologyPreservingSimplifier are more precisely defined - it follows #2. Theodor Foerster wrote: Hi, I came across a polygon, which I need to simplify. The result is an empty GeometryCollection. However, when I choose a smaller tolerance value, it performs correctly. Is this behaviour intended? I am just curious. Intentionally, I would think, that the result is a line with two points in the worst case. Theodor ITC, Enschede Department of Geo Information Processing PO. Box 6 7500 AA Enschede the Netherlands International Institute for Geo-Information Science and Earth Observation (ITC) Chamber of Commerce: 410 27 560 E-mail disclaimer The information in this e-mail, including any attachments, is intended for the addressee only. If you are not the intended recipient, you are hereby notified that any disclosure, copying, distribution or action in relation to the content of this information is strictly prohibited. If you have received this e-mail by mistake, please delete the message and any attachment and inform the sender by return e-mail. ITC accepts no liability for any error or omission in the message content or for damage of any kind that may arise as a result of e-mail transmission. ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
[jts-devel] Re: [jump-users] jts question
The current IndexedPointInAreaLocator is in com.vividsolutions.jts.algorithm.locate. The other one is obsolete. Not sure how it snuck back into the distribution - but you can delete it safely. Martin ferdinand tomale wrote: Hello to all, I imported the sources for jts-1.10 into a eclipse plugin project. I found out that GeometryGraph contains an ambiguous reference to IndexedPointInAreaLocator that exists in packages com.vividsolutions.jts.algorithm and com.vividsolutions.jts.algorithm.locate. Is this correct? I suspect I am doing something wrong. Any pointers to exploring jts? Ultimately, I hope to build an application that will load and display shape files. I already checked out the udig project and it contains references to jts. So I have to learn jts first. Thanks! ___ jump-users mailing list jump-us...@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jump-users -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: what shall I do If I get a topology exception in union op?
No, I don't use this technique. It looks pretty complicated! And I have never seen any implementation examples on the web (which is the case for 90% of the papers out there, of course). For predicates I use the technique of exact determinant sign evaluation by Devillers et al. For robustness of line arrangment computation I use a snap-rounding approach (see Hobby and others). M Michael Bedward wrote: 2009/3/18 Martin Davis : So it doesn't need debugging - it needs some brilliant new thinking! Sounds like what I think about most of my code... Out of interest Martin, do you use anything like the approach described here... Edelsbrunner & Mucke (1990) Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.5997 I've been trying to understand it. Michael ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: what shall I do If I get a topology exception in union op?
No, unfortunately there's no debugging procedure. This situation is due to a known limitation in the current overlay algorithm design. So it doesn't need debugging - it needs some brilliant new thinking! Thanks for the dataset Good that you found a workaround. Martin Stefan Steiniger wrote: Hei Martin, thank you for your answer. So it seems there is no "debugging" procedure and instead you suggest a data simplification. I will send you the dataset in a personal email. I have actually now taken a different approach by splitting the datasets and using the Symmetric Difference Function in ArcGIS. stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] what shall I do If I get a topology exception in union op?
This is likely due to lines in the input which are almost, but not quite coincident. This would be caused by two polygons which have similar, but not identical, line(s) along a portion of their boundaries. These might be in a single layer, or they might be in different input layers. Unfortunately in general these are not easy to recover from. One thing you can try is to reduce the precision of your input geometries. I think the ultimate technical solution to this is to snap-round the datasets individually and together. Unfortunately I don't have code or an API for doing this at this point. The coordinates in the error message are not useful - they are in a translated coordinate system used internally. I'd be interested to see the input dataset, if you can provide it. Martin Stefan Steiniger wrote: Hei Martin and others, I get the exception below while intersecting two layers of polygons (in OpenJUMP >Tools>two Layers>intersect polygon layers). Is there a way to proceed despite the exception? Could it be that the problem is within one layer of polygons? i.e. overlapping polygons in one layer? The coordinates are also not useful [1] - not sure what coordinate system they are in??? stefan [1] bbox(677104.8683854531,228446.29622920923,687118.4247461993,237423.31161814026) com.vividsolutions.jts.geom.TopologyException: found non-noded intersection between LINESTRING ( 5453.3047 32281.0, 5454.177554877591 32280.11017162766 ) and LINESTRING ( 5454.177554877578 32280.110171627675, 5452.379085899257 32281.844875321825 ) [ (5454.177554877563, 32280.11017162769, NaN) ] at com.vividsolutions.jts.noding.FastNodingValidator.checkValid(FastNodingValidator.java:109) at com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:94) at com.vividsolutions.jts.geomgraph.EdgeNodingValidator.checkValid(EdgeNodingValidator.java:59) at com.vividsolutions.jts.operation.overlay.OverlayOp.computeOverlay(OverlayOp.java:170) at com.vividsolutions.jts.operation.overlay.OverlayOp.getResultGeometry(OverlayOp.java:127) at com.vividsolutions.jts.operation.overlay.OverlayOp.overlayOp(OverlayOp.java:66) at com.vividsolutions.jts.operation.overlay.snap.SnapOverlayOp.getResultGeometry(SnapOverlayOp.java:67) at com.vividsolutions.jts.operation.overlay.snap.SnapOverlayOp.overlayOp(SnapOverlayOp.java:24) at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.getResultGeometry(SnapIfNeededOverlayOp.java:76) at com.vividsolutions.jts.operation.overlay.snap.SnapIfNeededOverlayOp.overlayOp(SnapIfNeededOverlayOp.java:25) at com.vividsolutions.jts.geom.Geometry.union(Geometry.java:1173) at org.openjump.core.geomutils.algorithm.IntersectGeometries.nodeLines(IntersectGeometries.java:471) at org.openjump.core.ui.plugin.tools.IntersectPolygonLayersPlugIn.runIntersectionNew(IntersectPolygonLayersPlugIn.java:179) at org.openjump.core.ui.plugin.tools.IntersectPolygonLayersPlugIn.run(IntersectPolygonLayersPlugIn.java:112) at com.vividsolutions.jump.workbench.ui.task.TaskMonitorManager$TaskWrapper.run(TaskMonitorManager.java:149) at java.lang.Thread.run(Thread.java:619) ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] difference error
Yep, this is still an issue in the current JTS codebase. Thanks - I'll have a look at it. Diego Guidi wrote: ehm, I'm not sure that this is actually a bug, but... I've received a NTS issue (http://code.google.com/p/nettopologysuite/issues/detail?id=37) and )ve verified that the same behavior is also with JTS 1.8.0 and 1.9.0 (no tests with newer versions, sorry). see JTS test attached and here (http://code.google.com/p/nettopologysuite/source/browse/trunk/NetTopologySuite.Samples.Console/Tests/Various/Issue37Test.cs?spec=svn415&r=415) for NTS test Diego Guidi ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] difference error
There's no quick fix for this within JTS. The issue is caused by vertices being very close to line segments, which causes robustness failures during some internal operations. The philosophical fix is to carry less precision in the input geometries. (e.g. round them to .001 or something reasonable). This really should be provided as a function in JTS, but isn't quite there yet. You can simulate it in this case by rounding the coordinates and then doing a buffer(0) to fix up the (invalid) result. Diego Guidi wrote: ehm, I'm not sure that this is actually a bug, but... I've received a NTS issue (http://code.google.com/p/nettopologysuite/issues/detail?id=37) and )ve verified that the same behavior is also with JTS 1.8.0 and 1.9.0 (no tests with newer versions, sorry). see JTS test attached and here (http://code.google.com/p/nettopologysuite/source/browse/trunk/NetTopologySuite.Samples.Console/Tests/Various/Issue37Test.cs?spec=svn415&r=415) for NTS test Diego Guidi ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: Proper construction of a search graph from geometric, > objects
Thanks, Michael.
I'm not sure there's any easy lesson for JTS here - except maybe that
generics are a nice thing to have for graph libraries!
Michaël Michaud wrote:
Hi Martin,
I agree with your experience that it's just as reasonable to work at
the feature level rather than the geometry level. Graph-based
algorithms are pretty much orthogonal to geometric algorithms, so
there's not much to be gained from having the graph "know" about the
geometry. The one exception is precisely for planar graphs - in this
case, the geometry implies an ordering of edges around each node,
which is important for various algorithms in JTS.
Sure ! I cannot remember if JGraphT has any code to manage an ordered
list of incident edges, but It probably lack a lot of code to manage
PlanarGraphs as it is needed by a library like JTS.
Perhaps this is why you're seeing JGraphT being faster that JTS?
There is a cost to computing the edge ordering, of course.
Indeed, I wrote it is very fast, but I cannot affirm it is faster than
JTS as I did not perform the same calculation with JTS. I just saw
that computing graphs of large datasets (3 features) takes only 1
second (I have a very new corei7) and do not need a lot of memory.
Do you have some details of how JGraphT is easier to use than JTS?
It would be nice for development if the JTS graph structures were as
easy to use as possible.
Here after is a small piece of code showing how I build a simple
weighted graph from a feature collection.
Stefan gave the adresse of the complete source code.
After a graph is built, I can use any algorithm of the JGraphT
library, then go back from the result (generally a set of nodes or a
set of edges) to the underlying features.
Michaël
private static WeightedGraph
add(WeightedGraph graph, Collection
features, boolean dim3) {
Coordinate[] cc;
for (Iterator it = features.iterator() ; it.hasNext() ; ) {
Feature f = (Feature)it.next();
Geometry g = f.getGeometry();
cc = f.getGeometry().getCoordinates();
INode node1 = dim3? new Node3D(cc[0]) : new Node2D(cc[0]);
INode node2 = dim3? new Node3D(cc[cc.length-1]) : new
Node2D(cc[cc.length-1]);
graph.addVertex(node1);
graph.addVertex(node2);
FeatureAsEdge edge = new FeatureAsEdge(f);
graph.addEdge(node1, node2, edge);
graph.setEdgeWeight(edge, g.getLength());
}
return graph;
}
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: Proper construction of a search graph from geometric, > objects
Michael, I agree with your experience that it's just as reasonable to work at the feature level rather than the geometry level. Graph-based algorithms are pretty much orthogonal to geometric algorithms, so there's not much to be gained from having the graph "know" about the geometry. The one exception is precisely for planar graphs - in this case, the geometry implies an ordering of edges around each node, which is important for various algorithms in JTS. Perhaps this is why you're seeing JGraphT being faster that JTS? There is a cost to computing the edge ordering, of course. Do you have some details of how JGraphT is easier to use than JTS? It would be nice for development if the JTS graph structures were as easy to use as possible. Michaël Michaud wrote: Hi, I have used JGraphT with JTS for a while and I can say it is *very* fast. I use it to find nodes of a linear network, degree* of each node, cycles... When using JTS+JGraphT, I consider linear features as the edges of the graph and first and last coordinates of their geometry as the nodes. It may not fit all needs as the graph has no node where features intersect if intersection point is not already the extremity of those features. I have to admit that I first tried to do this with pure JTS (avoiding to add a 500kb jar), but it appeared much more complex to use. Maybe some convenient methods around PlanarGraph class would have helped me achieve the same goal in pure JTS, but now, I'm no more sure there are much benefits working at the geometry level rather than at the feature level. My two cents Michaël * if you try to use it, note that I just discovered a bug which returns a degree 4 node at the end of a single looping edge (should be degree 2) Stefan Steiniger a écrit : I think Michael Michaud also used JgraphT for his OpeJUMP Plugin: http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-0.3.jar http://geo.michaelm.free.fr/OpenJUMP/resources/jump-jgrapht-src-0.3.zip but maybe it is already what you meant with JUMP plugin stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Re: patch for Angle.java
Thanks, Michael. I've added this to JTS 1.11. This is crying out for
a unit test - so I've added one of those as well.
Michael Bedward wrote:
oops - sorry, here is the patch again without the spurious line at the top...
2009/3/8 Michael Bedward :
Hi Martin and everyone,
Angle.normalizePositive doesn't give the advertised results if the
input is greater than 2PI. I've attached a patch based on cvs code.
cheers
Michael
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Proper construction of a search graph from geometric objects
LineMergeGraph inherits the add(Node) method from PlanarGraph. But I would look at using PlanarGraph, not LineMergeGraph. LMG is specifically intended for line merging, which is probably not what you're trying to do. If all you have is Coordinates and LineStrings, then you should be able to use PlanarGraph directly. If you have other data structures which model nodes and edges, you have two choices - implement a subclass of PlanarGraph to map the external structures into the inputs that PlanarGraph requires, or use the set/getUserData methods on LineString to "carry" your original objects. As for algorithms, have a look at ConnectedSubgraphFinder for an example of how to build an algorithm class. Johnathan Kool wrote: Hi all - I'm in the middle of trying to implement a shortest path routine using JTS 1.9. I looked into using some of JUMP's graph extension functions, but in the end I think it may be easier to use what's available in JTS. I've managed to work out a visibility algorithm based on Coordinates, Geometry obstacles and LineString paths, but now need to construct a graph so I can run a Dijkstra search (or A*). Essentially, I have a collection of Coordinates/Nodes, and LineStrings representing 'allowable' edges. What's the best way of creating a searchable graph from these objects? I looked at the PlanarGraph Class, and the LineMergeGraph subclass. I thought that LineMergeGraph was what I was after, but it seems to be missing the .add(Node) method that PlanarGraph has (even though it is supposed to extend PlanarGraph?). I need addNode, because it's possible to have a node with no connecting edges. Thanks in advance for your help with this, J ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] US postal code simplification with JTS
Nice writeup, Doug - thanks! It sounds like you're using a 64-bit JVM - right? Any issues with that? I haven't been able to try large memory sizes with JTS - but it seems like it would allow much larger processes to be carried out. Doug Smith wrote: Hi JTS-ers, I just posted a writeup on the process we used to simplify all of the postal code polygons in the USA, thanks in large part to JTS. If you're interested, check it out here: http://webmonkeyswithlaserbeams.wordpress.com/ Special thanks to Martin for his insightful responses to my questions on this list. Doug --- Doug Smith ELP Web Developer http://www.daveramsey.com "Life is an occasion, rise to it" -- Mr. Magorium ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Simplification on an invalid polygon, expected behavior?
I notice you're using NTS (right?)... The behaviour in JTS is slightly
different - it returns a POLYGON EMPTY.
Simplification always returns a geometry of the same type as the input
geometry, and by default it attempts to ensure valid topology (by
applying a buffer(0) - which is a bit of a hack, I admit). This is why
it returns an empty polygon.
You can prevent the validity enforcement by using
DouglasPeuckerSimplifier.setEnsureValid(false)
AFAIK there's no clear standard on how to handle degenerate cases like
this - different use cases might require different kinds of output. You
should check for degenerate input first and convert it according to your
precise need.
Jeff Adams wrote:
It shouldn't have been zero, although I don't actually know what it
was (It was due to a bug in my code, that has since been fixed).
However I just tried to reproduce it with a test case and simplify
seems to return an empty geometrycollection (which seems like
resonable behavior, although better behavior might be to produce a
single point at the center). So perhaps I was mistaken about exactly
what was going on... It makes me wonder if my code that calls
simplify is not correct ;-). I'll let you know if I am able to
reproduce this again.
Here is my simple test case if you want to mess around with it:
[Test]
public void TestSimplifyBadPoly()
{
Polygon p = new Polygon(new LinearRing(new ICoordinate[] {
new Coordinate(1, 1), new Coordinate(1, 1),
new Coordinate(1, 1), new Coordinate(1, 1),
new Coordinate(1, 1)}));
Console.Out.WriteLine("Bad polygon: " + p);
IGeometry simpleP = DouglasPeuckerSimplifier.Simplify(p, 0.1);
Console.Out.WriteLine("Simple bad polygon: " + simpleP);
Assert.AreNotEqual(p, simpleP, "Simplify didn't do
anything to this invalid polygon.");
}
On Tue, Mar 3, 2009 at 11:39 AM, Martin Davis <mailto:mbda...@refractions.net>> wrote:
What was your simplification tolerance? If it was 0 as well, then
nothing would be changed.
If not, this might be a bug - although this is a bit outside what
would be considered as reasonable input to a simplification routine.
Jeff Adams wrote:
- Show quoted text -
I have some code that creates "circle" polygons given a
center, radius, and number of points. The circle gets passed
to some other code that happens to simplify the polygon (using
DouglasPeucker).
I accidentally wound up calling this code with a radius of
zero. This produced a 46-point polygon where all the points
were identical. What was surprising to me is that the
simplifier didn't seem to change it at all. I would have
expected it to return a single point, or throw an exception,
or something. Is this (doing nothing) the expected behavior?
Thanks,
Jeff
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Simplification on an invalid polygon, expected behavior?
What was your simplification tolerance? If it was 0 as well, then nothing would be changed. If not, this might be a bug - although this is a bit outside what would be considered as reasonable input to a simplification routine. Jeff Adams wrote: I have some code that creates "circle" polygons given a center, radius, and number of points. The circle gets passed to some other code that happens to simplify the polygon (using DouglasPeucker). I accidentally wound up calling this code with a radius of zero. This produced a 46-point polygon where all the points were identical. What was surprising to me is that the simplifier didn't seem to change it at all. I would have expected it to return a single point, or throw an exception, or something. Is this (doing nothing) the expected behavior? Thanks, Jeff ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Odd behavior in negative mitred buffer
As I suspected, this problem was due to robustness issues in computing
mitred joins for almost parallel segments. I've commited a fix for this
to CVS - it handles all the test cases that you provided.
Let me know if you find any other issues.
I'll look into building your test cases into the JTS Test Suite - it
really needs some good testing for the various buffer styles.
Martin
Gabriel Reid wrote:
Hi Martin,
I've got a few other failure cases here, showing what seems to be a few
different examples of this kind of behaviour:
// Simple five-sided polygon that gets transformed into three triangles
POLYGON ((589300.089821923 4519627.577687806, 589296.6197410262
4519621.834087054, 589292.5450979208 4519615.089809029,
589282.7894421419 4519620.983829066, 589289.8814929381
4519632.722288636, 589300.089821923 4519627.577687806))
// Another example of the same triangle behavior
POLYGON ((588978.2942617612 4519797.499233156, 588989.1612999197
4519792.050291001, 588982.5784094566 4519779.549041149,
588962.0866377753 4519790.334848753, 588967.4026187821
4519802.960530801, 588978.2942617612 4519797.499233156))
// Resulting polygon has a single edge extending off one corner
POLYGON ((589099.8017397423 4518490.719003885, 589097.1198886324
4518486.20858194, 589090.9424687021 4518475.819013388, 589069.8993093553
4518487.1362185385, 589078.7377975255 4518502.093799692,
589081.1515112884 4518509.334764771, 589103.7370954598
4518497.015419995, 589099.8017397423 4518490.719003885))
// Similar behaviour as the original case that was posted, this polygon
// has to points that are very close together
POLYGON ((587854.8616905196 4519121.941123185, 587863.6671614297
4519138.176489661, 587863.9386104685 4519138.676991724,
587880.5408633598 4519129.672513268, 587871.463857397
4519112.9366913745, 587854.8616905196 4519121.941123185))
All of these examples can be demonstrated with the code that I posted
before (creating a mitred buffer with a magnitude of -5.0).
Again, if you don't have time and/or motivation to look into this, I'd
be more than happy to attempt to assist in doing that, especially if you
have a good idea of where to look (I'm trying to have a look anyhow).
Thanks again for the assistance,
Gabriel
-Original Message-
From: jts-devel-boun...@lists.jump-project.org [mailto:jts-devel-
boun...@lists.jump-project.org] On Behalf Of Martin Davis
Sent: donderdag 26 februari 2009 17:50
To: JTS Topology Suite Development
Subject: Re: [jts-devel] Odd behavior in negative mitred buffer
Ok, Gabriel. It sounds like some progress, at least.
Please post the other failure cases when you have isolated them.
Perhaps the next problem will be as easy to solve as the last one...
8^)
Gabriel Reid wrote:
Hi Martin,
Thanks a lot for the quick support!
I just tested this on the full dataset that I've been working with,
and
there are still some cases coming out; I'll try to isolate what the
situation is with those cases and see if there is a pattern (or if I
can
do something further with data cleaning).
I'll keep you posted.
Gabriel
-Original Message-
From: jts-devel-boun...@lists.jump-project.org [mailto:jts-devel-
boun...@lists.jump-project.org] On Behalf Of Martin Davis
Sent: donderdag 26 februari 2009 2:22
To: JTS Topology Suite Development
Subject: Re: [jts-devel] Odd behavior in negative mitred buffer
Good news! I looked into this problem, and found a minor bug in
the
buffer input simplification algorithm. With this fix the situation
you
provided is no longer a problem.
This is commited to CVS.
Can you try this out on to see if it solves the other problems you
have
encountered?
Martin Davis wrote:
This is probably due to some sort of limitation with the mitring
algorithm. However, I notice that the 7th and 8th points of your
geometry are almost identical. If I remove one of these, the
mitred
buffer looks fine. Can you clean the points of your geometries
somehow to avoid this situation?
Gabriel Reid wrote:
Hi,
I'm trying to create a negative mitred buffer on a (simple)
polygon
with
JTS 1.10, and I'm getting strange results very occasionally. For
example, the following code gives me an output geometry that
actually
extends outside the original geometry (even though a negative
buffer is
used).
WKTReader wktReader = new WKTReader();
String geom = "POLYGON ((588736.6028960398 4518922.914991864,
"
+ "588736.1060708747 4518922.061957178,
588718.6830715544 "
+ "4518930.620699637, 588712.0102834741
4518933.8985304395, "
+ "588722.7612465625 4518964.9567394
Re: [jts-devel] Odd behavior in negative mitred buffer
Thanks for the test cases, Gabriel. These errors are almost certainly caused by some shortcoming(s) in the algorithm for generating a mitred buffer offset curve. The errors seem to be linked to situations with almost flat angles - that might be part of the problem. Probably some further heuristics are needed to generate better quality offset curves in this case. Gabriel Reid wrote: Hi Martin, I've got a few other failure cases here, showing what seems to be a few different examples of this kind of behaviour: // Simple five-sided polygon that gets transformed into three triangles POLYGON ((589300.089821923 4519627.577687806, 589296.6197410262 4519621.834087054, 589292.5450979208 4519615.089809029, 589282.7894421419 4519620.983829066, 589289.8814929381 4519632.722288636, 589300.089821923 4519627.577687806)) // Another example of the same triangle behavior POLYGON ((588978.2942617612 4519797.499233156, 588989.1612999197 4519792.050291001, 588982.5784094566 4519779.549041149, 588962.0866377753 4519790.334848753, 588967.4026187821 4519802.960530801, 588978.2942617612 4519797.499233156)) // Resulting polygon has a single edge extending off one corner POLYGON ((589099.8017397423 4518490.719003885, 589097.1198886324 4518486.20858194, 589090.9424687021 4518475.819013388, 589069.8993093553 4518487.1362185385, 589078.7377975255 4518502.093799692, 589081.1515112884 4518509.334764771, 589103.7370954598 4518497.015419995, 589099.8017397423 4518490.719003885)) // Similar behaviour as the original case that was posted, this polygon // has to points that are very close together POLYGON ((587854.8616905196 4519121.941123185, 587863.6671614297 4519138.176489661, 587863.9386104685 4519138.676991724, 587880.5408633598 4519129.672513268, 587871.463857397 4519112.9366913745, 587854.8616905196 4519121.941123185)) All of these examples can be demonstrated with the code that I posted before (creating a mitred buffer with a magnitude of -5.0). Again, if you don't have time and/or motivation to look into this, I'd be more than happy to attempt to assist in doing that, especially if you have a good idea of where to look (I'm trying to have a look anyhow). Thanks again for the assistance, Gabriel -Original Message- From: jts-devel-boun...@lists.jump-project.org [mailto:jts-devel- boun...@lists.jump-project.org] On Behalf Of Martin Davis Sent: donderdag 26 februari 2009 17:50 To: JTS Topology Suite Development Subject: Re: [jts-devel] Odd behavior in negative mitred buffer Ok, Gabriel. It sounds like some progress, at least. Please post the other failure cases when you have isolated them. Perhaps the next problem will be as easy to solve as the last one... 8^) Gabriel Reid wrote: Hi Martin, Thanks a lot for the quick support! I just tested this on the full dataset that I've been working with, and there are still some cases coming out; I'll try to isolate what the situation is with those cases and see if there is a pattern (or if I can do something further with data cleaning). I'll keep you posted. Gabriel -Original Message- From: jts-devel-boun...@lists.jump-project.org [mailto:jts-devel- boun...@lists.jump-project.org] On Behalf Of Martin Davis Sent: donderdag 26 februari 2009 2:22 To: JTS Topology Suite Development Subject: Re: [jts-devel] Odd behavior in negative mitred buffer Good news! I looked into this problem, and found a minor bug in the buffer input simplification algorithm. With this fix the situation you provided is no longer a problem. This is commited to CVS. Can you try this out on to see if it solves the other problems you have encountered? Martin Davis wrote: This is probably due to some sort of limitation with the mitring algorithm. However, I notice that the 7th and 8th points of your geometry are almost identical. If I remove one of these, the mitred buffer looks fine. Can you clean the points of your geometries somehow to avoid this situation? Gabriel Reid wrote: Hi, I'm trying to create a negative mitred buffer on a (simple) polygon with JTS 1.10, and I'm getting strange results very occasionally. For example, the following code gives me an output geometry that actually extends outside the original geometry (even though a negative buffer is used). WKTReader wktReader = new WKTReader(); String geom = "POLYGON ((588736.6028960398 4518922.914991864, " + "588736.1060708747 4518922.061957178, 588718.6830715544 " + "4518930.620699637, 588712.0102834741 4518933.8985304395, " + "588722.7612465625 4518964.956739423, 588755
Re: [jts-devel] Intersections of cells in a GridCoverage with a LineString
How about creating a set of polygons equal in shape to your grid cells, and then intersect the line string with each polygon that it touches? You can use a spatial index (STRtree) to speed up finding candidate polygons. Martin Pete Ballack wrote: Hello, I posted the same question on the geotools-user-list and Michael Bedward responded as follows "However, I suggest you pose the same question on the JTS list where Martin Davis and the other geometric gurus might be able to help." So here is my message... I painted a small Graphic that should help to understand my current problem (I didn't want to post it on the mailing list directly) Here is the Link to the graphic. http://bayimg.com/oaNDJAaBn I created a GridCoverage with a specified cellsize to rasterize an area double width = envelope.getWidth(); // i.e. 1000m double height = envelope.getHeight(); // i.e. 1000m int numCellX = (int) Math.floor( width / cellSize ); // cellSize i.e. 10m int numCellY = (int) Math.floor( height / cellSize ); WritableRaster raster = RasterFactory.createBandedRaster( DataBuffer.TYPE_FLOAT, numCellX, numCellY, 1, null ); GridCoverage2D gridCoverage = factory.create( "My coverage", raster, envelope ); Now my Problem: The values of a cell in the raster depends on the length of the LineString covering the cell. (in my Image the green part of the LineString would determine the value of d;2) I belive that their is no function available doing that. So my idea to solve my problem is some workaround I'm not really satisfied with. 1.create a graph corresponding to the raster (width, height and cellsize) 2.for a given LineString find all intersection points with the created graph 3.for all following intersection points (i, i+1) a.calculate the length -> value for the cell b.get the middle point between (i, i+1) to find the corresponding cell c.add value to cell Maybe somebody has a smarter idea to solve my problem. Thanks Pete here is the link to my posting on the geotools-mailing-list http://n2.nabble.com/Intersections-of-cells-in-a-GridCoverage-with-a-LineString-td2405815.html ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 Hello, I posted the same question on the geotools-user-list and Michael Bedward responded as follows "However, I suggest you pose the same question on the JTS list where Martin Davis and the other geometric gurus might be able to help." So here is my message... I painted a small Graphic that should help to understand my current problem (I didn't want to post it on the mailing list directly) Here is the Link to the graphic. http://bayimg.com/oaNDJAaBn I created a GridCoverage with a specified cellsize to rasterize an area double width = envelope.getWidth(); // i.e. 1000m double height = envelope.getHeight(); // i.e. 1000m int numCellX = (int) Math.floor( width / cellSize ); // cellSize i.e. 10m int numCellY = (int) Math.floor( height / cellSize ); WritableRaster raster = RasterFactory.createBandedRaster( DataBuffer.TYPE_FLOAT, numCellX, numCellY, 1, null ); GridCoverage2D gridCoverage = factory.create( "My coverage", raster, envelope ); Now my Problem: The values of a cell in the raster depends on the length of the LineString covering the cell. (in my Image the green part of the LineString would determine the value of d;2) I belive that their is no function available doing that. So my idea to solve my problem is some workaround I'm not really satisfied with. 1.create a graph corresponding to the raster (width, height and cellsize) 2.for a given LineString find all intersection points with the created graph 3.for all following intersection points (i, i+1) a.calculate the length -> value for the cell b.get the middle point between (i, i+1) to find the corresponding cell c.add value to cell Maybe somebody has a smarter idea to solve my problem. Thanks Pete here is the link to my posting on the geotools-mailing-list http://n2.nabble.com/Intersections-of-cells-in-a-GridCoverage-with-a-LineString-td2405815.html ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 Hello, I posted the same question on the geotools-user-list and Michael Bedward respon
Re: [jts-devel] Re: Odd behavior in negative mitred buffer
No, the simplification *helped* in the case that I looked at. And for the other cases, I'm pretty sure it's not the simplification which is causing the problem, it's the logic for generating the mitred offset curve. Stefan Steiniger wrote: why not simply disabling the simplification for negative buffer values. that seems the easiest and fastest way? Or is there a real need for a speed improvement for negative buffers as well? stefan ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Odd behavior in negative mitred buffer
Ok, Gabriel. It sounds like some progress, at least. Please post the other failure cases when you have isolated them. Perhaps the next problem will be as easy to solve as the last one... 8^) Gabriel Reid wrote: Hi Martin, Thanks a lot for the quick support! I just tested this on the full dataset that I've been working with, and there are still some cases coming out; I'll try to isolate what the situation is with those cases and see if there is a pattern (or if I can do something further with data cleaning). I'll keep you posted. Gabriel -Original Message- From: jts-devel-boun...@lists.jump-project.org [mailto:jts-devel- boun...@lists.jump-project.org] On Behalf Of Martin Davis Sent: donderdag 26 februari 2009 2:22 To: JTS Topology Suite Development Subject: Re: [jts-devel] Odd behavior in negative mitred buffer Good news! I looked into this problem, and found a minor bug in the buffer input simplification algorithm. With this fix the situation you provided is no longer a problem. This is commited to CVS. Can you try this out on to see if it solves the other problems you have encountered? Martin Davis wrote: This is probably due to some sort of limitation with the mitring algorithm. However, I notice that the 7th and 8th points of your geometry are almost identical. If I remove one of these, the mitred buffer looks fine. Can you clean the points of your geometries somehow to avoid this situation? Gabriel Reid wrote: Hi, I'm trying to create a negative mitred buffer on a (simple) polygon with JTS 1.10, and I'm getting strange results very occasionally. For example, the following code gives me an output geometry that actually extends outside the original geometry (even though a negative buffer is used). WKTReader wktReader = new WKTReader(); String geom = "POLYGON ((588736.6028960398 4518922.914991864, " + "588736.1060708747 4518922.061957178, 588718.6830715544 " + "4518930.620699637, 588712.0102834741 4518933.8985304395, " + "588722.7612465625 4518964.956739423, 588755.2073151038 " + "4518948.2420851765, 588750.2892019567 4518938.490656119, " + "588750.2892047082 4518938.490654858, 588741.1098934844 " + "4518920.290260831, 588736.6028960398 4518922.914991864))"; Geometry inputGeometry = wktReader.read(geom); BufferParameters bufferParameters = new BufferParameters(); bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); Geometry bufferedGeometry = BufferOp.bufferOp( inputGeometry, -5.0, bufferParameters); I've tried using a few different strategies in investigating this, such as reducing the coordinate precision, offsetting the x and/or y coordinates by a constant offset, or iteratively buffering the geometry (for example, buffering it five times by -1.0). All of these strategies have had limited success, and none seem to work in all cases that I'm encountering. Does this situation spring out to anyone, or is there any advice on how to get around this (or is this the expected behaviour for some reason?). I would be happy to *attempt* to fix this in JTS if someone can point me in the general direction of where the issue probably is. Thanks in advance for any information, Gabriel Reid ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Odd behavior in negative mitred buffer
Good news! I looked into this problem, and found a minor bug in the buffer input simplification algorithm. With this fix the situation you provided is no longer a problem. This is commited to CVS. Can you try this out on to see if it solves the other problems you have encountered? Martin Davis wrote: This is probably due to some sort of limitation with the mitring algorithm. However, I notice that the 7th and 8th points of your geometry are almost identical. If I remove one of these, the mitred buffer looks fine. Can you clean the points of your geometries somehow to avoid this situation? Gabriel Reid wrote: Hi, I'm trying to create a negative mitred buffer on a (simple) polygon with JTS 1.10, and I'm getting strange results very occasionally. For example, the following code gives me an output geometry that actually extends outside the original geometry (even though a negative buffer is used). WKTReader wktReader = new WKTReader(); String geom = "POLYGON ((588736.6028960398 4518922.914991864, " + "588736.1060708747 4518922.061957178, 588718.6830715544 " + "4518930.620699637, 588712.0102834741 4518933.8985304395, " + "588722.7612465625 4518964.956739423, 588755.2073151038 " + "4518948.2420851765, 588750.2892019567 4518938.490656119, " + "588750.2892047082 4518938.490654858, 588741.1098934844 " + "4518920.290260831, 588736.6028960398 4518922.914991864))"; Geometry inputGeometry = wktReader.read(geom); BufferParameters bufferParameters = new BufferParameters(); bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); Geometry bufferedGeometry = BufferOp.bufferOp( inputGeometry, -5.0, bufferParameters); I've tried using a few different strategies in investigating this, such as reducing the coordinate precision, offsetting the x and/or y coordinates by a constant offset, or iteratively buffering the geometry (for example, buffering it five times by -1.0). All of these strategies have had limited success, and none seem to work in all cases that I'm encountering. Does this situation spring out to anyone, or is there any advice on how to get around this (or is this the expected behaviour for some reason?). I would be happy to *attempt* to fix this in JTS if someone can point me in the general direction of where the issue probably is. Thanks in advance for any information, Gabriel Reid ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] concave hull
Ok, keep checking back. Convex hulls seem to be of great interest
suddenly, so it would be nice to get one into JTS.
PeGa FaL wrote:
Hi
Thanks for replying.
Unfortunately, we don't have any budgets on this project. This is the
project that my close friends and I are doing for fun.
Please do let me know when the concave hull is implemented (if there
is one at all).
In the meanwhile, I'll be checking JTS websites every now and then.
Thanks
On Wed, Feb 25, 2009 at 5:27 PM, Martin Davis <mailto:mbda...@refractions.net>> wrote:
No, not right now. This would be nice to have, though, and I have
looked a bit at what would be required to do this. If you need
this fast and are able to fund development, I'd be interested in
discussing that.
PeGa FaL wrote:
Hi
Does JTS have implementation for Concave Hull? I know JTS has
Convex Hull implemantation but this is not suited for our
project requirement.
Thanks
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
<mailto:jts-devel@lists.jump-project.org>
http://lists.refractions.net/mailman/listinfo/jts-devel
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022
___
jts-devel mailing list
jts-devel@lists.jump-project.org
http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] concave hull
No, not right now. This would be nice to have, though, and I have looked a bit at what would be required to do this. If you need this fast and are able to fund development, I'd be interested in discussing that. PeGa FaL wrote: Hi Does JTS have implementation for Concave Hull? I know JTS has Convex Hull implemantation but this is not suited for our project requirement. Thanks ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Odd behavior in negative mitred buffer
Ok, let me know if you find anything. I'll try and take a look as well. Gabriel Reid wrote: Hi Martin, I'm trying to create a negative mitred buffer on a (simple) polygon with JTS 1.10, and I'm getting strange results very occasionally. For example, the following code gives me an output geometry that actually extends outside the original geometry (even though a negative buffer is used). This is probably due to some sort of limitation with the mitring algorithm. However, I notice that the 7th and 8th points of your geometry are almost identical. If I remove one of these, the mitred buffer looks fine. Can you clean the points of your geometries somehow to avoid this situation? Based on what I've seen, it does indeed seem to be due to very short edges. I've tried cleaning the geometry by reducing coordinate precision to one place past the decimal and then running it through a DouglasPeuckerSimplifier with a tolerance of 0 to remove duplicate coordinates, but this still problem still comes out sometimes (as there are still some very close coordinates present). I believe I can clean out all the extremely short edges another way, but I'm also taking a look at the code in the OffsetCurveBuilder to see if I can find where it's going wrong. Regards, Gabriel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Odd behavior in negative mitred buffer
This is probably due to some sort of limitation with the mitring algorithm. However, I notice that the 7th and 8th points of your geometry are almost identical. If I remove one of these, the mitred buffer looks fine. Can you clean the points of your geometries somehow to avoid this situation? Gabriel Reid wrote: Hi, I'm trying to create a negative mitred buffer on a (simple) polygon with JTS 1.10, and I'm getting strange results very occasionally. For example, the following code gives me an output geometry that actually extends outside the original geometry (even though a negative buffer is used). WKTReader wktReader = new WKTReader(); String geom = "POLYGON ((588736.6028960398 4518922.914991864, " + "588736.1060708747 4518922.061957178, 588718.6830715544 " + "4518930.620699637, 588712.0102834741 4518933.8985304395, " + "588722.7612465625 4518964.956739423, 588755.2073151038 " + "4518948.2420851765, 588750.2892019567 4518938.490656119, " + "588750.2892047082 4518938.490654858, 588741.1098934844 " + "4518920.290260831, 588736.6028960398 4518922.914991864))"; Geometry inputGeometry = wktReader.read(geom); BufferParameters bufferParameters = new BufferParameters(); bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE); Geometry bufferedGeometry = BufferOp.bufferOp( inputGeometry, -5.0, bufferParameters); I've tried using a few different strategies in investigating this, such as reducing the coordinate precision, offsetting the x and/or y coordinates by a constant offset, or iteratively buffering the geometry (for example, buffering it five times by -1.0). All of these strategies have had limited success, and none seem to work in all cases that I'm encountering. Does this situation spring out to anyone, or is there any advice on how to get around this (or is this the expected behaviour for some reason?). I would be happy to *attempt* to fix this in JTS if someone can point me in the general direction of where the issue probably is. Thanks in advance for any information, Gabriel Reid ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Geometry to WKT
Yeah, I guess it makes sense to deprecate it.. John Cartwright wrote: Thanks, that'll be great. Can you also remove or deprecate the toText method at that time? --john Martin Davis wrote: Cool - I'll add this for ver 1.11 John Cartwright wrote: I like that suggestion even better! --john Martin Davis wrote: Good point, Ken. Maybe even better would be toWKT() and toWKB() methods - that would be very explicit about what is being returned. Ken Tanaka wrote: I think that it's reasonable that the methods toString and toText are the same, but the toString output shouldn't be relied on for WKT representations--typically toString contains whatever the author of the API feels is useful to know about the object and its format may change in future implementations unless the JavaDoc defines and commits to maintain a given format into the future. The toText is expected conform to the WKT format -Ken John Cartwright wrote: Hello All, I'm just looking for a little clarification on converting a Geometry to it's WKT representation. It looks to me like Geometry#toString and Geometry#toText produce the same result. Is there any reason to use one over the other? Given both these return the WKT, why would one choose to use the WKTWriter#write method? Thanks! --john ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Geometry to WKT
Cool - I'll add this for ver 1.11 John Cartwright wrote: I like that suggestion even better! --john Martin Davis wrote: Good point, Ken. Maybe even better would be toWKT() and toWKB() methods - that would be very explicit about what is being returned. Ken Tanaka wrote: I think that it's reasonable that the methods toString and toText are the same, but the toString output shouldn't be relied on for WKT representations--typically toString contains whatever the author of the API feels is useful to know about the object and its format may change in future implementations unless the JavaDoc defines and commits to maintain a given format into the future. The toText is expected conform to the WKT format -Ken John Cartwright wrote: Hello All, I'm just looking for a little clarification on converting a Geometry to it's WKT representation. It looks to me like Geometry#toString and Geometry#toText produce the same result. Is there any reason to use one over the other? Given both these return the WKT, why would one choose to use the WKTWriter#write method? Thanks! --john ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
Re: [jts-devel] Geometry to WKT
Good point, Ken. Maybe even better would be toWKT() and toWKB() methods - that would be very explicit about what is being returned. Ken Tanaka wrote: I think that it's reasonable that the methods toString and toText are the same, but the toString output shouldn't be relied on for WKT representations--typically toString contains whatever the author of the API feels is useful to know about the object and its format may change in future implementations unless the JavaDoc defines and commits to maintain a given format into the future. The toText is expected conform to the WKT format -Ken John Cartwright wrote: Hello All, I'm just looking for a little clarification on converting a Geometry to it's WKT representation. It looks to me like Geometry#toString and Geometry#toText produce the same result. Is there any reason to use one over the other? Given both these return the WKT, why would one choose to use the WKTWriter#write method? Thanks! --john ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 ___ jts-devel mailing list jts-devel@lists.jump-project.org http://lists.refractions.net/mailman/listinfo/jts-devel
