[postgis-users] Union fails on 2389 linestrings.

Wed Jul 28 13:15:52 PDT 2010

OK, I finally have it down to a manageable use case.  Union these 16
linestrings, you get a topology exception.  Remove any one of them, you
don't.  What the heck can I do about this?  Simplifying and snapping to
grid, at any reasonable precision, did not help my larger real data (I
didn't try with this little test case).

Is there any chance that ST_Union has a bug?  Isn't it supposed to be adding
the node it complains is missing?

SELECT ST_Union(ARRAY[
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.30613361296
33.8122380826708,-118.304098 33.810251,-118.304236 33.810103,-118.304709
33.810071,-118.305765 33.810748,-118.305909 33.809732,-118.306626
33.809556,-118.306593 33.808887,-118.307343 33.808265,-118.307262
33.808031,-118.306361 33.807514,-118.304929 33.807514,-118.304845
33.807291,-118.305287 33.806817,-118.306369 33.806816,-118.306362
33.804825,-118.307257 33.80412,-118.307256 33.803689,-118.306994
33.803306,-118.307001 33.802282,-118.306366 33.801427,-118.304812
33.801424,-118.304852 33.800714,-118.304474 33.799426,-118.304048
33.799149,-118.303735 33.798054,-118.302859 33.798053,-118.302692
33.797818,-118.3043 33.796488,-118.304414 33.796697,-118.305316
33.796699,-118.305309 33.795842,-118.305185 33.795766,-118.307667
33.793712,-118.307871 33.79377,-118.307762 33.794063,-118.308329
33.794165,-118.309331 33.794785,-118.309496 33.794646,-118.309026
33.793433,-118.309301 33.793431,-118.310179 33.792369,-118.311477
33.792408,-118.311221 33.791529,-118.312053 33.789477,-118.314394
33.78809,-118.314441 33.787542,-118.314939 33.787103,-118.314933
33.787655,-118.316174 33.788043,-118.317662 33.786051,-118.317822
33.785331,-118.31926 33.783198,-118.319515 33.783401,-118.31952
33.784353,-118.320133 33.784875,-118.320168 33.785781,-118.320644
33.786331,-118.321187 33.786329,-118.321664 33.785748,-118.322465
33.786108,-118.322465 33.785588,-118.322725 33.785508,-118.322861
33.785552,-118.322863 33.787017,-118.324012 33.786812,-118.324484
33.78618,-118.324536 33.785867,-118.325534 33.786479,-118.327373
33.786445,-118.32739 33.78696,-118.328084 33.7867,-118.328192
33.786312,-118.329673 33.786315,-118.330558 33.786692,-118.331564
33.78613,-118.332317 33.786324,-118.333303 33.785763,-118.333296
33.7829,-118.334243 33.781681,-118.334739 33.781502,-118.336465
33.782973,-118.337471 33.78022,-118.338271 33.779854,-118.33873
33.779245,-118.339713 33.7811,-118.340119 33.779571,-118.340489
33.779635,-118.340011 33.778281,-118.34055 33.777196,-118.34009
33.777247,-118.339995 33.77709,-118.341573 33.776763,-118.342003
33.776325,-118.342988 33.777413,-118.343422 33.776597,-118.342638
33.77558,-118.343555 33.776151,-118.343818 33.776151,-118.344472
33.775277,-118.344577 33.775582,-118.343992 33.776306,-118.344084
33.77655,-118.344886 33.77729,-118.348172 33.779425,-118.349097388008
33.7794492053201)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.307700993013
33.8134536081132,-118.307366 33.813558,-118.306908 33.812743,-118.304434
33.810553,-118.304622 33.810418,-118.30525 33.810988,-118.305923
33.810719,-118.306 33.810101,-118.306704 33.809973,-118.306688
33.809247,-118.307466 33.808468,-118.307319 33.808037,-118.306547
33.807529,-118.30539 33.807538,-118.305338 33.807293,-118.305635
33.806943,-118.30707 33.806906,-118.307423 33.806221,-118.307375
33.805322,-118.307014 33.80495,-118.307489 33.8043,-118.30749
33.803281,-118.307227 33.803082,-118.30738 33.802612,-118.307223
33.802298,-118.307267 33.801238,-118.306917 33.801077,-118.305484
33.801074,-118.305272 33.800949,-118.305345 33.800715,-118.304968
33.799428,-118.305239 33.7988,-118.304129 33.7988,-118.303185
33.797819,-118.304138 33.797653,-118.304135 33.797435,-118.303851
33.797269,-118.306955 33.794712,-118.307505 33.794711,-118.30766
33.794122,-118.30946 33.793419,-118.310673 33.792496,-118.311722
33.792499,-118.31194 33.792328,-118.311811 33.791541,-118.312067
33.79133,-118.312203 33.791282,-118.312207 33.792323,-118.312605
33.793072,-118.313723 33.79307,-118.314322 33.792613,-118.314338
33.791002,-118.313872 33.790674,-118.314438 33.790629,-118.314586
33.790086,-118.31479 33.790069,-118.314784 33.790818,-118.315957
33.790293,-118.316272 33.79029,-118.316276 33.789496,-118.317512
33.788665,-118.317508 33.78897,-118.317922 33.789289,-118.319415
33.789292,-118.319822 33.788966,-118.319822 33.787578,-118.320026
33.787281,-118.320228 33.787282,-118.320228 33.788607,-118.321767
33.787298,-118.321769 33.78668,-118.322724 33.785959,-118.32286
33.786049,-118.322864 33.787241,-118.324012 33.786846,-118.324477
33.786221,-118.324536 33.785867,-118.325534 33.786479,-118.327373
33.786445,-118.32739 33.78696,-118.328084 33.7867,-118.328192
33.786312,-118.329976 33.786391,-118.330383 33.786205,-118.330798
33.786434,-118.331589 33.786157,-118.333241 33.786522,-118.33319
33.785878,-118.333446 33.785733,-118.333249 33.78524,-118.333293
33.783478,-118.333551 33.783132,-118.33375 33.783734,-118.337252
33.784222,-118.337272 33.78409,-118.337582 33.78435,-118.337953
33.784311,-118.338888 33.785102,-118.339435 33.784442,-118.339977
33.784578,-118.340642 33.783119,-118.341129 33.782651,-118.341162
33.782983,-118.340942 33.783344,-118.34147 33.784,-118.342781
33.785206,-118.343369 33.785377,-118.343965 33.78596,-118.344404
33.785906,-118.345565 33.785188,-118.346632 33.784948,-118.346263
33.785593,-118.345294 33.786038,-118.343339 33.787391,-118.342914
33.788404,-118.344329 33.789551,-118.344834 33.789647,-118.345547
33.790826,-118.346802 33.791674,-118.346973 33.792355,-118.347339
33.79248,-118.348118 33.793207,-118.348143 33.793939,-118.348962
33.793846,-118.349103 33.793586,-118.349468 33.793472,-118.350038
33.792956,-118.350515 33.792864,-118.351036 33.792069,-118.353376
33.790784,-118.355734 33.789024,-118.355245 33.788011,-118.356367
33.786715,-118.354972 33.78611,-118.354149 33.786328,-118.354231
33.784792,-118.354544 33.784053,-118.355962 33.784602,-118.357489
33.785796,-118.358813435042 33.7855261326062)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.304848630339
33.8111422006911,-118.304605 33.810709,-118.303261 33.809465,-118.303066
33.808994,-118.303047 33.808764,-118.304678 33.808727,-118.304204
33.807417,-118.303217 33.807414,-118.303039 33.807564,-118.30284
33.807286,-118.303155 33.80711,-118.305469 33.807118,-118.305132
33.805605,-118.304916 33.805121,-118.304567 33.80512,-118.304624
33.804945,-118.303265 33.801157,-118.302756 33.801007,-118.300683
33.797815,-118.301197 33.797388,-118.301319 33.797708,-118.302268
33.79771,-118.302535 33.797461,-118.302534 33.7971,-118.301946
33.796762,-118.302558 33.796716,-118.302656 33.796386,-118.302522
33.796285,-118.303826 33.795209,-118.304173 33.795212,-118.304241
33.794877,-118.305718 33.793661,-118.307238 33.793667,-118.307507
33.793434,-118.30751 33.792915,-118.307226 33.792558,-118.307047
33.792557,-118.307673 33.792037,-118.307796 33.792023,-118.307974
33.792387,-118.30957 33.792391,-118.309312 33.791501,-118.3106
33.790482,-118.310854 33.790483,-118.311109 33.790064,-118.312064
33.789273,-118.314397 33.78883,-118.314404 33.78825,-118.314596
33.78801,-118.314802 33.788004,-118.314793 33.788736,-118.316043
33.788337,-118.316826 33.788339,-118.317112 33.787982,-118.317143
33.786759,-118.317543 33.786583,-118.317784 33.787485,-118.318591
33.787418,-118.319824 33.787894,-118.319819 33.785511,-118.320017
33.785203,-118.320221 33.78533,-118.320225 33.786017,-118.320425
33.786482,-118.321244 33.78648,-118.321721 33.785898,-118.322521
33.78602,-118.322522 33.785558,-118.322861 33.785552,-118.322863
33.787017,-118.324012 33.786812,-118.324484 33.78618,-118.324536
33.785867,-118.325473 33.786414,-118.327192 33.786568,-118.327159
33.786393,-118.32913 33.786126,-118.330072 33.786179,-118.330661
33.78648,-118.331149 33.786488,-118.33146 33.786208,-118.33199
33.786395,-118.333088 33.786362,-118.333197 33.784267,-118.333617
33.783891,-118.333541 33.782489,-118.334243 33.781681,-118.334727
33.781597,-118.337372 33.783843,-118.337801 33.782229,-118.337775
33.78179,-118.337228 33.781161,-118.338482 33.780641,-118.338787
33.78142,-118.339889 33.781405,-118.340305 33.78154,-118.340372
33.779912,-118.340702 33.779767,-118.342003 33.779991,-118.342707
33.778679,-118.343946 33.780445,-118.343594 33.781199,-118.34191
33.782263,-118.341886 33.783636,-118.343458 33.784865,-118.344662
33.785274,-118.345142 33.784764,-118.346172 33.784403,-118.347436
33.784214,-118.347888 33.784652,-118.348115 33.7844,-118.348775
33.784432,-118.350288 33.784162,-118.351655 33.782986,-118.351467
33.782198,-118.350625 33.781652,-118.350715 33.781321,-118.350949
33.781314,-118.352025 33.78202,-118.352465 33.782066,-118.352774
33.780824,-118.352971 33.780656,-118.355227 33.782384,-118.355679
33.78227,-118.355689 33.781705,-118.356677 33.781749,-118.357000162508
33.7819097651871)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.357169759789
33.7834490284716,-118.357033 33.783851,-118.357898
33.784215,-118.359328629247 33.784207709798)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.303089803431
33.8096422063087,-118.30301 33.808914,-118.302281
33.808821,-118.302230554228 33.8087352371279)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.301521804907
33.8075302921941,-118.301284 33.807126,-118.299501 33.805505,-118.29965
33.805337,-118.300478 33.806088,-118.300959 33.805355,-118.301754
33.80542,-118.302461 33.8049,-118.300752 33.803522,-118.300736
33.802591,-118.29908 33.800009,-118.299078 33.79936,-118.298126
33.798199,-118.297897 33.798196,-118.297542 33.798694,-118.296491
33.797739,-118.297443 33.797578,-118.297399 33.796956,-118.297636
33.796822,-118.29767 33.797187,-118.297998 33.797514,-118.299227
33.797578,-118.29968 33.797272,-118.299688 33.796031,-118.299392
33.795709,-118.299874 33.795499,-118.299915 33.794929,-118.30138
33.793734,-118.302011 33.793739,-118.302555 33.793521,-118.301943
33.79327,-118.302688 33.79317,-118.302722 33.792626,-118.302976
33.792415,-118.303621 33.792417,-118.303482 33.791996,-118.304351
33.791287,-118.305664 33.791398,-118.305345 33.790471,-118.306815
33.790407,-118.307346 33.790006,-118.306795 33.789544,-118.306567
33.789543,-118.306835 33.789398,-118.307507 33.789402,-118.307649
33.789276,-118.307718 33.788531,-118.307919 33.788787,-118.309149
33.788796,-118.309397 33.788545,-118.30911 33.788213,-118.309956
33.787547,-118.31168 33.787433,-118.311612 33.786862,-118.312713
33.785993,-118.312834 33.785971,-118.31279 33.786371,-118.313089
33.786427,-118.313412 33.786157,-118.314404 33.786276,-118.314426
33.785601,-118.313755 33.785209,-118.314624 33.785098,-118.314696
33.784527,-118.315529 33.784589,-118.315858 33.785109,-118.316121
33.786327,-118.316484 33.786947,-118.317697 33.785776,-118.317923
33.784866,-118.318853 33.784151,-118.318883 33.783487,-118.319275
33.783116,-118.319695 33.78206,-118.319977 33.782698,-118.319707
33.78376,-118.319754 33.784296,-118.320396 33.784866,-118.32043
33.785632,-118.321971 33.785845,-118.322728 33.785326,-118.324198
33.786022,-118.324267 33.785631,-118.325005 33.786193,-118.325794
33.786532,-118.326632 33.786509,-118.326488 33.786846,-118.32664
33.786845,-118.326819 33.787409,-118.326993 33.787409,-118.327278
33.786916,-118.327253 33.786443,-118.328893 33.786306,-118.32939
33.786114,-118.330125 33.786169,-118.330733 33.78648,-118.331513
33.786198,-118.333173 33.78661,-118.333114 33.785919,-118.333302
33.785783,-118.333173 33.785281,-118.333247 33.784311,-118.333624
33.783764,-118.333511 33.782611,-118.334297 33.781646,-118.336277
33.783248,-118.336621 33.78325,-118.338452 33.784795,-118.33917
33.784288,-118.339476 33.783346,-118.339385 33.782988,-118.339631
33.782794,-118.338909 33.781621,-118.340143 33.781607,-118.340929
33.780816,-118.341792 33.780975,-118.342079 33.780189,-118.34225
33.780101,-118.342615 33.780504,-118.342196 33.781688,-118.341381
33.783009,-118.341979 33.783894,-118.343081 33.784838,-118.344449
33.785454,-118.345181 33.784944,-118.346233 33.784494,-118.346648
33.784836,-118.349171 33.784624,-118.349984 33.784341,-118.353068
33.785771,-118.353056 33.783686,-118.352762 33.783051,-118.352003
33.782798,-118.352097 33.782229,-118.352621 33.782097,-118.352685
33.782538,-118.353197 33.782903,-118.353692 33.782857,-118.353489
33.782097,-118.353978 33.782284,-118.354301 33.782759,-118.354704
33.782671,-118.354936 33.782421,-118.355333 33.782578,-118.355198
33.782707,-118.355458 33.783551,-118.35688 33.783258,-118.35714707651
33.7835707923095)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.357401619265
33.7838689054455,-118.357879 33.784428,-118.357962
33.785686,-118.358889500305 33.7854213315776)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.308746858587
33.8175427468454,-118.308708 33.817061,-118.30847770782 33.8169411415257)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.307561901608
33.8160004041704,-118.307515 33.814991,-118.307658
33.814793,-118.307628474836 33.8146729847436)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.307382137965
33.8136716631955,-118.307365 33.813602,-118.307043979511 33.813016336587)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.307042066317
33.8130128461942,-118.306881 33.812719,-118.303923 33.810094,-118.304036
33.80994,-118.304256 33.810138,-118.304885 33.810011,-118.305908
33.810079,-118.305874 33.80954,-118.306606 33.809107,-118.306362
33.808818,-118.307278 33.808159,-118.30716 33.807777,-118.306317
33.807502,-118.304689 33.807501,-118.304588 33.807291,-118.305031
33.806816,-118.306114 33.806818,-118.306106 33.804825,-118.307088
33.804119,-118.306973 33.80209,-118.30611 33.801426,-118.304556
33.801423,-118.303994 33.799329,-118.304026 33.798643,-118.303713
33.798054,-118.302711 33.798053,-118.302435 33.797818,-118.305056
33.79566,-118.306831 33.795665,-118.306617 33.795237,-118.30609
33.794802,-118.307666 33.793498,-118.309843 33.792447,-118.310571
33.792504,-118.310883 33.791627,-118.312094 33.790712,-118.314204
33.790586,-118.314398 33.790274,-118.314358 33.789593,-118.314589
33.789463,-118.314711 33.789504,-118.314661 33.790251,-118.315831
33.790306,-118.315512 33.789507,-118.316943 33.78944,-118.31714
33.789014,-118.316546 33.788727,-118.317516 33.78804,-118.31751
33.788755,-118.318006 33.789196,-118.319333 33.789198,-118.319822
33.788747,-118.319822 33.786954,-118.320026 33.786657,-118.320254
33.786592,-118.320228 33.78807,-118.321768 33.786763,-118.321722
33.786007,-118.322725 33.785508,-118.322861 33.785552,-118.322863
33.787017,-118.324012 33.786812,-118.324484 33.78618,-118.324536
33.785867,-118.325534 33.786479,-118.327373 33.786445,-118.32739
33.78696,-118.328084 33.7867,-118.328192 33.786312,-118.329673
33.786315,-118.330522 33.786672,-118.331562 33.786128,-118.332314
33.786323,-118.33323 33.785922,-118.333379 33.784045,-118.333293
33.782898,-118.334243 33.781681,-118.334734 33.78154,-118.336434
33.782989,-118.337364 33.780521,-118.338572 33.779886,-118.340304
33.779689,-118.341613 33.779914,-118.342106 33.779586,-118.342518
33.77815,-118.342987 33.777958,-118.344659 33.7805,-118.343381
33.780906,-118.343632 33.781143,-118.342398 33.783934,-118.343512
33.784819,-118.344915 33.784888,-118.34587 33.784421,-118.347695
33.784125,-118.348113 33.78462,-118.350786 33.78368,-118.351221
33.783293,-118.349414 33.781941,-118.349272 33.780323,-118.351328
33.780357,-118.352627 33.78109,-118.353084 33.77979,-118.353488
33.779397,-118.353845 33.77931,-118.354605 33.779992,-118.354302
33.780391,-118.354036 33.781226,-118.355018 33.780952,-118.355374
33.781143,-118.3558 33.780502,-118.356525457447 33.7806494603301)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.357238541314
33.7806010373294,-118.357325612665 33.7805398901349)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.357342573846
33.7805383054012,-118.357615033695 33.7806751225237)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.357693277501
33.7809493965079,-118.357455525965 33.7813634913787)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.357444440338
33.7838848876304,-118.357453 33.783942,-118.357982
33.784141,-118.35917094071 33.7841021918463)'),
ST_GeomFromEWKT('SRID=4326;LINESTRING(-118.29510929418
33.7752042976004,-118.295895 33.775667,-118.295975 33.775514,-118.296254
33.775883,-118.296184 33.778951,-118.296341 33.77951,-118.297119
33.780547,-118.298343 33.780232,-118.299024 33.779858,-118.299207
33.778491,-118.299472 33.778718,-118.301295 33.779122,-118.301733
33.778885,-118.30297 33.778888,-118.303043 33.779769,-118.303358
33.779732,-118.303983 33.778992,-118.303682 33.77972,-118.304919
33.779888,-118.304667 33.780495,-118.303892 33.780511,-118.30404
33.781208,-118.303359 33.781416,-118.304219 33.782044,-118.304214
33.782771,-118.305056 33.782756,-118.3054 33.783381,-118.305683
33.783381,-118.30588 33.783663,-118.305981 33.7843,-118.307116
33.785157,-118.307545 33.785104,-118.309046 33.78565,-118.309874
33.786831,-118.3097 33.787235,-118.309963 33.787412,-118.310398
33.787411,-118.311112 33.78786,-118.311488 33.787548,-118.31177
33.787632,-118.311792 33.787809,-118.311122 33.788364,-118.312091
33.788904,-118.312363 33.789343,-118.31268 33.789485,-118.310864
33.791643,-118.309697 33.791608,-118.309507 33.792027,-118.309862
33.792454,-118.308861 33.79445,-118.3088 33.794935,-118.30625
33.796639,-118.30641 33.796778,-118.305036 33.796853,-118.304479
33.7973,-118.305042 33.797743,-118.305281 33.797743,-118.304355
33.798502,-118.303949 33.79877,-118.303609 33.798097,-118.300308
33.798092,-118.301358 33.800068,-118.301353 33.800585,-118.301167
33.801237,-118.30032 33.802052,-118.29926 33.80198,-118.299237
33.802909,-118.298648 33.804168,-118.297427 33.804616,-118.29581032417
33.804010103814)')
]) as broken;

NOTICE:  TopologyException: found non-noded intersection between LINESTRING
(-118.323 33.7869, -118.323 33.7869) and LINESTRING (-118.323 33.7869,
-118.323 33.7869) at -118.323 33.7869

ERROR:  GEOS union() threw an error!

********** Error **********

ERROR: GEOS union() threw an error!
SQL state: XX000

On Wed, Jul 28, 2010 at 9:18 AM, Jeff Adams <jadams at azavea.com> wrote:

> The ST_SnapToGrid doesn't help.  It changes the points slightly, but Union
> still fails.  I tried simplifying my input linework, snapping to grids of
> various sizes, nothing seem to make it happy.  I'm trying to reduce the
> amount of lines being unioned to see if that either fixes it or at least I
> can get a small enough test case to post here.
>
>
> On Tue, Jul 27, 2010 at 10:59 AM, Jeff Adams <jadams at azavea.com> wrote:
>
>> The challenge is I don't know the exact point it is unhappy about.  If
>> I check the one in the error message, none of my linestrings intersect
>> it, which means it is probably being printed with insufficient
>> precision.  I have 19 linestrings that have a point that could be
>> printed as -118.296 34.1185 due to rounding.
>>
>> Also, the two linestrings printed in the error aren't real inputs,
>> they must be something created internally by ST_Union as it is
>> processing.
>>
>> I tried adding a ST_SnapToGrid(..., 0.00001)  (0.00001 is very roughly
>> a meter in lat/lon) and it has been running for almost 40 minutes, so
>> it is either slower than before or it has made it further than before
>> :-).
>>
>> Jeff
>>
>> On Tue, Jul 27, 2010 at 10:27 AM, Nicolas Ribot <nicolas.ribot at gmail.com>
>> wrote:
>> >> ST_IsValid returns true for all of them.  I'll try reducing the
>> >> precision slightly, though I'm later going to do point-in-poly checks
>> >> against some other original input data and the reduced precision will
>> >> increase the chances of inaccurate results.
>> >>
>> >
>> > Ok,
>> > I'm wondering if using the notice message could be used in conjunction
>> > with linear referencing functions to add the missing point to the
>> > failing linestring(s):
>> >
>> > 1- identify failing linestrings (or offending coordinates, then
>> > finding the closest linestring to this point)
>> > 2- complete these linestrings with new points built from coordinates
>> > 3- relaunch the union procedure.
>> >
>> > Though I've never done this.
>> >
>> > Nicolas
>> > _______________________________________________
>> > postgis-users mailing list
>> > postgis-users at postgis.refractions.net
>> > http://postgis.refractions.net/mailman/listinfo/postgis-users
>> >
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20100728/fe4bce2e/attachment.html>