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
