[postgis-devel] [Fwd: Re: ST_Line_Substring]

[Martin Davis]

I've been working on a fast, cacheable distance computation for JTS.  I 
also thought of this approach of sorting the line segments along some 
line between the geometries.  It seems like it should work fine.

Another more general approach is to spatially index the facets of both 
geometries and use a branch-and-bound algorithm to find the shortest 
distance.  The latter has the advantage of (a) being cacheable for one 
of the geometries) and (b) being useful in the case where the geometries 
overlap.  That's the approach I've ended up pursuing, and it's certainly 
providing a dramatic performance increase.  It would require some real 
world testing to determine whether one is better than the other, I think.

Martin

Paul Ramsey wrote:
> Thanks Nicklas, that's a nice write-up. In future, remember to attach
> in open formats, like PDF or OpenOffice. And now that I see your
> implementation is a bolt-on enhancement ot distance calculations
> rather than a replacement I feel more comfortable with it. It seems
> like you could have some degenerate conditions if the bbox center is
> quite a ways outside the actual polygon boundary, though, have you
> tested that?
>
> Another approach to the problem would be to build an internal index of
> the edges of both polygons, then traverse that index. It would have
> the advantage of being cacheable and more general (works for all
> cases) but would probably not have nearly the real-world improvement
> your heuristic has.
>
> I'm interested to hear what a real geometer thinks of your approach, I
> wonder if Martin would comment?
>
> P.
>
> On Wed, Sep 9, 2009 at 1:32 PM, <nicklas.aven at jordogskog.no> wrote:
>   
>> thanks
>>
>> about the distance-calculations don't miss the dist.doc in ticket #231.
>> That might save you some time to see the idea behind the new
>> distance-calculation of polygons and linestrings that don't have
>> intersecting bounding boxes.
>>
>> /Nicklas
>>
>>
>>
>> 2009-09-09 Paul Ramsey wrote:
>>
>> Niklas,
>>     
>>> There are at least three different implementations of line substring
>>> hanging around, a couple that are bound to the old functions and one I
>>> did for the elevationbetween functions. The whole conjunction calls
>>> out for a cleaning and consolidation, frankly, but I've been leaving
>>> it alone on the basis of not touching things that are working.
>>>
>>> Attach your patch for 3D to a ticket so it doesn't get lost. I've got
>>> reviewing your distance ticket on my list too so don't give up hope on
>>> that.
>>>
>>> P.
>>>
>>> On Sun, Aug 30, 2009 at 1:17 PM, wrote:
>>>       
>>>> The function ST_Line_Substring is some mixture between 2D and 3D. It
>>>> preserves the z-value but don't use it in calculation. The documentation
>>>> describes this but the note that the function supports 3D I think is
>>>> false.
>>>>
>>>> Why not make it real 3D so it considers the third dimmension in the
>>>> calculation.
>>>>
>>>> Now this query:
>>>> select st_asewkt(ST_Line_Substring(the_geom,0.2, 0.8))
>>>>  from
>>>> (SELECT ST_GeomFromEWKT('SRID=4269;LINESTRING(1 1 1,1 1 3, 1 1 5, 1 1
>>>> 8)')
>>>> as the_geom ) a;
>>>> gives the little bit strange result:
>>>> "SRID=4269;LINESTRING(1 1 3,1 1 5)"
>>>>
>>>> I think t would be much better to make it fully 3D-supportive. Then the
>>>> result of this query is:
>>>> "SRID=4269;LINESTRING(1 1 2.4,1 1 3,1 1 5,1 1 6.6)"
>>>>
>>>> I have attached a patch that makes this.
>>>>
>>>> The reason I started to look at this was that I wanted a function that
>>>> takes
>>>> distances instead of fraction of the total length.
>>>> I hve a working finction that takes the startdistance and end-distance
>>>> from
>>>> the start of the line to pull out the substring-line. In some cases that
>>>> is
>>>> more straight on than going via the fractions. Should I post it or will
>>>> there be to many functions too little difference?
>>>> The question is if I should put effort in writing the documentation and
>>>> regression-tests.
>>>>
>>>> Greetings
>>>> Nicklas
>>>>
>>>> _______________________________________________
>>>> postgis-devel mailing list
>>>> postgis-devel at postgis.refractions.net
>>>> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>>>>
>>>>
>>>>         
>>> _______________________________________________
>>> postgis-devel mailing list
>>> postgis-devel at postgis.refractions.net
>>> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>>>
>>>
>>>       
>> _______________________________________________
>> postgis-devel mailing list
>> postgis-devel at postgis.refractions.net
>> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>>
>>
>>     
>
>   

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022




-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022