[OSM-dev] Determining if two linestrings are "similar"
Paweł Paprota
ppawel at fastmail.fm
Fri Jan 4 14:38:15 GMT 2013
Hi Jochen,
On 01/04/2013 02:50 PM, Jochen Topf wrote:
>
> You can create a buffer (with ST_Buffer) around one geometry and then see
> whether the other geometry is inside this buffer or not. Unfortunately that
> is a rather expensive operation, so it might be too slow for your use.
>
Yeah, Kompza on IRC suggested a similar solution with ST_Buffer. I will
try that.
I came up with something else:
st_equals(
st_snaptogrid(st_segmentize($1, 0.00002), 0.0002),
st_snaptogrid(st_segmentize($2, 0.00002), 0.0002)
);
Unfortunately this is slow for long linestrings, perhaps even slower
than ST_Buffer.
> If the number of nodes in a way didn't change you could optimize by just
> comparing them coordinate by coordinate.
>
Yes, it's also easy to determine that they are NOT similar so that I can
jump out early from further processing.
>> I tried ST_HausdorffDistance[1] from PostGIS but for now it does not
>> yield useful results or maybe I am misinterpreting them.
>>
>> Any ideas?
>>
>> http://www.postgis.org/docs/ST_HausdorffDistance.html
>
> The documentation says "This is the Hausdorff distance restricted to discrete
> points for one of the geometries." I am not sure what the consequences of
> that are, but it might be too restrictive for your use.
>
Exactly, the most problematic cases are linestrings with different set
of nodes. That's why I had to add the expensive ST_Segmentize in my
solution above - to make snapping work.
I also found Frechet distance[1] which looks more interesting than
Hausdorff for my use but it's not implemented in GEOS/PostGIS and it
would probably need a similar operation to segmentization.
On the other hand, it was suggested on IRC that OWL should not really
filter out such non-changes and show everything. I'm trying to filter
them out to speed up processing, whether it makes sense to do it from
user perspective I don't know... I personally don't care too much about
ways that were simplified (without topology changes) or changed only
very slightly. Other opinions are welcome...
[1] http://www.cim.mcgill.ca/~stephane/cs507/Project.html
Paweł
More information about the dev
mailing list