[Qgis-developer] FW: Geometric Network Analysis Tools

[Petros Apotsos]

Dear List,

After doing some extensive search on Geometric Network Analysis (GNA) FOSS
Tools and software, I can say that I stand a bit confused. Not so much about
what I am capable of doing, but more so about what is the best way to do it.

To start, I am posting my latest Q&A to the list:

Hello,

 

> Given a Point Cloud (either a file or a stream) that represents 

> positions, speed and direction of a vehicle fleet (TAXIs in my case), 

> and a graph (geometric network) that represents roads and 

> intersections, I want to be able to do the following:

 

Your problem will probably be best answered through PostGIS queries, which
you can then visualize with QGIS, and/or a custom web-based application.

 

Let's say you have a table taxi_position like this, where position is a
point geometry :

 

| gid | taxi_id | speed | pos_time | position |

 

>     1. Track down the route of any single vehicle, as a succession of 

> points on the network.

 

Group by taxi_id, order by pos_time and make a line with the resulting
points.

 

>     2. Calculate the total passes of vehicles through any given point or 

> segment of the network.

 

Join your segment (or node) network with your taxi_position table, allowing
a tolerance around the segment/node (st_dwithin will do the trick), then
group by taxi if you want to consider each vehicle only once.

 

>     3. (Not as urgent as the above) Find the nearest TAXI to a random 

> point on the network.

 

With PostGIS > 2.0, use KNN-search to do it fast as light. Otherwise, use
st_dwithin with growing values for the search radius.

 

> All of the above need to be FOSS-based solutions.

check.

 

> Although I am willing and ready to program plugins or algorithms to do 

> the above tasks, I am not really into re-inventing the wheel, so my 

> questions are the following:

>     A) Are there any libraries or plugins that handle the above tasks?

> Is there any FOSS work already done with them?

 

That would be a few SQL queries then.

 

>     B) Is QGIS ready (aka efficient enough) to handle those tasks, or 

> shall we try other tools/software?

Use QGIS as visualization tool, and PostGIS as a backend, and you're set for
hundreds of millions of positions without problem (well, do not visualize
everything at once).

 

> Any opinions on my task would be greatly appreciated!

You're welcome

 

Vincent

 

> Thanx in advance!

> 

> Petros Apotsos

 

The above answers cover most of my questions, but trying to be more specific
to my task, which includes network attribute callibration, it is essential
that I get a better knowledge and understanding of the following concepts
that I need for my work to be considered excellent:

1) Geometry extraction: Given a random point (either vehicle signal node or
checkpoint), I want to be able to connect it to the network, but only after
doing some tests, like proximity ("What is the distance of the point from
the nearest edge?") and direction ("Is the orientation of the vehicle's
movement compatible with the orientation of the network edge I am trying to
connect to?" - this only applies to vehicle signals). So the questions that
arise are:

- How exactly are new points/nodes, which generally don't belong to one of
the edges, connected to the network?

- After they are connected, can we somehow (eg. with a query or
programmatically) get the geometry of the edge at the specific point where
the connection actually happens (coordinates of the point and tangent
direction of the edge at the specific point could do the trick)?

2) New point (temporary) connection: In QGIS's Network Analysis Library it
is possible to "tie"/"connect" new nodes to the graph/geometric network.
What is exactly (or even approximately) the mechanism, under which this is
done? How do other GNA libraries handle this? I am trying to figure this out
in relation to the analysis I am trying to do (and which is explained
above).

3)A short list of what I am trying to do: The program I am trying to design
should be able to do the following, given a stream of vehicle signals and a
geometric network of the roads of a city:

                - Read a new vehicle signal. Decide if it is "legitimate",
then "assign" it to the network ("Assign" = Determine a point on a network
edge, where the vehicle most probably is moving - "Legitimate" = Signal that
contains correct position information and complete information on the rest
of the attributes of the vehicle's movement (speed, direction, Vehicle ID
etc.)

                - Log the above information as persistent data, that can be
retrieved eg. using SQL.

                - Calculate, log and visualize the movement of each vehicle.
This could be done eg. by successive routing between "assigned" signals of a
particular vehicle.

                - Given a point on the network (either original node or a
"new" node on an edge) determine if the route of the taxi passes through
this point.

I know this is a lot, and maybe I am posting in the wrong direction, but I
think this can benefit all of the GIS community. If some work has already be
done on the above issues (which I am sure it has), I would like to know in
what direction to search (eg. I am sure trivial car navigator software
covers the first issue from 3). If not, I am willing to do the relevant work
and research, but as I state above, I don't need to reinvent the wheel, and
thus I need some starting points.

If all goes well, I hope I will be able to publish a relevant toolbox/plugin
to share with the community.

Always at your disposal and thank you in advance,

 

Petros Apotsos

 

Rural & Surveying Engineer

Technical Chamber of Greece Registry Number 96798

Τ: 2310 220345

F: 2310 220346

Ermou 18A, Postal Code 54624

Thessaloniki, GREECE

 

PS: I am always open to discussions and/or prospective cooperations. Feel
free to drop me a line, though I think the list is the best place for
technical discussions.

PPS: Through my research I have come to the conclusion, thought it might
only be a personal conception of the state of the art, that although many
FOSS tools handle the concept of network analysis, they mostly focus on the
graph analysis part, and neglect the geometry part. Do you feel this is so
or do you think I am missing something? I am sure the building parts are all
out there, but some engineering work has to be done to bind them all
together. I will do (among others) some research and modeling work and will
let you know if and when I come to any conclusions.

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/qgis-developer/attachments/20130207/f8058fa4/attachment-0001.html>