Hi Andrè, thanks for reporting the stats. Seems to be fairly clear what is fastest :)
stefan Am 02.09.13 09:08, schrieb André Salvati: > Hi, > > see bellow a comparison between methods that we've discussed. I've had > to put calls inside a loop with 10000 requests to get elapsed times with > more than 1 ms. These data were obtained from F2 instances from Google > App Engine (1200MHz processors and 256MB of memory) and were inside the > context of our app. > > Number of points -> 552 > containsProperly(), from a PreparedGeometry (10000 requests) -> 8 ms > isWithinDistance(), from a LineString (10000 requests) -> 282 ms > contains(), from a Geometry (10000 requests) -> 4984 ms > > Number of points -> 552 > containsProperly(), from a PreparedGeometry (10000 requests) -> 12 ms > isWithinDistance(), from a LineString (10000 requests) -> 459 ms > contains(), from a Geometry (10000 requests) -> 4591 ms > > Number of points -> 367 > containsProperly(), from a PreparedGeometry (10000 requests) -> 3 ms > isWithinDistance(), from a LineString (10000 requests) -> 472 ms > contains(), from a Geometry (10000 requests) -> 2882 ms > > Number of points -> 219 > containsProperly(), from a PreparedGeometry (10000 requests) -> 8 ms > isWithinDistance(), from a LineString (10000 requests) -> 89 ms > contains(), from a Geometry (10000 requests) -> 1687 ms > > Number of points -> 254 > containsProperly(), from a PreparedGeometry (10000 requests) -> 13 ms > isWithinDistance(), from a LineString (10000 requests) -> 132 ms > contains(), from a Geometry (10000 requests) -> 1796 ms > > > > > 2013/8/26 André Fernando Salvati <[email protected] > <mailto:[email protected]>> > > > Ok Martin, > > I'm going to do some tests and share the results. > > Thank you all for your comments and ideas. > > > 2013/8/26 Martin Davis <[email protected] <mailto:[email protected]>> > > This is a very interesting question. Stefan and Michael have > provided some useful comments. Here's a little more information > about the issue, focussing on what's in JTS today, and what > could be added to improve the story. > > As you point out, there are two general approaches to this > computation: > > 1) buffer the LIneString by the query distance and compute > "contains" (or actually "containsProperly", which is a simpler > predicate) > 2) Compute the isWithinDistance predicate on the LineString > > It's hard to say which is faster *now* in JTS, and even harder > to say which is theoretically the fastest. You'll really have > to try both and see. Here's what's in JTS now: > > For #1, you should use PreparedGeometry to preprocess the buffer > polygon. My guess is that the cost of computing the initial > buffer is totally dominated by the query time. Then use the > "cointainsProperly" predicate. This will utilized indexing to > optimize the Point-In-Polygon computation. It is thread-safe now > in trunk, so you may want to build from trunk and use that code. > > For #2, the current JTS isWithinDistance is not fully optimized > for large LineStrings, since it uses a brute-force approach. > Still, if the input LineString has a fairly low number of > vertices it may still be faster than #1. As Michael pointed > out, this can be improve by indexing the LineString segments > using an STRtree and using the nearestNeighbour method to do a > fast NN query. The intention is to implement this in JTS as new > methods on the PreparedGeometry class - most of the code is > done, but it still needs to be packaged for production. > > It would be very interesting to hear which of these methods > turns out to be the fasted in your case. > > > > On Mon, Aug 26, 2013 at 10:21 AM, André Salvati > <[email protected] <mailto:[email protected]>> > wrote: > > Hi, > > I'm a beginner with JTS and this is my first post here. > > We've been working with geofences for a vehicle tracking app > and I would like to know what solution could give me a lower > CPU consumption. > > 1) Calculate and store a Buffered Area (100 meters) from a > LineString object. Run 4 million times if my vehicle > positions are inside or not that precalculated with > contains() method. > > 2) Run 4 million times isWithinDistance() method from > LineString for each position. > > Are there another options? > > Thanks. > > > ------------------------------------------------------------------------------ > Introducing Performance Central, a new site from SourceForge and > AppDynamics. Performance Central is your source for news, > insights, > analysis and resources for efficient Application Performance > Management. > Visit us today! > > http://pubads.g.doubleclick.net/gampad/clk?id=48897511&iu=/4140/ostg.clktrk > _______________________________________________ > Jts-topo-suite-user mailing list > [email protected] > <mailto:[email protected]> > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > > > ------------------------------------------------------------------------------ > Introducing Performance Central, a new site from SourceForge and > AppDynamics. Performance Central is your source for news, insights, > analysis and resources for efficient Application Performance > Management. > Visit us today! > > http://pubads.g.doubleclick.net/gampad/clk?id=48897511&iu=/4140/ostg.clktrk > _______________________________________________ > Jts-topo-suite-user mailing list > [email protected] > <mailto:[email protected]> > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > > > > ------------------------------------------------------------------------------ > Learn the latest--Visual Studio 2012, SharePoint 2013, SQL 2012, more! > Discover the easy way to master current and previous Microsoft technologies > and advance your career. Get an incredible 1,500+ hours of step-by-step > tutorial videos with LearnDevNow. Subscribe today and save! > http://pubads.g.doubleclick.net/gampad/clk?id=58040911&iu=/4140/ostg.clktrk > > > > _______________________________________________ > Jts-topo-suite-user mailing list > [email protected] > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > ------------------------------------------------------------------------------ Learn the latest--Visual Studio 2012, SharePoint 2013, SQL 2012, more! Discover the easy way to master current and previous Microsoft technologies and advance your career. Get an incredible 1,500+ hours of step-by-step tutorial videos with LearnDevNow. Subscribe today and save! http://pubads.g.doubleclick.net/gampad/clk?id=58040911&iu=/4140/ostg.clktrk _______________________________________________ Jts-topo-suite-user mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
