Even better would be a routine that removes the "crazy" line segments, so
at least the rest of the geometry (which is most of it) can be processed.
I haven't worked this out in detail, but I think this could be done with a
sort of "moving window lag filter". This would be based on the envelope
(or perhaps radius) of the last N segments, and would start discarding
intermediate segments if the next segment didn't move outside the window.
On Wed, Jan 21, 2015 at 11:36 AM, Martin Davis <[email protected]> wrote:
> Yes, the excessive memory usage in LineString#intersects() is due to the
> large number of self-intersections.
>
> What you're looking for is a filter that will identify cases like this and
> allow them to be discarded or handled specially. It's usually a bit tricky
> determining such a filter, to make it have the right selectivity, and also
> to perform fast enough (since it will be run on every single input case).
>
> In this case the most obvious thing to do is to compute the total count of
> self-intersections (without computing the actual intersection points) and
> compare the number to the total number of segments. (Or even just set a
> limit to the number of self-intersections which can be handled, since this
> is directly correlated to the amount of memory required.
>
> This requires some special-purpose coding using the JTS noding package. A
> SegmentIntersector class needs to be created which only counts nodes, and
> does not store them. This is then run using the MCIndexNoder class.
>
> In fact, I just commited code to do exactly this:
> https://sourceforge.net/p/jts-topo-suite/code/950/
>
> (The counting code is added to the InteriorIntersectionFinder class, and
> the NodingFunctions.nodeCount function shows how to use it.)
>
> The good news is that it runs very fast, so should be fine to use as a
> pre-intersection filter. As an example, on the "crazy" linestring it runs
> in 630 ms and reports 949135 intersections. This is almost the square of
> the number of input segments, which is clearly indicating an anomaly.
>
>
> On Wed, Jan 21, 2015 at 10:53 AM, Jan Torben Heuer <[email protected]>
> wrote:
>
>> Hi Martin,
>>
>>
>> Thanks for the answer, yes, I should have mentioned that the LineString
>> is ‚crazy‘. "It works with PreparedGeometry“ means that the result can be
>> computed very quickly and without memory problems (see original test case).
>>
>>
>> So the reason why LineString#intersect() does not work here are the tons
>> of self-intersections? The data set is from a GPS device and I have a
>> couple of LineStrings like that. I suspect most geometry methods won’t work
>> here (buffer for instance). Do you have a recommendation how to deal with
>> this data? I’d be fine with dropping the data if that is easily possible.
>> Would you recommend to calculate the number of self-intersections before
>> and set a limit?
>>
>> So yes, the precise answer is of interest but I can live with dropping a
>> small percentage of „crazy“ data.
>>
>>
>>
>>
------------------------------------------------------------------------------
New Year. New Location. New Benefits. New Data Center in Ashburn, VA.
GigeNET is offering a free month of service with a new server in Ashburn.
Choose from 2 high performing configs, both with 100TB of bandwidth.
Higher redundancy.Lower latency.Increased capacity.Completely compliant.
http://p.sf.net/sfu/gigenet
_______________________________________________
Jts-topo-suite-user mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user
