[OSM-dev] Determining if two linestrings are "similar"

[Paweł Paprota]

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ł