Research client side draggable route selection with pgRouting
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 183 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/32147 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language | ||
| Producer | ||
| Production Year | 2015 | |
| Production Place | Seoul, South Korea |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Functional (mathematics)Revision controlComputer programmingCountingPattern languageRoutingCASE <Informatik>Shape (magazine)Limit (category theory)Software testingExecution unitDistanceMetreClient (computing)Point (geometry)ResultantInterface (computing)Menu (computing)Computer fontSampling (statistics)PurchasingBitForm (programming)AreaAdditionTerm (mathematics)MassMachine visionQuicksortLetterpress printingComputer animation
05:07
CASE <Informatik>Different (Kate Ryan album)XML
05:36
Error messageCASE <Informatik>Convex setStandard deviationSource codeParallel portMessage passing
06:42
MappingWeb pagePivot elementCASE <Informatik>Particle systemSparse matrixRootPosition operatorPoint (geometry)Process (computing)Block (periodic table)MereologyGoodness of fitReduction of orderVirtual machineTheoryFitness functionQuicksortMultiplication signGroup actionSoftware testingBootingDrag (physics)RoutingLine (geometry)ResultantSelectivity (electronic)Functional (mathematics)Modal logicDirection (geometry)Link (knot theory)Open sourceXML
10:44
FrequencyUltraviolet photoelectron spectroscopyGoodness of fitDrag (physics)Direction (geometry)RoutingEngineering drawingProgram flowchart
11:09
Social classProcess (computing)Virtual machineMIDIQuantumCellular automatonDirection (geometry)Source codeSoftware frameworkOpen source
11:51
Routing
12:14
Open sourceAreaDensity functional theoryMappingReference dataSummierbarkeitPoint (geometry)Medical imagingMereologyDistanceTheoryInterface (computing)InferenceMetreState of matterProcess (computing)Operator (mathematics)Front and back endsSoftware frameworkCausalitySource codeType theoryResultantTask (computing)Web pageVideoconferencingWebsiteError messageVirtual machineFamilyComputer programmingInheritance (object-oriented programming)Social classParameter (computer programming)Pulse (signal processing)Film editingFunctional (mathematics)Position operatorScalar fieldScaling (geometry)Demo (music)Wrapper (data mining)Level (video gaming)Total S.A.RootObject (grammar)Travelling salesman problemGeometryoutputSystem callWell-formed formulaView (database)Dependent and independent variablesClient (computing)Message passingDebuggerServer (computing)Router (computing)CASE <Informatik>SoftwareProjective plane
18:23
Form (programming)PlanningRouting
18:49
Software testingQuantum gravityContent (media)Plug-in (computing)ImplementationVirtual machineMultiplication signLogicServer (computing)Vector spaceClient (computing)Statistical hypothesis testingBitAdditionExtension (kinesiology)XMLUML
20:29
Computer animation
Transcript: English(auto-generated)
00:04
Thank you. I am also QGIS PG routing layer programming contributor. My known contribution about PG routing layer is supporting PG routing version 2.0 functions.
00:24
And currently, I am supporting PG routing 2.1 functions. And I think I will be finish it soon.
00:41
So I will show what PG routing the programming is. A PG routing layer can call from a PG routing,
01:00
PG routing function from QGIS interface. So example, this font is a bit small, but you can select a PG routing function from menu.
01:22
And for example, if I use Dijkstra, then select start and end point, then done. Oh, sorry.
01:44
Then done. Then you can easily, you can get result of PG routing easily. Also, I implemented some other functions,
02:05
like driving distance. This red point is distance 0.02. This unit is the degree,
02:22
but it can be possible to change meters if the original data is, data units is meter. And also support the alpha shape. So I think it's the easiest way
02:42
to get result from PG routing with visual. Okay, to describe this research's background.
03:02
A few months ago, there was a specific PG routing use case in our company. The client requests all possible routes, and a long-trip case, a go-on-back case,
03:21
and a parallel edges case. At first, I thought K-show test pass, which is already implemented in PG routing, can do it, but there are some limitations.
03:44
So it is necessary to use dual-couple routing. And at first requirements, all the possible routes,
04:03
it is known as a self-appointing work. So at first, start and end point, if one grid, then there is two route. But if it becomes two by two grid,
04:24
then it combinate, its pattern count becomes 12. And it becomes 12, 184, then 8,500, 12.
04:42
It easily become bigger, and it easily cause combinatorial explosion. If you like, you can see this funny YouTube movie.
05:18
So there is a funny Japanese animation,
05:23
which describe combinatorial explosion. But I'll stop this now. And also, there is a long-trip case requirement.
05:48
So start to end this route, it includes go there and go and back, then continue.
06:03
And also, go and go, and back and back case. So the combinatorial explosion becomes worse. And other issues is same source target parallel edges case.
06:26
This is a pre-routing old issue. And recent discussion is here. So you can check long pre-routing issue.
06:41
And at first, I thought that case shortest pass can be used, but case B returns first, second,
07:01
and case shortest is alternative routes. And case B is not for all possible routes. Also, case B, not only case B, but also every
07:20
pre-routing function doesn't support down-trip case, go and back case. And to support parallel edges case, post-processing becomes necessary.
07:45
That is why I want to, I have to, had to use draggable routing. In case draggable routing, first select start and end
08:04
point, then first result is red line here. Then select edge point two and drag here. Then route becomes this line.
08:22
And also, this point drag to here, then final route becomes here. And about processing, just do, just route start point to one, then one, two, two.
08:48
And last, two to end. So processing becomes easy, really easy. And in this case, supporting long-trip case is possible.
09:01
For example, in this case, these two drag to here, then the route becomes like this. So long-trip support, long-trip case support is become easy.
09:21
And last, to support parallel edges case, edge-based routing is necessary. And pre-routing has one PGL-TRSP, turn restrict shortest pass function. And it support edge-based routing.
09:47
So I started to research existing draggable routing frameworks. First, probably Google Maps Reactions API
10:00
is the famous one. And in open source world, open source routing machine, OSRM is probably a famous one. And last, deflate routing machine, short name, Abraham, is the new one. But I think that it is good.
10:26
For each frameworks, Google Maps directions, about Google Maps directions API, link and documentation is here. And for example, example is here.
10:51
And in Google Maps directions API, you can drag route like this.
11:12
And the plus of Google Maps directions API is it is a most well-known framework. But this is a closed source.
11:24
And if I use, if I want to, if I want to use as commercial, then getting a license is necessary.
11:42
And second, open source routing machine, it is famous, also a bit small, but it also like draggable routing.
12:16
And plus, it is a very well-known framework in open source
12:22
and also, yes, it is open source. But a consequence is about back end license was changed from strict AGPL, a fellow GP license to meet license. But about front end, front end client side,
12:41
the license is still restricted to a fellow AGPL. So I researched another one, different routing machine, short name LRM. Project and source code is here.
13:02
And plus, it's open source. And license is not strict. ISG, it's like, it is almost like a meet license. And several routing engines support
13:20
built-in OSRM and GraphFropper, Mapbox Deactions API, and Mapzen Valhalla. And cons is only, pg routing with own network data can be used. So I tried to create this different
13:42
routing machine, pg routing plugin. I will describe quick runs at LRM plugin interface and server-side design, and client-side processing, and show demo.
14:05
The tutorial, using other router tutorials is here. And it just request waypoints. These waypoints to a server via LRM iRouter interface, a root method.
14:22
Probably we want maybe a bit small, but just like array, coordinate array. And after that, get response from server, from the server,
14:40
and pass the results, then format and pass it to LRM iRouter interface object. I root, i root means like these waypoints. Waypoints is a snapped one, and root coordinates, and summary, cost and distance,
15:00
and time, total time, and instructions. After that, LRM then done waypoints and coordinates in a map and show summary and instructions in a panel, this panel.
15:22
About server-side design, to make it simple, I decided to use GeoServer WFS layer with a scale view, and the PLPG scale wrapper function. PLPG scale wrapper function passes input waypoints,
15:42
then call a PGLTSP function for each waypoints. So, start to run, and run to end. GeoServer, but the problem is GeoServer doesn't support multi-proved geometry common layer,
16:02
because the result is not only root coordinates, root-line coordinates, but also waypoints, snapped waypoints. So, I designed that PLPG scale returns a merged TSP result
16:21
which is with a point type attribute. It's like flag, one, two, four, eight, and its meaning. So, it can be used in an operator.
16:41
And about PLPG scale wrapper function, the formula is like this one. And past waypoints take its at first, then find each waypoint's nearest edge, and position in the edge, and a snapped point.
17:03
Then, call PLPG and TSP function for each waypoints. After credit, PLPG scale wrapper function, then call it from GeoServer scale view setting.
17:27
And about client-side processing, the case waypoints as view points evaluated to the GeoServer WFS layer.
17:43
Then, create WFS request from parameter. And after get response from GeoServer WFS layer, then pass it and generate a root object.
18:09
So, and finally, result root and waypoints rendered in a map, and result summary and instructions displayed in a panel. So, I will show a demo.
18:29
Like this one, this one. So, I could, I could done drag-up routing.
18:51
So, about future plans, there is some topics remained. One is more simple creation and test.
19:02
Current implementation depends on OSM2PO, so converting edge-stable schema. So, more generalization is necessary. And currently, instructions contents is built at the client-side, but moving its logic to server PLPG scale-side may be better. And also, currently tested it only with small data set,
19:23
so testing it with larger data set become necessary. And in my abstract, I wrote about OLS3 extension, but I had no time to do this.
19:43
But I think it is possible. Like, OLS3 routing machine ORM. Also, I think it is possible to apply QG's Python plugin. Okay, thank you.
20:22
Okay, if there are no questions, we'll move on to our second presenter. Thank you.