[postgis-users] Intersection testing with one-to-many relationships
Tom Payne
tom at tompayne.org
Sun Jan 13 15:42:37 PST 2013
Hi Nicolas,
Just to follow up on this, your solution works exceptionally well in
practice. I'll denormalize my schema to squeeze out a little more
performance (e.g. by storing the number of turnpoints per task, rather than
having PG calculate it in a CTE), but I'm seriously impressed by PostGIS's
capabilities.
Thanks again for the fast and excellent response,
Tom
P.S. For anybody who is interested, I'm using Python, with SQLAlchemy and
GeoAlchemy2. Nicolas's query looks like this (before denomalization):
@classmethod
def all_pairs(cls):
task_turnpoints = db.session.query(
Task.id.label('task_id'),
db.func.count(Turnpoint.id).label('count')
) \
.filter(Task.id == Turnpoint.task_id) \
.group_by(Task.id) \
.order_by(Task.id) \
.cte(name='task_turnpoints')
flight_turnpoint_intersections = db.session.query(
Task.id.label('task_id'),
Flight.id.label('flight_id'),
db.func.count(Turnpoint.id).label('count')
) \
.filter(Task.id == Turnpoint.task_id) \
.filter(db.func.ST_intersects(Flight.geom, Turnpoint.geom)) \
.group_by(Task.id, Flight.id) \
.cte(name='flight_turnpoint_intersections')
query = db.session.query(
Task.id.label('task_id'),
Flight.id.label('flight_id')
) \
.filter(Task.id == task_turnpoints.c.task_id) \
.filter(Task.id == flight_turnpoint_intersections.c.task_id) \
.filter(Flight.id ==
flight_turnpoint_intersections.c.flight_id) \
.filter(flight_turnpoint_intersections.c.count ==
task_turnpoints.c.count) \
.group_by(Task.id, Flight.id) \
.order_by(Task.id, Flight.id)
return set((task_id, flight_id) for task_id, flight_id in query)
On 24 December 2012 16:50, Nicolas Ribot <nicolas.ribot at gmail.com> wrote:
> :) Merci.
>
> Bonnes fetes à vous aussi !
>
> (by the way, quite challenging to also answer the question in one SQL
> query: are the turnpoints visited in the right order...)
>
> Nicolas
>
>
> On 24 December 2012 16:48, Tom Payne <tom at tompayne.org> wrote:
>
>> That's awesome Nicolas.
>>
>> Many thanks and bonnes fêtes !
>>
>> Tom
>>
>>
>> On 24 December 2012 15:30, Nicolas Ribot <nicolas.ribot at gmail.com> wrote:
>>
>>> (with proper indices, I'm confident this kind of query would be fast
>>> enough for your target size)
>>>
>>>
>>> On 24 December 2012 15:29, Nicolas Ribot <nicolas.ribot at gmail.com>wrote:
>>>
>>>> Hi,
>>>>
>>>> There must be a simpler solution than the one provided, but can't see
>>>> it right now.
>>>> Maybe using windows functions...
>>>>
>>>> Anyway...:
>>>> Your 2 questions are the same: for the first one, you will add a WHERE
>>>> clause defining the task id you want results for.
>>>>
>>>> The following query is using Common Table Expression (CTE) with WITH
>>>> construct, easier to read and write than subqueries.
>>>> The first "tasks" query just gives the number of turnpoints per task.
>>>> It will be used to filter out flights that do not intersect ALL turnpoints
>>>> for a task.
>>>> The second "inter" query performs the actual intersection and count the
>>>> number of intersected turnpoints for a flight-task pair
>>>> Finally, the outer query makes a join between the 2 first CTE tables
>>>> and filters rows to keep only flights intersecting ALL turnpoints.
>>>>
>>>> with tasks as (
>>>> select t.id, count(tu.id) as num_turnpoint
>>>> from task t, turnpoint tu
>>>> where t.id = tu.task_id
>>>> group by t.id
>>>> order by t.id
>>>> ), inter as (
>>>> select t.id as taskid, f.id as flightid, count(p.id) as cnt
>>>> from tasks t, flight f, turnpoint p
>>>> where t.id = p.task_id
>>>> and st_intersects(f.geometry, p.geometry)
>>>> group by t.id, f.id
>>>> ) select i.*
>>>> from inter i, tasks t
>>>> where i.cnt = t.num_turnpoint
>>>> and t.id = i.taskid;
>>>>
>>>> Nicolas
>>>>
>>>>
>>>> On 24 December 2012 13:17, Tom Payne <twpayne at gmail.com> wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>>
>>>>> tl;dr How to select rows that intersect _all_ geometries defined in a
>>>>> one-to-many relationship?
>>>>>
>>>>>
>>>>> I'm using PostGIS as the core of a new system for scoring paragliding
>>>>> competitions. In such a competition, a task is defined by sequence of
>>>>> turnpoints (polygons) that must be visited in order. The pilot submits a
>>>>> GPS trace (linestring) as evidence. I'm trying to write a PostGIS query
>>>>> that returns all GPS traces that intersect all turnpoints in a given task.
>>>>> I've spent time Googling, but this is beyond my current PostGIS/SQL
>>>>> abilities.
>>>>>
>>>>>
>>>>> My schema looks like:
>>>>>
>>>>> -- a task has many turnpoints
>>>>> CREATE TABLE task (
>>>>> id INTEGER NOT NULL,
>>>>> PRIMARY KEY (id)
>>>>> );
>>>>>
>>>>> -- a turnpoint belongs to a task and has a geometry
>>>>> CREATE TABLE turnpoint (
>>>>> id INTEGER NOT NULL,
>>>>> task_id INTEGER,
>>>>> seq INTEGER NOT NULL, -- index within its task
>>>>> geom geometry(POLYGON,-1) NOT NULL,
>>>>> PRIMARY KEY (id),
>>>>> UNIQUE (task_id, seq),
>>>>> FOREIGN KEY(task_id) REFERENCES task (id)
>>>>> );
>>>>>
>>>>> -- a flight has a geometry
>>>>> CREATE TABLE flight (
>>>>> id INTEGER NOT NULL,
>>>>> geom geometry(LINESTRING,-1) NOT NULL,
>>>>> PRIMARY KEY (id)
>>>>> );
>>>>>
>>>>>
>>>>> What I want is:
>>>>>
>>>>> (1) for a given task, return all flight.ids that intersect all of that
>>>>> task's turnpoints' geoms; intersection tests can be approximate
>>>>> (i.e.intersecting with && is sufficient)
>>>>>
>>>>> (2) a list of (task.id, flight.id) pairs where the flight's geom
>>>>> intersects all of the task's turnpoints' geoms (intersecting with && is
>>>>> sufficient)
>>>>>
>>>>>
>>>>> I'm a bit stuck on how to achieve the above. If I use ST_Collect to
>>>>> combine all the turnpoints of a single task, and then do the intersection
>>>>> test with ST_Intersects then I'll select all flights that intersect ANY of
>>>>> the task's turnpoints; not all flights that intersect ALL of the task's
>>>>> turnpoints.
>>>>>
>>>>> If it is necessary to change the schema (e.g. to represent a task's
>>>>> turnpoints as an array of geometries rather than a one-to-many
>>>>> relationship) then that's fine.
>>>>>
>>>>>
>>>>> Many thanks for any help or pointers on how to achieve this with
>>>>> PostGIS.
>>>>>
>>>>> Tom
>>>>>
>>>>>
>>>>>
>>>>> P.S. Background information, probably not relevant to question:
>>>>> - I'd like to use the queries above as an initial filter, the precise
>>>>> intersection tests and the checks that the turnpoints are visited in the
>>>>> correct order is done in my application
>>>>> - Each task typically has 2-5 turnpoints
>>>>> - The database will eventually contain thousands of tasks and tens of
>>>>> thousands of flights, I plan to make it possible to do query (2) above
>>>>> incrementally
>>>>>
>>>>> _______________________________________________
>>>>> postgis-users mailing list
>>>>> postgis-users at lists.osgeo.org
>>>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>>>>
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> postgis-users mailing list
>>> postgis-users at lists.osgeo.org
>>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>>
>>>
>>
>> _______________________________________________
>> postgis-users mailing list
>> postgis-users at lists.osgeo.org
>> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>>
>>
>
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20130114/d1c665f4/attachment.html>
More information about the postgis-users
mailing list