[geos-devel] [BUG] no outgoing dirEdge found

[strk at refractions.net]

Mark, I found out that a coordinate reduction on one of the input
geometries goes around the bug. Attached is a test file.
I confirm the bug being in GEOS-2.1.2CVS, GEOS-3.0.0 and
current JTS:

-- with GEOS:
psql:test.sql:16: NOTICE:  TopologyException: no outgoing dirEdge found (-102895,939993)
psql:test.sql:16: ERROR:  GEOS difference() threw an error!


-- with JTS:
psql:test.sql:16: NOTICE:  no outgoing dirEdge found [ (-102894.55624213882, 939992.6692729667, NaN) ]
psql:test.sql:16: ERROR:  JTS difference() threw an error!


Making an XML test would be harder since WKT representation brings 
to precision reduction that in turn makes the test work. The format
used in the attached test.sql file is HEX-WKB.

Test has been conducted linking the postgis library against libGEOS
and libJTS respectively.

--strk;
-------------- next part --------------
SELECT postgis_full_version();

CREATE TEMP TABLE test(a geometry, b geometry);
INSERT INTO test VALUES (
'0103000020E80A00000100000069010000ECA2396C13BBFF40E8BA3424319F2541DEFB1D49DFB8FF40E73660ADA07F2541FAD6C80B43B2FF407033A9AC12602541E43630383FA7FF401F0EFC9789402541470638AAD497FF408AE2E2E40721254133F2A0950484FF40D372540890012541776AF085D06BFF40B21B837624E22441E2C9515E3A4FFF40DBD7ABA2C7C22441CDA87059442EFF407956E5FE7BA32441DF5C4C09F108FF40A728EFFB4384244184A9045743DFFE40A40901092265244116A59F823EB1FE4096459A931846244141D7C822E67EFE40AD4251072A272441B29589243E48FE405630A3CD58082441A6A4FACA4A0DFE4065E0C34DA7E923417321EFAE10CEFD40D6CD6DEC17CB2341B7BD98BE948AFD40F954B20BADAC23414652253DDC42FD40B720CA0A698E234192D155C2ECF6FC40ADD0E5454E702341B3A10E3ACCA6FC40CCDBFE155F522341D166E1E38052FC4022B3A8D09D3423411747905211FAFB408628E2C70C172341F7B18A6B849DFB40B61CE749AEF92241F6B46366E13CFB40907802A184DC2241B9E841CC2FD8FA40FA74601392BF224194014977776FFA400135E1E2D8A22241500FFD91C002FA40CFB5EB4C5B8622416E789F961392F940DE17418A1B6A22418ABD854E791DF940FD44D0CE1B4E224122126AD1FAA4F84096F689495E32224164D8B584A128F840951F3524E5162241350EC61A77A8F7406EBD4383B2FB2141FEB929928524F7408B13A885C8E021417066DA34D79CF6408654AA4429C62141BCBC6E977611F64071BCBED3D6AB21414A4D47986E82F5407B1F5C40D39121416897B55ECAEFF44024F0D29120782141DA601D5A9559F4403AC024C9C05E2141AC6E1041DBBFF340C23FDCE0B545214109B16410A822F340EABCE5CC012D214160F4440A0882F2402528687AA61421417B2A3CB507DEF140659F9ECFA5FC2041975E3BDBB336F1408B83B2AB01E5204109689A88198CF040F01A96E6BBCD204192DE26168CBCEF40FDC3DF50D6B620418BB372E18D5AEE40A5BAA5B352A020414762D20D54F2EC409D735AD0328A204125366DB2FA83EB401B90A9607874204149EEA6609E0FEA40CC6C5516255F20412C71E5215C95E840C14E159B3A4A204167244D755115E740E4307490BA3520410516744D9C8FE5409C34B08FA621204130250C0E5B04E44024B89A29000E2041F2588489AC73E240152AF2CC91F51F414194A1FEAFDDE040A812CC8B04D01F41B9AE1D2C0A85DE40479B677D5BAB1F413F7ECABF9744DB4062B59D7D99871F4122E757A249FAD740CEC04256C1641F412B6FA08261A6D440A7E1EEBED5421F41A4982BCF2149D14038C2C75CD9211F41436DFF619BC5CB402FC54BC2CE011F41DF6CCA0C52E7C44028AC1E6FB8E21E41DD196F76E1EFBB409BB6D7CF98C41E41F3220E7C07E0AB40163DD13D72A71E4180CA45A3CBEE47C079CCF9FE468B1E4173AA092451DDACC0EBC4A64519701E41488EA3D140CBBCC00E806830EB551E41721152D143A2C5C0D501E0C9BE3C1E41BB857A0AAEECCCC05637960896241E4176759EC42622D2C0BAC6D4CE720D1E41BE846FDD47D4D5C0657380EA56F71D41F4583488708CD9C03319F51444E21D4153B71285564ADDC0B041E3F23BCE1D41F73ECE90D786E0C0E7552F1440BB1D417067519F176BE2C05E6FD2F351A91D413DDB08ABC551E4C0B5CABCF772981D41C6EB69C0BB3AE6C01FDEB970A4881D4115D45EBED325E8C00516569AE7791D4168E43F59E712EAC0BF39C69A3D6C1D4198FFCF1DD001ECC05C7AD082A75F1D41AE2E3C7467F2EDC0482DB74D26541D41D30E1EA386E4EFC0703425E1BA491D41C76E406903ECF0C06B151C0D66401D417873748760E6F1C014C1E38B28381D41AC8C2E2647E1F2C0D60CFC0103311D410441B9B4A3DCF3C0C9DE0FFEF52A1D41EDBA2C9962D8F4C0A10DEAF801261D419914F63170D4F5C053F56B5527221D41003D5FD7B8D0F6C024C18560661F1D41725717DD28CDF7C0C06B3051BF1D1D410D77BB93ACC9F8C0D0756948321D1D4181975F4A30C6F9C067533051BF1D1D4180B41750A0C2FAC075908560661F1D4127E180F5E8BEFBC051AC6B5527221D41C5404A8EF6BAFCC051ACE9F801261D4152C2BD72B5B6FDC033650FFEF52A1D41FF7F480112B2FEC0047BFB0103311D4139A402A0F8ACFFC01117E38B28381D41D05A1BDFAA5300C145531B0D66401D41B215F4EA8AD000C1365A24E1BA491D41C495ACB6124D01C10B3BB64D26541D4169AA478C38C901C12E70CF82A75F1D41EBBA6BBDF24402C1B517C59A3D6C1D418A0924A437C002C136DC549AE7791D41FC4EA1A3FD3A03C1A38CB870A4881D414F9FF9283BB503C1A661BBF772981D414689E7ABE62E04C1DAEED0F351A91D41386188AFF6A704C10ABE2D1440BB1D41B0A819C3612005C19B92E1F23BCE1D41F083B5821E9805C10753F31444E21D41B72E0E98230F06C145967EEA56F71D41AE6128BB678506C1CDD2D2CE720D1E41DA9914B3E1FA06C1C12C940896241E41C133A756886F07C1C2E0DDC9BE3C1E41D14B2F8D52E307C1A7486630EB551E41CA552C4F375608C15C77A44519701E410E5D02A72DC808C1F068F7FE468B1E41B1DFACB12C3909C1C3C3CE3D72A71E417036709F2BA909C1B027D5CF98C41E41AB7B89B421180AC1D7071C6FB8E21E41ACE3DC4906860AC1AD0B49C2CE011F41A378A2CDD0F20AC1BCF3C45CD9211F41E52C11C4785E0BC168FEEBBED5421F410D3608C8F5C80BC107C93F56C1641F41D1A3B68B3F320CC14DA99A7D99871F41742541D94D9A0CC1207B647D5BAB1F41F3F0659318010DC1AFDEC88B04D01F4116BF1EB697660DC189E2EECC91F51F41C9CF4057C3CA0DC1B60A9929000E20414EEA1AA7932D0EC1A77DAE8FA6212041DF4C11F1008F0EC189707290BA352041B07F379C03EF0EC12585139B3A4A20413BFFE72B944D0FC1129A5316255F204117B25940ABAA0FC167B4A76078742041528F99CB200310C1148F58D0328A20418BAA0D06283010C16DCDA3B352A020414941A4CC675C10C13DCEDD50D6B62041221106ACDC8710C1CE1C94E6BBCD2041B960AE4083B210C12F7DB0AB01E52041EEA52E3758DC10C1F8909CCFA5FC2041EAEA704C580511C1D011667AA6142141DEECF84D802D11C1D79EE3CC012D214154EF231ACD5411C11A1ADAE0B5452141313F67A03B7B11C1299322C9C05E214166608DE1C8A011C1D5BBD09120782141B1E1F1EF71C511C11AE45940D39121419ED1BBEF33E911C12B7ABCD3D6AB214159D016170C0C12C1870BA84429C62141C5B96AAEF72D12C101C4A585C8E0214195E39110F44E12C187674183B2FB21411BEB0DABFE6E12C181C33224E5162241BB0E3BFE148E12C1839487495E322241FB0E829D34AC12C11BDDCDCE1B4E22414D93882F5BC912C15CAA3E8A1B6A2241D00E606E86E512C1DF42E94C5B8622415A21B327B40013C1D3BCDEE2D8A222414B71F13CE21A13C1BFF75D1392BF2241AFFA79A30E3413C17BF6FFA084DC22416DD0C364374C13C1F895E449AEF922415D4C859E5A6313C1519DDFC70C1723411AABD982767913C1AA23A6D09D342341C6106558898E13C14348FC155F522341D5F3767A91A213C14839E3454E7023413AEB2A598DB513C1A885C70A698E23416FDD87797BC713C175B6AF0BADAC2341D48D9D755AD813C1112C6BEC17CB23413386A0FC28E813C1943BC14DA7E92341235A04D3E5F613C1AD88A0CD580824414D4294D28F0414C161984E072A2724419E0D8AEA251114C1DD98979318462441AA66A31FA71C14C1B25AFE0822652441856B358C122714C1B377ECFB4384244195963E60673014C1B9A3E2FE7BA32441FEF676E1A43814C18423A9A2C7C2244154B75E6BCA3F14C1FA65807624E2244180F14A6FD74514C1EFBB510890012541CBCE7074CB4A14C1B22AE0E40721254140F3EE17A64E14C18855F997894025419833D50C675114C1517AA6AC1260254128952A1C0E5314C1777D5DADA07F25414597F1249B5314C15C013224319F2541DAC52A1C0E5314C17985069BC1BE2541F994D50C675114C14189BD9B4FDE25414685EF17A64E14C11AAF6AB0D8FD25416D917174CB4A14C16DDB83635A1D2641AEE44B6FD74514C1194C1240D23C2641FCDA5F6BCA3F14C164A4E3D13D5C2641074B78E1A43814C19CE9BAA59A7B2641E61A4060673014C1946C8149E69A26410020378C122714C1339C774C1EBA26412D4BA51FA71C14C139BD653F40D9264102228CEA251114C17E83CCB449F82641698696D28F0414C1D588154138172741CBCD06D3E5F613C1CE9DC37A093627413529A3FC28E813C196F0A2FABA542741FB5FA0755AD813C13106F95B4A73274183DE8A797BC713C14F82B43CB5912741FF1A2E598DB513C107BA9C3DF9AF27410B527A7A91A213C1B90D810214CE27412B9D6858898E13C17706683203EC27416665DD82767913C13233BE77C40928414634899E5A6313C111C2848055272841A6E5C764374C13C157D27FFEB3442841E43C7EA30E3413C1257B64A7DD6128412AE0F53CE21A13C197830635D07E284189BCB727B40013C19BC88565899B2841F2D5646E86E512C10B4D7BFB06B8284104868D2F5BC912C16BF025BE46D42841E42C879D34AC12C1EBC8967946F02841705740FE148E12C1211DDDFE030C2941325E13ABFE6E12C121FA31247D272941A1809710F44E12C1756223C5AF422941578070AEF72D12C1B412BFC2995D2941FDBF1C170C0C12C143D8BC0339782941DEE9C1EF33E911C11077A8748B9229411322F8EF71C511C1EC1A0B088FAC29416DC893E1C8A011C1555194B641C629415DCE6DA03B7B11C17C88427FA1DF294123A52A1ACD5411C15E108B67ACF82941C9C8FF4D802D11C1C99A817B60112A4169EC774C580511C14D37FFCDBB292A4173CC353758DC10C1F5C7C878BC412A41B7ABB54083B210C1E0EBB49C60592A4108800DACDC8710C1B45CD161A6702A4182D3ABCC675C10C108BC87F78B872A417F5F1506283010C1E9CDC1940F9E2A416866A1CB200310C1A01D0D782FB42A414EA36940ABAA0FC1F609BEE7E9C92A413E32F82B944D0FC13F3612323DDF2A413DF3479C03EF0EC1685D52AD27F42A41AAFF21F1008F0EC18884F3B7A7082B410ADB2BA7932D0EC1358AB7B8BB1C2B4123FD5157C3CA0DC13510CD1E62302B41B72730B697660DC1F8BCEE6199432B418093779318010DC177D2810260562B418C0053D94D9A0CC11218B489B4682B4110B6C88B3F320CC10D159989957A2B410B7E1AC8F5C80BC17F99469D018C2B4134A923C4785E0BC15793F068F79C2B41D227B5CDD0F20AC1702D049A75AD2B4146C4EF4906860AC1733642E77ABD2B41378C9CB421180AC18FCDD81006CD2B417275839F2BA909C109537CE015DC2B41A84BC0B12C3909C1989A7F29A9EA2B4177F415A72DC808C1CD5DEBC8BEF82B411D17404F375608C191EC94A555062C418335438D52E307C1141A34B06C132C414644BB56886F07C15A6478E302202C41A1CF28B3E1FA06C1DA541D44172C2C4123BB3CBB678506C17B18FEE0A8372C4144AA2298230F06C18E4D28D3B6422C41FB1FCA821E9805C12106EE3D404D2C41A0632EC3612005C16EFDF64E44572C416D399DAFF6A704C1EFFE503EC2602C41207DFCABE62E04C1DF7D7F4EB9692C412DAD0E293BB503C1EF5B8ACC28722C413875B6A3FD3A03C104DE0B10107A2C417F4639A437C002C1E7CD3D7B6E812C41F10C81BDF24402C1EDC7057B43882C41D70F5D8C38C901C18CB300878E8E2C41ED0CC2B6124D01C10E668D214F942C41EA9C09EB8AD000C17C6ED6D784992C416AF030DFAA5300C1090ADB412F9E2C41D2E82DA0F8ACFFC0464077024EA22C419DDA730112B2FEC07D266BC7E0A52C41942FE972B5B6FDC0A2496149E7A82C4148BD758EF6BAFCC0593EF44B61AB2C418769ACF5E8BEFBC0A656B39D4EAD2C4158454350A0C2FAC0E77C2618AFAE2C416B2D8B4A30C6F9C0C433D19F82AF2C41A30EE793ACC9F8C0E8BA3424C9AF2C414FED42DD28CDF7C04858D19F82AF2C41BCCD8AD7B8D0F6C0EDC52618AFAE2C41CF9C213270D4F5C028C4B39D4EAD2C413837589962D8F4C04ED0F44B61AB2C41FFADE4B4A3DCF3C0FFFF6149E7A82C41F6E6592647E1F2C034016CC7E0A52C41AFB79F8760E6F1C0463F78024EA22C418B996B6903ECF0C03D2DDC412F9E2C41B92A74A386E4EFC0CEB5D7D784992C413B0A927467F2EDC065D18E214F942C411C94251ED001ECC0CB4202878E8E2C41352B9559E712EAC0F57A077B43882C4184C6B3BED325E8C096A43F7B6E812C413983BEC0BB3AE6C036D80D10107A2C411C115DABC551E4C07C798CCC28722C412835A59F176BE2C09DBE814EB9692C41009E2191D786E0C0B062533EC2602C41078BB885564ADDC00384F94E44572C415C35D988708CD9C058AFF03D404D2C41FF5C13DE47D4D5C031192BD3B6422C41C93C41C52622D2C0540601E1A8372C4123D9BD0BAEECCCC0AC642044172C2C41681093D243A2C5C0EA957BE302202C413EB120D440CBBCC0216D37B06C132C411BD7F92851DDACC0D96098A555062C4127FFB1DCCCEE47C00BF3EEC8BEF82B41B64F337707E0AB4085508329A9EA2B417C4F0774E1EFBB405A2980E015DC2B41506F990B52E7C440F8C3DC1006CD2B411C6FD1609BC5CB40A54C46E77ABD2B410A2596CE2149D1401A63089A75AD2B41B2920C8261A6D44024E8F468F79C2B414CADC5A149FAD740170D4B9D018C2B4172F239BF9744DB401AA79D89957A2B4139DC8E2B0A85DE4037C8B889B4682B413A0D5BFEAFDDE04058A0860260562B41A3B93E89AC73E24033A8F36199432B410773C70D5B04E4406918D21E62302B415C56304D9C8FE540FEAEBCB8BB1C2B41885C0A755115E7407FC5F8B7A7082B414AA6A3215C95E84024BA57AD27F42A41872566609E0FEA4053AE17323DDF2A418F742DB2FA83EB40F79CC3E7E9C92A41D6AC930D54F2EC401DCB12782FB42A41220F35E18D5AEE407195C7940F9E2A41FF4FEA158CBCEF40299D8DF78B872A4107AE7C88198CF040F756D761A6702A412F341EDBB336F140CFFEBA9C60592A41F1911FB507DEF14015F3CE78BC412A41F0EF280A0882F240247A05CEBB292A41E2424910A822F340DAF4877B60112A41F298F540DBBFF3402A819167ACF82941A425035A9559F440820F497FA1DF2941C0F89B5ECAEFF44013EE9AB641C62941314D2E986E82F540DECC11088FAC2941255D56977611F640B13DAF748B92294141A9C234D79CF6400BB3C3033978294111A112928524F7401A01C6C2995D2941579BAF1A77A8F740EF632AC5AF422941540DA084A128F840220E39247D27294193F054D1FAA4F8401D43E4FE030C29412347714E791DF94053009E7946F02841C8AE8B961392F940AF382DBE46D42841F4F3E991C002FA409AA582FB06B8284100963677776FFA40E2308D65899B28415D2E30CC2FD8FA4001FB0D35D07E284133AD5266E13CFB401E016CA7DD612841215E7A6B849DFB40496687FEB344284173A8805211FAFB4064638C8055272841987ED2E38052FC404EE1C577C40928410E71003ACCA6FC40C3C06F3203EC27419C5948C2ECF6FC409AD3880214CE27410C94183DDC42FD40E28AA43DF9AF274136BA8CBE948AFD40895DBC3CB59127419BD9E3AE10CEFD402CEB005C4A7327415819F0CA4A0DFE40B5DEAAFABA542741C1C77F243E48FE407294CB7A0936274170C7BF22E67EFE405F871D41381727411A5497823EB1FE404F89D4B449F826410318FD5643DFFE40B1C96D3F40D926416F8B4509F108FF40B1AE7F4C1EBA2641F6976A59442EFF4077848949E69A26411D7A4C5E3A4FFF404206C3A59A7B26412FDCEB85D06BFF402CC5EBD13D5C2641C2259D950484FF4060701A40D23C2641F9FB34AAD497FF4090028C635A1D2641F4EE2D383FA7FF4077D872B0D8FD25419651C70B43B2FF4035B4C59B4FDE254124391D49DFB8FF4060B10E9BC1BE2541ECA2396C13BBFF40E8BA3424319F2541',
'0103000020E80A0000010000001B0000003731C25DB7A40AC123BABA3D2F2E1541482DDA6520AE15C150176B846E0E04419D9BAD51D2DD20C188B238C6A20F1341C93BA6B63EF616C1773C690356B72041AFE718BD3DE01AC1363F67295618224104666722A81614C128DF2B476DE92641E3BF74CA1BBCF1C0D43292B68C652141BDD1D74AAFA6CCC01D27263DE8A122418FF95A96AD86C240BA1AA7079685274134285EE6E81EF9C040F2AA56B1AF2C4117B1B91CDC81FA40E8363289617C3041DF296F1F14800941806416C77A5C2C4143DE3E9BAE901A41E5DD836A7C8E2E413E4390CBBBDE1E41DCBAED0B9BC82741489E9ED935770A41535871C71BFB2441A247FE423D360841CDF36716539B2441ECC1420680470741BD3D4C94710F23414D024D7D04380A41FEC5364D1A022241407DA7BAAF811D41DD0784C658ED184192B08CF1A618184108E3295E56ED104121896F9066610541F13A975D57FE1941096E8D134BEBFB406847DAE3D9661741AABE21A245A00B41845A019F2304FF40E48112BC1AF0F84080891F1A39C7F140DD811CEEB3B3EF40AE82AE28194B0341AB6F85D09F3409C1B06BA7169F6201413731C25DB7A40AC123BABA3D2F2E1541');

SELECT isvalid(a) as a_valid, isvalid(b) as b_valid from test;

-- This works, which is precision reduction on geometry B 
-- introduced by 'astext' is enought to get the exception away
SELECT geometrytype(difference(setSRID(a, -1),astext(b))) from test;

-- This throws the exception:
-- TopologyException: no outgoing dirEdge found (-102895,939993)
SELECT difference(a,b) from test;