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]>
>
> 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]>
>
>> 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]> 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]
>>> 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]
>> 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
