Thanks, Andre. As Stefan says, pretty clear which is faster.
Just to be precise, is the number of points the number in the input
linestring? For the contains methods you buffered the linestring by the
distance tolerance? How were the points distributed - randomly, or in a
more regular pattern?
On Mon, Sep 2, 2013 at 6:08 AM, André Salvati <[email protected]>wrote:
> 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
>
>
------------------------------------------------------------------------------
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
