For what it's worth, here's an example of parallelizing CascadedPolygonUnion using JDK8 parallel streams:
https://gist.github.com/dbaston/6b32fcb8c70d4d58775b Cheers, Dan ________________________________________ From: [email protected] <[email protected]> Sent: Monday, November 30, 2015 12:52 PM To: [email protected] Subject: Jts-topo-suite-user Digest, Vol 70, Issue 6 Send Jts-topo-suite-user mailing list submissions to [email protected] To subscribe or unsubscribe via the World Wide Web, visit https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user or, via email, send a message with subject or body 'help' to [email protected] You can reach the person managing the list at [email protected] When replying, please edit your Subject line so it is more specific than "Re: Contents of Jts-topo-suite-user digest..." Today's Topics: 1. Re: Regarding Query from the STRtree (Martin Davis) 2. Re: JTS and Parallel Computing (Kay, Jim) ---------------------------------------------------------------------- Message: 1 Date: Mon, 30 Nov 2015 09:51:13 -0800 From: Martin Davis <[email protected]> Subject: Re: [Jts-topo-suite-user] Regarding Query from the STRtree To: Saurav Ranjit <[email protected]> Cc: "[email protected]" <[email protected]> Message-ID: <cak2ens14axx_9krjbfjyz2y4me2flq-sag3fj2fu8m05xwc...@mail.gmail.com> Content-Type: text/plain; charset="utf-8" The reason for the multiple results is that the STRtree queries based on the envelopes of the indexed geometries. (This is known as a "primary filter" in spatial querying [1]). You need to implement a "secondary filter" to execute the actual spatial test you want to perform. In the case of testing whether a point "belongs" to a line segment you will need to decide whether you want a precise geometric test, or (more likely) a test based on distance between the point and the linestring. For the first case use Line.covers(Point), for the second use Line.distance(Point). [1] https://books.google.ca/books?id=8shsCQAAQBAJ&pg=PA405&lpg=PA405&dq=geometry+primary+filter&source=bl&ots=ziVSr9mspm&sig=dr55bdT8yt9nYyqI5ePW4HykJqY&hl=en&sa=X&ved=0ahUKEwjQmZqP2rjJAhUVfYgKHZEPAuMQ6AEINDAF#v=onepage&q=geometry%20primary%20filter&f=false On Sun, Nov 29, 2015 at 6:14 AM, Saurav Ranjit <[email protected]> wrote: > Hi everyone, > > I am new to the jts. I am trying to query in which line segment the gps > point belongs to using the STRtree. I created the STRtree using the WKT > format of linestring. I am able to perform the query using "List<Object[]> > search_result = index.query(search);". But in many case the it produced > multiple result. > > For example for the point "13.7127, 100.52007", the query is giving me 3 > result of different line segments. > > LINESTRING (100.51997 13.71225,100.52005 13.71278,100.52009 13.71366) > LINESTRING (100.52007 13.71224,100.52012 13.71263,100.52019 > 13.71351,100.52021 13.71375) > LINESTRING (100.5196 13.71037,100.51978 13.71085,100.52001 > 13.71153,100.52017 13.71211,100.52021 13.71233,100.52026 13.71263,100.52033 > 13.71335,100.52035 13.71374,100.52035 13.71377,100.52033 13.7145,100.52023 > 13.7155,100.52023 13.71558,100.52023 13.7156,100.52023 13.71596) > > I would like to know exactly in which line segment the point belongs to. I > have also attached the image of the point and the line segment here. > > Please let me know regarding my questions. > > Thank you very much for the help > > Regards, > Saurav Ranjit > Master's in Engineering of Remote Sensing and Geographic Information > Systems (RSGIS) > School of Engineering and Technology (SET) > Asian Institute of Technology (AIT) > Thailand > Mobile: (+66) 800544946 > Skype: sauravranjit > > > ------------------------------------------------------------------------------ > Go from Idea to Many App Stores Faster with Intel(R) XDK > Give your users amazing mobile app experiences with Intel(R) XDK. > Use one codebase in this all-in-one HTML5 development environment. > Design, debug & build mobile apps & 2D/3D high-impact games for multiple > OSs. > http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140 > _______________________________________________ > Jts-topo-suite-user mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > -------------- next part -------------- An HTML attachment was scrubbed... ------------------------------ Message: 2 Date: Mon, 30 Nov 2015 17:52:01 +0000 From: "Kay, Jim" <[email protected]> Subject: Re: [Jts-topo-suite-user] JTS and Parallel Computing To: Martin Davis <[email protected]> Cc: "[email protected]" <[email protected]> Message-ID: <[email protected]> Content-Type: text/plain; charset="utf-8" ?Another operation which uses a recursive tree structure is CascadedPolygonUnion. This should be fairly easy to make parallel, I think? Exactly the same one I was thinking of! (and just started to look at). The new concurrent classes in JDK 8 look promising, in particular the RecursiveTask and ForkJoinPool. Jim From: Martin Davis [mailto:[email protected]] Sent: 30 November 2015 17:41 To: Kay, Jim Cc: [email protected] Subject: Re: [Jts-topo-suite-user] JTS and Parallel Computing I've given parallel computation with JTS only some casual thought, but one thing that occurred to me is that there's two ways to parallelize geometry computation with JTS. The first is what I'll call *external* parallelism. In this scenario JTS itself runs sequentially, but the invoking process is parallelized. In many cases the client process is easily parallelizable, so this provides improved throughput for low effort. The other approach is *internal* parallelism, in which JTS algorithms are reworked to offer some degree of multi-execution. This sounds like what you're thinking of. Is it the case that the frameworks mentioned can only improve performance for internal parallelism? (In which case I'm curious to know why this is - and to what extent it's in fact possible.) For internal parallelism, the obvious place to look is at the major loops in the processes. In the case of overlay operations, this would be the noding phase. Ironically, the algorithms which provide best performance in the sequential case often are not ones which parallelize. For instance, currently overlay uses a sweepline algorithm for noding (SimpleMCSweepLineIntersector), which is inherently sequential. To parallelize this it would be better to use something like MCIndexNoder, which iterates over a set of unordered chains. In the case of distance, the current (inefficient) algorithm iterates over a set of unordered geometry "facets", so this should be easily parallelized. However, there's a much more efficient approach which is to use a Branch-and-Bound algorithm over two spatial indexes. Perhaps this would be harder to parallelize? Another operation which uses a recursive tree structure is CascadedPolygonUnion. This should be fairly easy to make parallel, I think. One worthy goal would be to generalize the code so that it is easy to switch between parallel and sequential execution modes. How hard would this be? On Mon, Nov 30, 2015 at 12:44 AM, Kay, Jim <[email protected]<mailto:[email protected]>> wrote: I am starting to think about dipping my toe in the water of Java parallel computing; possibly using JCuda for gpu calculations, or PJ2 for everything, or possibly MPJ-Express. Has anybody got any experience or advice of using JTS in a parallel Java world? Our application principally uses a lot of basic Polygon operations (union, intersection, distance between geometries). Can anybody provide any useful pointers as to which core Geometry routines might benefit from speedup by being rewritten to use parallel methods? Thanks. Jim Jim Kay Principal Engineer Tel: +44 (0) 1332 223229<tel:%2B44%20%280%29%201332%20223229> Mob: +44 (0) 7715 536828<tel:%2B44%20%280%29%207715%20536828> Email: [email protected]<mailto:[email protected]> [cid:[email protected]] interfleetgroup.com<http://www.interfleetgroup.com/> | snclavalin.com<http://snclavalin.com> ------------------------------------------------------------------------------ Go from Idea to Many App Stores Faster with Intel(R) XDK Give your users amazing mobile app experiences with Intel(R) XDK. Use one codebase in this all-in-one HTML5 development environment. Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs. http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140 _______________________________________________ Jts-topo-suite-user mailing list [email protected]<mailto:[email protected]> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user -------------- next part -------------- An HTML attachment was scrubbed... -------------- next part -------------- A non-text attachment was scrubbed... Name: image001.jpg Type: image/jpeg Size: 853 bytes Desc: image001.jpg -------------- next part -------------- A non-text attachment was scrubbed... Name: image002.png Type: image/png Size: 12533 bytes Desc: image002.png ------------------------------ ------------------------------------------------------------------------------ Go from Idea to Many App Stores Faster with Intel(R) XDK Give your users amazing mobile app experiences with Intel(R) XDK. Use one codebase in this all-in-one HTML5 development environment. Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs. http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140 ------------------------------ _______________________________________________ Jts-topo-suite-user mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user End of Jts-topo-suite-user Digest, Vol 70, Issue 6 ************************************************** ------------------------------------------------------------------------------ Go from Idea to Many App Stores Faster with Intel(R) XDK Give your users amazing mobile app experiences with Intel(R) XDK. Use one codebase in this all-in-one HTML5 development environment. Design, debug & build mobile apps & 2D/3D high-impact games for multiple OSs. http://pubads.g.doubleclick.net/gampad/clk?id=254741911&iu=/4140 _______________________________________________ Jts-topo-suite-user mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
