pgr_nodenetwork on very long lines misses some nodes

[tssmits]

Problem pgr_nodenetwork misses nodes on very long ferry lines imported from OSM.

To Reproduce Load the table public.lines from the sql in the Sample Data section.

Execute

select pgr_nodenetwork('public.lines', 0.0001, id := 'way_id', the_geom := 'geom');
select pgr_createtopology('public.lines_noded', 0.0001, the_geom := 'geom', id := 'id');

Expectation All points where the lines overlap should be noded. However, some are missing.

Multiple re-runs give the same missing nodes, so the failure seems to be at least stable over time.

With the results from this sample data, one is missing (in the middle, above the two overlapping nodes):

Sample Data

create table lines
(
    way_id bigint not null,
    tags   hstore,
    geom   geometry(LineString, 3857)
);

alter table lines
    owner to postgres;

create index lines_geom_idx
    on lines using gist (geom);

create index lines_way_id_idx
    on lines (way_id);

INSERT INTO public.lines (way_id, tags, geom) VALUES (232581694, 'duration => 11:00, route => ferry, motor_vehicle => yes, name => Rotterdam-Immingham, operator => "DFDS Tor Line"', '0102000020110F0000220000009433D64721A31D41B71925D407E05941CA5C010F95A71D41E806C9FE93DF594144DFFA7E37A81D4116054AFE15DF59412FC795CFE9931D41FA51F971E1DE5941112565E3717D1D41E120556047DE594145740FF7706E1D41248032921DDE594109DD8A0660591D4188ADA23B21DE5941743A3AEFCF2A1D4125F22DA4B7DE5941F8B01B00231B1D41528D50CC14DF5941ECB65A01F2E91C4197E88847FDE059418E37E68E57D01C41E67EA13ADAE15941710BF1A26DC31C412C33780485E25941F7F28B0830BC1C41BC156B6B2DE3594120B360A5C4B51C4130634511F6E3594167337B1314A91C4101B27B13C7E45941EC1B629A606F1C41FE1EB436F7E65941B7125E1903531C4185DA09BC58E85941414F3531060C1C41E383E15CDCEB5941AABED32B9BED1B41D4CBC45F43EC59418D4AC7D72BC01B41D55C090688ED5941448C33AB37941B4196CA561EA2EE594109E0467ABF5D1B41294ED4590AF05941BC4397399DA115412BD8175E7D365A4190A7AA298E0E084174E0C098549B5A417795433D9E44E340400372503DFE5A41AD0742F3E7D6D840F12ECE3D1A075B41883E6A7B29FAD1401C27686851065B4177B8CF3B9971AD4060069FD1020E5B4168F25B08BACE94C05B3E576CB00E5B412244441B6985CBC07886598F2C155B41C4D5FBAB28FCD2C09D89F57E12175B4104B09A0ED961D4C0E94C181D27165B413E1C299817FCD4C0D6596A705C155B412A71001290F1D5C05E83CC1105165B41');
INSERT INTO public.lines (way_id, tags, geom) VALUES (32340204, 'duration:forward => 11:45, website => http://www.poferries.com, bicycle => yes, motorcar => yes, toll => yes, operator => "P&O Ferries", duration => 11:45, motorcycle => yes, route => ferry, motor_vehicle => yes, caravan => yes, hgv => yes, name => "Hull - Rotterdam", animal => yes, from => Hull, duration:backward => 11:00, to => Rotterdam, foot => yes', '0102000020110F00001D0000005266A5CE8561DEC08801A9D64F2A5B411DFAF6129967DEC0A6F1E0D31A2A5B41432D06F12149DEC020B0BEA4E9295B41A52550F2785EDCC013F8002646285B41DFDCE355A4DFDAC056B5158E70265B41214ACF4BEEB0D9C023ED392418245B41BC4EE68326F0D6C0A49C91CBD81C5B41A55CE1165295D5C0E4B51FDEB1195B41A2F4005882A2D3C0C8689A0335175B413785A1458497CBC09B8E43D50D155B41118AE4431EE795C0CF22EB4A700E5B415BFBB1923CB0AC40371606DFD30D5B41274251C536F8D140746B5B5E23065B41C11B581767BAD840A00531E8E7065B414AAF77DE331AE3407DD49539D9FD5A411EEE0D27F0BD07419E0114DF4B995A4125703ACEDA8115419B17AAED8F345A41B1DD9832E45A1B41740471F8E9EF59415A4801D5DC931B41E8FD638879EE5941D32AE153C0BD1B41159B8836FCEC59415904666AC2F01B410C8D3E9E8BEB5941805E426577061C41549EE739B3EA5941022067606F0B1C41ED54E76F39EA59416242BB9CF70D1C4101DA8D65DAE95941A42209C23E0F1C41423E138B5EE959412AB9EF37E30D1C41A193C58E77E8594118B33C0F470D1C41407A33ED7EE759413B399393960E1C41BCFDDAA914E759410821003052121C4144407AF507E75941');
INSERT INTO public.lines (way_id, tags, geom) VALUES (96109913, 'horse => no, duration => 19:00, motorcycle => no, route => ferry, bicycle => no, hgv => yes, fee => yes, name => "Rotterdam - Teesport", motorcar => no, toll => yes, foot => no, operator => "P & O"', '0102000020110F000016000000EEBCF0195538FFC04781F75FB0C95B41B592B413563DFFC0576352A6C2C95B41B8519910CA7EFFC070460384D1CA5B41BA2363B20988FFC0F399036F50CB5B4173D98997E869FFC098647FED39CC5B41449136033266FFC043AB6DFC4BCD5B41EF3C6D000079FFC0215C277AAECE5B41ABE26251547BFFC049C2BC1FC9CF5B410F22D9BE03C1FEC0B81BAF51A5D45B41BB767E123CC0FDC0B800FE3D88D55B4132E6E38CF021EBC0BAF4B35EF1C15B41C7435AB05FC1154125BF22CF6A385A41EEB58EB69A601B41F95331BA2AF05941B9A3FF7592941B413F1AA7B5CAEE59413D652473C0B51B41C36F710868ED594187A32BA032F11B41ACA50A0A99EB5941B01A7BD0BC061C410D4D2DC8B8EA59415C65DC64EF0B1C411A182F473CEA5941C826FCC96D0E1C4155D621A8DBE95941FB018622A90F1C417BC9E5305EE959412546E99D6B0D1C414F0032F704E7594147DB1BB1C40B1C41B3B451B9BDE65941');
INSERT INTO public.lines (way_id, tags, geom) VALUES (96053700, 'horse => no, duration => 15:00, motorcycle => no, route => ferry, bicycle => no, hgv => yes, name => "Zeebrugge - Teesport", motorcar => no, toll => yes, foot => no, operator => "P&O Ferries"', '0102000020110F0000180000007C369C66FFAB1541BB413AAD397D59412E41BF8912AD15417BF5CECD497D594135D0591C48B115415E816474667D59413F16AA26A8C415418C509310247E59419ADE2459ECC61541398A43DE517E59415BAB10E3B3C615412305F87DA17E59419E9EB23CE4A21541EF1FC8179581594160020966AE591541F31C9741098859418F931C496E1815419BA31942B287594126DB1669D2701441CE8E90D7438B594105FBB8E7C92912419A6E3CD654BC59411DCFD46255111241DAD7D86A6AD65941B9E72CD1C0451241EC610135FDB55A41964DE61FFF1BEBC0BFDD4ADB03C25B4135630C5843BAFDC07F4C3A04B8D55B412030F64EE8CAFEC090D49588B7D45B41C18E18E6727CFFC0BAAC6468CCCF5B4119F31B635C7AFFC08AFE6BFBACCE5B419A0BF7C50368FFC073BE3E664CCD5B4175E38DEE256CFFC0E406357C3ACC5B41D2CF18472889FFC06FE8A4E250CB5B411823F594087FFFC06595BFBCD0CA5B41003FA6D6DB3DFFC0A2BEA361C1C95B41EEBCF0195538FFC04781F75FB0C95B41');

This was imported with osm2pgsql from the file ferries-problematic.osm.pbf in this zip:

ferries-problematic.zip

Platform/versions

Host Ubuntu 20.04

Docker version 20.10.5, build 55c4c88
Docker container based on pgrouting/pgrouting:13-3.0-3.1.1

SELECT version();
PostgreSQL 13.1 (Debian 13.1-1.pgdg100+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 8.3.0-6) 8.3.0, 64-bit

SELECT postgis_full_version();
POSTGIS="3.0.3 6660953" [EXTENSION] PGSQL="130" GEOS="3.7.1-CAPI-1.11.1 27a5e771" PROJ="Rel. 5.2.0, September 15th, 2018" LIBXML="2.9.4" LIBJSON="0.12.1" LIBPROTOBUF="1.3.1" WAGYU="0.4.3 (Internal)"

SELECT pgr_version();
3.1.1

osm2pgsql and osmium:
2021-04-06 17:25:21  osm2pgsql version 1.4.1
Compiled using the following library versions:
Libosmium 2.16.0
Proj [API 4] Rel. 5.2.0, September 15th, 2018
Lua 5.3.3

[tssmits]

I've started a branch on my fork, where I've added a first attempt at a test case that should cover this issue.

https://github.com/tssmits/pgrouting/pull/1

Still figuring out how to actually run the test, but I thought I'd already share what I have so far.

[dkastl]

Thanks a lot! I tried to look through the function briefly, but it's quite a lot of code and it was contributed quite some time ago, so I'm not familiar with it. Eventually you have a not so common use case with your very long lines, which is not covered with pgRouting tests.

Feel free to ask on our chat if you have some question or want to discuss something. https://gitter.im/pgRouting/pgrouting

[cvvergara]

FYI This is a very problematic function as you can see from the lists of bugs Wrap your test case as follows, :

SELECT todo_start('issue 1882 needs to be fixed');
SELECT is((SELECT count(*)::INTEGER FROM ferry_lines), 4, 'we have 4 ferry_lines edges');
SELECT pgr_nodeNetwork('ferry_lines', 0.0001, 'id', 'the_geom');
SELECT is((SELECT count(*)::INTEGER FROM ferry_lines_noded), 15, 'Now we have 15 edges')
SELECT todo_end();

And make the PR if possible to both branches, master/main and develop. Soon we will change the name to "main". so use the branch name that you see.

[cvvergara]

Made a comment in https://github.com/tssmits/pgrouting/pull/2