[jts-dev] TopologyException: found non-noded intersection

[Felix Obermaier <obe@xxxxxxxxxxxxx>]

Hello list,

On NTS Google groups came up with two polygons that, when doing a difference operation, threw a TopologyException.
https://groups.google.com/forum/#!topic/nettopologysuite/6YTDe0pMMgI

Polygon 1:
"MULTIPOLYGON (((636192.59787309519 6154321.6995911133,
636182.897398793 6154321.8655825993,
636173.596086427 6154322.1355276527,
636167.86522464128 6154325.0849273112,
636161.6231205092 6154326.6646057721,
636160.17831999587 6154326.7813923974,
636161.62312051 6154326.66460577,
636167.86343093 6154325.08425578,
636173.59608643 6154322.13552765,
636182.89523056 6154321.86485684,
636185.751571696 6154321.8162046,
636192.59787309519 6154321.6995911133)),
((636152.84859301744 6154319.8801070936,
636153.02270491 6154322.12552969,
636154.630037279 6154324.02402822,
636157.17036459 6154327.02453251,
636157.17036458931 6154327.02453251,
636153.02270490839 6154322.1255296879,
636152.84859301744 6154319.8801070936)),
((636211.11390913755 6154314.0155097777,
636211.114677974 6154314.0171801187,
636207.437031418 6154321.4456680715,
636207.43681213306 6154321.4456718238,
636211.11390913755 6154314.0155097777)),
((636203.68238669413 6154308.2698675757,
636208.89654585847 6154309.1981610162,
636209.84867722925 6154311.2667209692,
636208.89554388 6154309.19807967,
636203.68238669413 6154308.2698675757)),
((636172.16130951955 6154302.44953468,
636178.5428774301 6154303.7584576393,
636172.16345147 6154302.45243773,
636158.325838736 6154303.24290477,
636158.1491036 6154303.25300068,
636157.253171342 6154304.03329127,
636152.6634752 6154308.0305764,
636152.581231977 6154315.22303587,
636152.56918352365 6154316.2767155087,
636152.65988775936 6154308.0283991182,
636158.15162006055 6154303.2493718751,
636172.16130951955 6154302.44953468)))

Polygon 2:
MULTIPOLYGON (((636167.79101204267 6154298.2703853333,
636168.33523776615 6154298.2803832982,
636170.65232001338 6154298.4203548077,
636170.69354923489 6154298.4303527726,
636171.18829989259 6154298.4703446319,
636173.33221940952 6154298.7302917205,
636173.42292369681 6154298.7502876511,
636174.0083786418 6154298.8402693355,
636174.02487033047 6154298.8502673,
636176.01211880578 6154299.2501858976,
636176.56459037366 6154299.3701614775,
636177.13355363009 6154299.5501248464,
636177.521108312 6154299.690096355,
636179.05483535107 6154300.2899742518,
636179.219752237 6154300.3499620417,
636179.75573211617 6154300.5999111654,
636180.27522030682 6154300.8698562188,
636180.76997096464 6154301.1897910973,
636180.976117072 6154301.3197646411,
636182.44387735671 6154302.3595529953,
636182.71599021845 6154302.5695102587,
636183.177757499 6154302.9394349623,
636183.60654140241 6154303.33935356,
636184.01058777294 6154303.7692660522,
636184.38165076624 6154304.2291724393,
636184.72797622671 6154304.7090747571,
636184.85528403521 6154304.9176677912,
636179.86541827 6154304.02921314,
636172.16345147 6154302.45243773,
636158.325838736 6154303.24290477,
636158.1491036 6154303.25300068,
636157.253171342 6154304.03329127,
636152.6634752 6154308.0305764,
636152.581231977 6154315.22303587,
636152.56918347 6154316.2767202,
636153.02270491 6154322.12552969,
636154.630037279 6154324.02402822,
636157.17036459 6154327.02453251,
636157.518183773 6154326.99641747,
636161.62312051 6154326.66460577,
636167.86343093 6154325.08425578,
636173.59608643 6154322.13552765,
636182.89523056 6154321.86485684,
636184.8490700468 6154321.8315769676,
636184.60428856232 6154322.2854971271,
636184.46410920925 6154322.525448286,
636183.4416245165 6154324.1751125008,
636183.2767076306 6154324.4350595893,
636182.93038217013 6154324.9149619071,
636182.55931917683 6154325.3748682942,
636182.1552728063 6154325.8047807869,
636181.72648890293 6154326.204699385,
636181.26472162234 6154326.5746240877,
636180.7864626532 6154326.9145548958,
636180.29171199538 6154327.2344897734,
636179.77222380473 6154327.5044348277,
636179.70625705039 6154327.5444266871,
636178.88167262077 6154327.9343473194,
636176.35019842186 6154329.2740746224,
636176.11931478162 6154329.3940502014,
636175.58333490242 6154329.6439993251,
636175.03086333454 6154329.8439586237,
636174.46190007811 6154330.0239219926,
636173.89293682168 6154330.1538955374,
636173.30748187669 6154330.2438772218,
636172.7220269317 6154330.3038650118,
636172.202538741 6154330.3238609415,
636170.808991055 6154330.3338589063,
636170.74302430055 6154330.3338589063,
636170.41319052875 6154330.3338589063,
636168.17032088025 6154330.2438772218,
636167.634341001 6154330.2538751867,
636163.00017650658 6154331.173687961,
636162.4147215616 6154331.2636696463,
636162.18383792136 6154331.2936635409,
636157.70634446852 6154331.7635678928,
636157.35177316377 6154331.7935617883,
636156.76631821878 6154331.8135577179,
636156.1808632738 6154331.7935617883,
636155.59540832881 6154331.7335739983,
636155.00995338371 6154331.6435923139,
636154.44099012727 6154331.5036208043,
636154.02869791246 6154331.39364319,
636152.30531645461 6154330.8437551185,
636152.148645413 6154330.7837673286,
636151.59617384523 6154330.58380803,
636151.06019396591 6154330.3338589063,
636150.54070577526 6154330.0639138529,
636150.04595511756 6154329.7439789744,
636149.5676961483 6154329.4040481662,
636149.10592886782 6154329.0341234636,
636148.67714496434 6154328.6342048654,
636148.56170314422 6154328.5142292865,
636148.05046079785 6154327.9843371445,
636147.76185624755 6154327.6744002309,
636147.39079325413 6154327.2144938437,
636147.04446779378 6154326.7345915269,
636146.73937155481 6154326.2346932795,
636146.45901284879 6154325.7147991024,
636146.23637505271 6154325.2348967856,
636145.69214932923 6154323.9451593077,
636145.67565764056 6154323.8851715177,
636145.46126568888 6154323.3352834461,
636145.296348803 6154322.7753974088,
636145.27985711442 6154322.7254075846,
636144.71913970227 6154320.5858430862,
636144.60369788215 6154320.0659489091,
636144.50474775059 6154319.5160608375,
636144.38106008607 6154318.6062460281,
636144.38106008607 6154318.5662541678,
636144.348076709 6154318.3163050441,
636144.16666813439 6154316.4966754252,
636144.05947215855 6154315.5468687555,
636144.02648878144 6154315.1569481222,
636144.00999709277 6154314.5670681912,
636144.02648878144 6154313.9771882594,
636144.0842096915 6154313.3873083275,
636144.18315982306 6154312.80742636,
636144.31509333174 6154312.2375423592,
636144.36456839752 6154312.05757899,
636144.405797619 6154311.6776563218,
636144.50474775059 6154311.0877763908,
636144.55422281637 6154310.847825232,
636144.81808983383 6154309.6880612988,
636144.90054827684 6154309.3581284555,
636145.06546516274 6154308.798242419,
636145.27985711442 6154308.2483543465,
636145.51898659894 6154307.70846424,
636145.79934530507 6154307.1885700626,
636146.104441544 6154306.6886718152,
636146.12917907687 6154306.6586779207,
636147.300088967 6154304.9190320205,
636147.62167689449 6154304.4691235982,
636147.99273988779 6154304.009217211,
636148.39678625832 6154303.5793047184,
636148.5699489885 6154303.4193372792,
636149.55120445974 6154302.4895265391,
636149.80682563293 6154302.2495753812,
636150.26859291352 6154301.8796506776,
636150.74685188266 6154301.53971987,
636151.24160254048 6154301.2197849918,
636151.76109073113 6154300.9498399384,
636152.04144943715 6154300.8098684289,
636153.32780114736 6154300.2299864627,
636153.58342232055 6154300.1200088477,
636154.13589388831 6154299.9200495491,
636154.70485714474 6154299.74008618,
636154.91100325214 6154299.690096355,
636155.94173378916 6154299.4401472323,
636156.30455093819 6154299.3601635126,
636156.8900058833 6154299.2701818282,
636157.12088952353 6154299.2401879327,
636159.77605138684 6154298.9602449145,
636160.056410093 6154298.93025102,
636164.47618263564 6154298.6103161415,
636166.69431475119 6154298.3403710881,
636167.20555709756 6154298.290381263,
636167.79101204267 6154298.2703853333)))

I tested with the latest JTS version and the problem is there, too. 

While using GeometryPrecisionReducer solves the issue, I was wondering whether inserting the topology-exception location coordinate into the input coordinates would solve the problem, too.
So I did a quick proof of concept for the problem at hand and found out it worked. 
(https://groups.google.com/group/nettopologysuite/attach/c9b8d04e0ec55/TopologyExceptionCatch.cs?part=0.1&authuser=0&view=1). Has anyone already persued this approach and dismissed it, or is there some interest in modifying it to viable solution?

Felix Obermaier

------------------------------------------
Ingenieurgruppe IVV GmbH & Co. KG
Dipl.-Ing. Felix Obermaier
Oppenhoffallee 171
52066 Aachen

Telefon: +49 (241) 94691-39
Telefax: +49 (241) 531622
eMail: obe@xxxxxxxxxxxxx
Internet: http://www.ivv-aachen.de

Sitz der Gesellschaft: Aachen
Amtsgericht Aachen HRA 6212
Geschäftsführer:
Dipl.-Ing. Wolfgang Hölsken
Dr.-Ing. Stephan Krug
Dr.-Ing. Dirk Serwill
IVV-Management GmbH
Amtsgericht Aachen HRB 12453