Conversation
|
Quick comparison using Before this change: After: Looks like the corrected curve shape could give us a modest performance boost due to improved cache locality. |
oxidase
force-pushed
the
refactor-hilbert-values
branch
from
97937dd to
a0eedc1
Compare
oxidase
force-pushed
the
refactor-hilbert-values
branch
from
a0eedc1 to
5c4ee44
Compare
|
Tests features/testbot/compression.feature:7, features/car/maxspeed.feature:81, features/car/maxspeed.feature:100 use exact values for expectations, but other ordering could return different edges for phantom nodes and due to some round-off errors introduce 0.11 meters segments that correspond to 0.000001 coordinate precision. Expectation in tests are update to the new values that still depend on an edges ordering in R-tree. related #3368 |
|
Tests features/car/summaries.feature:9, features/car/traffic_turn_penalties.feature:105 fail due to 0-length segments in snapped phantom nodes. |
|
Test features/testbot/bearing_param.feature:48 fail due to different components of the source and the target phantom nodes. It should not be in real cases, so i would suggest to remove |
oxidase
force-pushed
the
refactor-hilbert-values
branch
2 times, most recently
from
9986141 to
e3e83cd
Compare
| # The target point `a` can belong to either `ab` or `ha` edge. | ||
| # The latter case leads to "Impossible route between points", | ||
| # because `ab` and `ha` are in different components | ||
| #| 1 | d | 90 90 | ab,bc,cd,da,da | 0->90,90->0,0->270,270->180,180->0 | |
There was a problem hiding this comment.
I'm not sure I understand this. We are not trying to snap to a, we are trying to snap to a coordinate close to 1 (which is just a coordinate not linked to an OSM node). It should be something in the middle of ab (which has bearing 90°).
The target segment for d should be unique as well. It is only contained by one segment (cd) with 90°. I'm quite confused why the original test specifies da as target segment which has bearing 180 and should not be chosen as segment for d.
There was a problem hiding this comment.
The problem is in the target point for d. Here the nearest edges to d:
input_coordinate = (lon:1.000089, lat:1)
2,1 "cd" distance 0.111226299998 fwd bearing 270.000007845 invalid, bck bearing 90.0000078449 invalid
1,5 "da" distance 0.111226299998 fwd bearing 180 invalid, bck bearing 360 invalid
1,0 "dg" distance 0.111226299998 fwd bearing 270.000000777 invalid, bck bearing 90.0000007767 invalid
4,5 "ha" distance 10.1215933 fwd bearing 89.9999992235 valid, bck bearing 269.999999223 invalid
5,6 "ab" distance 10.1215933 fwd bearing 90 valid, bck bearing 270 invalid 0.1112263
With the new ordering ha is before ab and ha also has bearing 90, so it is a valid phantom node, but ha is in another scc. One possibility would be to introduce point 2 close to d on the edge cd and use instead of d
There was a problem hiding this comment.
Ah now I understand. Yes we should fix this test case by adding a middle node 2 on da. I think I misunderstood the original test, it seems like we want to snap to da because cd has bearing 270° (since it is going in the different direction).
oxidase
force-pushed
the
refactor-hilbert-values
branch
from
e3e83cd to
b925e3d
Compare
| | from | to | bearings | route | bearing | | ||
| | 0 | b | 10 10 | bc,bc | 0->0,0->0 | | ||
| | 0 | b | 90 90 | ab,ab | 0->90,90->0 | | ||
| | 0 | b | 170 170 | da,da | 0->0,0->0 | |
There was a problem hiding this comment.
i have uncommented two checks here, both 0 and b project to a on da, so the result is a 0-size segment on da
3 participants
Issue
The current Hilbert codes is an SFC but not the original Hilbert curve #3352. The PR fixes Hilbert code computation. There are 6 failing test cases, that failing due to reordering of edges in the R-tree. For example, features/testbot/compression.feature:7 returns phantom node that uses 3 segments instead of 4, so the small adjustment of 0.11 meters is not added. Other tie-breaking cases look not so trivial and must be clarified first.
Tasklist
Requirements / Relations
Arndt, Jörg. Matters Computational Ideas, Algorithms, Source Code, 2010. p86
http://home.pipeline.com/~hbaker1/hakmem/topology.html#item115