Using Range Querying to Filter LineString Segments

There are many types of ranged values used to describe business objects.

Here are a few:

  • Date Range: Date valid from and date valid to. This may describe the date an object was first made available to date on which it was retired.
  • Numeric Range: An example in the GIS world is the range of numeric value associated with a measured linear geometry; another the range of temperatures recorded at a weather station.

In these situations, as in others like it, a common query is to find values with a specific range.

For example:

“Find me the business objects that were in operation between 1st January 2017 to 30th June 2017”.
“Find me the road segment whose measures fall within a certain range”.

In all cases, the query approach is the same. The predicate that will do all out “heavy lifting” in all ranged data applications is:

 WHERE Greatest(f.date_from, f.query_date_from) < Least(f.date_to, f.query_date_to);

This predicate will find data that has an overlap of actual data ranges. If one wants to return ranges that have an end/start (query windows touches start at its end) or start /end (query window touches end at its start), one simply uses less than or equal:

Filtering linestring segments as in the roads example above is easier than you think.

I will say little about the following example, but it is a powerful reminder that generic IT processing concepts can be applied to spatial data: one does not need a GIS to implement this sort of processing, but it helps with the visualisation.

In the following we use the complete length of the linestring and the component lengths of its segments to execute our querying. First off I break the linestring into its components. Then I fabricate “measures” using the cumulative length fro the start of the linestring to generate lo and hi measure values. I then generate 10 ranges using the original linestring, query the segments and then classify the relationships.

(I do the processing here using SQL Server Spatial. SQL Server does not have a GREATEST/LEAST operators so the predicate is coded using case statements. The concepts can be implemented in any of the spatial databases.)


uWITH data as (
select geometry::STGeomFromText('LINESTRING(-1 -1,0 1, 2 2, 5 4,9 1)',0) as line
), segments_with_range AS (
SELECT segment_id, 
       ROUND(COALESCE(LAG(f.length_hi,1) over (order by segment_id),0),4) as length_lo,
       ROUND(f.length_hi,4) as length_hi,
  FROM (SELECT segment_id,
               gs.geom as segment,
               SUM(gs.geom.STLength()) over (order by as length_hi
          FROM data as a
               cross apply
               [dbo].[STSegmentize](a.line) as gs
       ) as f
) -- select * from segments_with_range;
,  range_query_data as (
select row_number()  over (order by (SELECT 1)) as range_id,
       ROUND(g.lo_range,4) as lo_range,
       ROUND(g.lo_range + dbo.STRandomBetween(0,g.lLength) ,4) as hi_range
  from (select dbo.STRandomBetween(-1,d.line.STLength()+1) as lo_range,
               d.line.STLength() as lLength
          from data as d
               cross apply
               dbo.Generate_Series(1,10,1) as range
       ) as g
) -- select * from range_query_data;
SELECT segment_id, range_id,
       CASE WHEN length_lo  = lo_range and length_hi = hi_range THEN 'EQUAL'
            WHEN lo_range > length_lo  and hi_range < length_hi THEN 'INSIDE'
            WHEN hi_range < length_lo  and lo_range > length_hi THEN 'DISJOINT'
            WHEN lo_range = length_lo THEN 'LEFT_START_TOUCH'
            WHEN hi_range = length_hi THEN 'RIGHT_END_TOUCH'
            WHEN lo_range = length_hi THEN 'LEFT_TOUCH_END'
            WHEN hi_range = length_lo THEN 'RIGHT_TOUCH_START'
            WHEN lo_range < length_lo and hi_range > length_hi THEN 'CONTAINS'
            WHEN lo_range < length_hi and hi_range > length_hi 
              OR lo_range < length_lo and hi_range > length_lo 
            THEN 'COVERS'
            ELSE 'UNKNOWN'
             END AS Description,
            swd.segment.STAsText() as segment
       FROM range_query_data as rqd,
            segments_with_range as swd
       WHERE case when swd.length_lo > rqd.lo_range then swd.length_lo else rqd.lo_range  end
             case when swd.length_hi < rqd.hi_range then swd.length_hi else rqd.hi_range end;
13COVERS00.205811.18272.2361LINESTRING (-1 -1, 0 1)
15COVERS01.77143.97042.2361LINESTRING (-1 -1, 0 1)
17COVERS01.996413.9932.2361LINESTRING (-1 -1, 0 1)
21CONTAINS2.23611.942513.00864.4721LINESTRING (0 1, 2 2)
25COVERS2.23611.26243.87254.4721LINESTRING (0 1, 2 2)
31CONTAINS4.47214.440514.16948.0777LINESTRING (2 2, 5 4)
33COVERS4.47214.917113.6118.0777LINESTRING (2 2, 5 4)
37INSIDE4.47214.61137.23098.0777LINESTRING (2 2, 5 4)
38COVERS4.47217.91619.56318.0777LINESTRING (2 2, 5 4)
39COVERS4.47216.231710.64258.0777LINESTRING (2 2, 5 4)
310INSIDE4.47214.936.22768.0777LINESTRING (2 2, 5 4)
42COVERS8.077712.458518.94913.0777LINESTRING (5 4, 9 1)
43COVERS8.07779.504320.190913.0777LINESTRING (5 4, 9 1)
44CONTAINS8.07777.355416.941813.0777LINESTRING (5 4, 9 1)
45CONTAINS8.07773.777214.573613.0777LINESTRING (5 4, 9 1)
46COVERS8.07779.221414.231513.0777LINESTRING (5 4, 9 1)
47COVERS8.07772.076510.841313.0777LINESTRING (5 4, 9 1)
48COVERS8.07775.59829.730413.0777LINESTRING (5 4, 9 1)
49CONTAINS8.07772.766413.150813.0777LINESTRING (5 4, 9 1)
410COVERS8.0777-0.30489.161713.0777LINESTRING (5 4, 9 1)

This sort of processing is embedded in my TSQL code, in particular the STSegmentize() function.

I hope this is of interest to someone.

Leave a Reply

Your email address will not be published. Required fields are marked *