Strange behaviour in pgr_withPoints

[denadai2]

Hello everybody, I'm using the proposed function pgr_withPoints, but it seems there is a bug

Expected behavior and actual behavior

The expected result is the one I obtain if I select all the point of interests "limiting" the results for example in this way:

select * from pgr_withPoints('SELECT gid as id, source, target, length_m as cost, length_m as reverse_cost, x1,y1,x2,y2 FROM ways', 'SELECT j.bid as pid, j.way_id as edge_id, j.fraction from join_building_ways j where bid in (13464281, 13464251, 13464250)', -13464281, -13464250);
 seq | path_seq |   node    | edge  |       cost       |     agg_cost     
-----+----------+-----------+-------+------------------+------------------
   1 |        1 | -13464281 | 85965 | 21.3940627565627 |                0
   2 |        2 |     75852 | 85957 | 9.67727907223116 | 21.3940627565627
   3 |        3 |     68330 | 85956 | 7.22238171772227 | 31.0713418287938
   4 |        4 |     71916 | 85955 | 7.18404585924898 | 38.2937235465161
   5 |        5 | -13464250 |    -1 |                0 | 45.4777694057651

If I do this:

select * from pgr_withPoints('SELECT gid as id, source, target, length_m as cost, length_m as reverse_cost, x1,y1,x2,y2 FROM ways', 'SELECT j.bid as pid, j.way_id as edge_id, j.fraction from join_building_ways j', -13464281, -13464250);
 seq | path_seq | node | edge | cost | agg_cost 
-----+----------+------+------+------+----------
(0 rows)

I have no results. Why?

Steps to reproduce the problem

create a db with this backup.
https://www.dropbox.com/s/p9pq9dh2zz1yfir/bug2.sql.zip?dl=0

Specifications like the version of pgRouting/PostGIS and PostgreSQL as well as Operating System

---

PostgreSQL 9.6.1 on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4, 64-bit

POSTGIS="2.3.0 r15146" GEOS="3.5.0-CAPI-1.9.0 r4084" PROJ="Rel. 4.9.2, 08 September 2015" GDAL="GDAL 1.11.3, released 2015/09/16" LIBXML="2.9.1" RASTER

(2.3.2,v2.3.2,1f2af3c52,master,1.54.0)

[cvvergara]

Hello,
I downloaded your data.

There is this issue that it has with the "fraction", 0, 1 are whole numbers they are not fractions.
You see, what the withPoints do before processing the dijkstra algorithm it modifies the graph.

From what I can see from here there is more that one problem here:

1. There is no message that informs the user that a 0 or 1 as a faction was given in a point.
2. There is no official documentation on the way around.
3. I've being thinking on how to solve this issue since I first coded them, team has discussed, and It will stay proposed until this issue is fixed.

So, first I am going to talk about how it works, when there is a problem, why it is a problem, and the user's way around to avoid the problem.

how it works

To simplify I am going to talk about undirected graph, So say there is this graph:

     |                         |                         |
-----A-------85955-------------B-------85956-------------C
     |                         |                         |

A is connected to 4 vertices (can be more can be less) one of them happens to be B, B is connected to 4 vertices one of them happens to be A the other C (etc)
you want to route from P , so P is one of the entries in the Points table (join_building_ways) say that P is

   pid    | edge_id |     fraction      
----------+---------+-------------------
 13464251 |   85955 | 0.742538045332056

     |                         |                         |
-----A-------85955-----P--------B-------85956-------------C
     |                         |                         |

And its the graph it uses.

The problem is when:

For this graph

     |                         |                         |
-----A-------85955-------------B-------85956-------------C
     |                         |                         |

and P is like:

   pid    | edge_id |     fraction      
----------+---------+-------------------
 13464250 |   85956 |                 0

which means that actually P is not a point outside the graph, it is B (vertex 71916 in your data)

Suppose it does the same thing:

     |                         |                         |
-----A-------85955-------------P-------85956-------------C
     |                         |                         |

So S gets re-ided to have the -13464250 as id.

Why is it a problem:

Imagine that there is also a Q point

   pid    | edge_id |     fraction      
----------+---------+-------------------
 99999    |   85955 |                 1

As first glance, the point Q looks quite different as of P, its in a different edge, instead of 0 is 1
its the same vertex B

     |                         |                         |
-----A-------85955-------------B-------85956-------------C
     |                         |                         |

So B, shall I it be re-ided as P, as Q?

Actually the Points are new vertices outside the vertex set, but P & Q are B

In general:

• points can not have the same fraction on the same edge (not your case)
• you have to detect if it is really a point outside the graph or is it already on the graph

way around:

buildings wont move, the streets don't move, lets keep the data in a table instead of recalculating the st_linelocatepoint, that is to avoid overhead, when loading the graph to the function, so in the building table add the edge_id and the fraction, btw, also add a vertex_id if you use way around 1. is more complex but its my favourite

way around 1:

explanaation and demo in: (other data)
http://gis.stackexchange.com/questions/216273/using-pgr-withpointscost-from-pgrouting-2-2-2/218233#218233

(I might as well put that in the wiki, but I am busy with the 2.4 release)

way around 2

works on your data, because there are no 2 buildings that share the same vertex, otherwise you would need to make the fractions different.

• instead of 0 use a slightly larger 0
• instead of 1 use a slightly smaller 1

demo using your data:

SELECT * into building_points FROM join_building_ways ;

UPDATE building_points SET fraction = 0.00001 where fraction = 0;
UPDATE building_points SET fraction = 0.999999 where fraction = 1;

your first query

select * from pgr_withPoints('SELECT gid as id, source, target, length_m as cost, length_m as reverse_cost, x1,y1,x2,y2 FROM ways', 'SELECT j.bid as pid, j.way_id as edge_id, j.fraction from building_points j where bid in (13464281, 13464251, 13464250)', -13464281, -13464250);
 seq | path_seq |   node    | edge  |       cost       |     agg_cost     
-----+----------+-----------+-------+------------------+------------------
   1 |        1 | -13464281 | 85965 | 21.3940627565627 |                0
   2 |        2 |     75852 | 85957 | 9.67727907223116 | 21.3940627565627
   3 |        3 |     68330 | 85956 |  7.2223094939051 | 31.0713418287938
   4 |        4 | -13464250 |    -1 |                0 | 38.2936513226989

the second one

select * from pgr_withPoints('SELECT gid as id, source, target, length_m as cost, length_m as reverse_cost, x1,y1,x2,y2 FROM ways', 'SELECT j.bid as pid, j.way_id as edge_id, j.fraction from building_points j', -13464281, -13464250);
 seq | path_seq |   node    | edge  |       cost       |     agg_cost     
-----+----------+-----------+-------+------------------+------------------
   1 |        1 | -13464281 | 85965 | 21.3940627565627 |                0
   2 |        2 |     75852 | 85957 | 9.67727907223116 | 21.3940627565627
   3 |        3 |     68330 | 85956 |  7.2223094939051 | 31.0713418287938
   4 |        4 | -13464250 |    -1 |                0 | 38.2936513226989
(4 rows)

point -13464250 is in reality vertex 71916, making the query using the vertex, get the "same" results, agg_cost is different by 1/10th of a millimetre

select * from pgr_withPoints('SELECT gid as id, source, target, length_m as cost, length_m as reverse_cost, x1,y1,x2,y2 FROM ways', 'SELECT j.bid as pid, j.way_id as edge_id, j.fraction from building_points j', -13464281, 71916);
 seq | path_seq |   node    | edge  |       cost       |     agg_cost     
-----+----------+-----------+-------+------------------+------------------
   1 |        1 | -13464281 | 85965 | 21.3940627565627 |                0
   2 |        2 |     75852 | 85957 | 9.67727907223116 | 21.3940627565627
   3 |        3 |     68330 | 85956 | 7.22238171772227 | 31.0713418287938
   4 |        4 |     71916 |    -1 |                0 | 38.2937235465161

[cvvergara]

Bug: because it does not inform the suer that a fraction of 0 or 1 was given as input
Discussion: because opens the door to talk about how to consider 0 and 1 as fraction transparently for the user.
Enhancement: because that transparency is an enhancement
Documentation: To write down the way around with more detail on the wiki

[denadai2]

Thanks, I also preferred to implement the way around n*1.

PS: great answer!