Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

How to avoid problem with ConcaveHull? #716

Open
Evgeny1303 opened this issue Oct 5, 2023 · 4 comments
Open

How to avoid problem with ConcaveHull? #716

Evgeny1303 opened this issue Oct 5, 2023 · 4 comments

Comments

@Evgeny1303
Copy link

I use NetTopologySuite.Algorithm.Hull.ConcaveHull.ConcaveHullByLengthRatio (Geometry geom, double lengthRatio, bool isHolesAllowed) to build a concave hull. Sometimes the function works fine, but sometimes it falls with an exception:

NetTopologySuite.Triangulate.QuadEdge.LocateFailureException: Locate failed to converge (at edge: LINESTRING( 38.52788223 59.20800324999999, 38.529696464538574 59.20393475499401)).  Possible causes include invalid Subdivision topology or very close sites
         at NetTopologySuite.Triangulate.QuadEdge.QuadEdgeSubdivision.LocateFromEdge(Vertex v, QuadEdge startEdge)
         at NetTopologySuite.Triangulate.QuadEdge.LastFoundQuadEdgeLocator.Locate(Vertex v)
         at NetTopologySuite.Triangulate.IncrementalDelaunayTriangulator.InsertSite(Vertex v)
         at NetTopologySuite.Triangulate.IncrementalDelaunayTriangulator.InsertSites(ICollection`1 vertices)
         at NetTopologySuite.Triangulate.DelaunayTriangulationBuilder.Create()
         at NetTopologySuite.Triangulate.DelaunayTriangulationBuilder.GetSubdivision()
         at NetTopologySuite.Algorithm.Hull.HullTriangulation.CreateDelaunayTriangulation(Geometry geom)
         at NetTopologySuite.Algorithm.Hull.ConcaveHull.GetHull()
         at NetTopologySuite.Algorithm.Hull.ConcaveHull.ConcaveHullByLengthRatio(Geometry geom, Double lengthRatio, Boolean isHolesAllowed)

lengthRatio is 0.2 (I've tried to use values from 0.1 to 1.0 - nothing changed), isHolesAllowed is true.

geom is MultiPoint containing coordinates, for example .

What should I do to avoid such behaviour of the function and get the correct concave hull geometry?
@FObermaier
Copy link
Member

I can't reproduce your issue with the current code in this repository:

const string WKT = "MULTIPOINT((38.304000189460474 59.18059265130876), (38.55351779119629 59.227983784250405), (38.39688109797687 59.36200579912337), (38.50221484400682 59.23510036844686), (38.51739331280218 59.20678543240145), (38.509951785704615 59.23134783733542), (38.37586340772256 59.215316243022684), (38.534758 59.211099), (38.51672084836604 59.20725220939938), (38.4816134709033 59.22364164963281), (38.50968520766368 59.2211483547392), (38.38724552851707 59.26836618370752), (38.60756499015031 59.28042553120765), (38.26649365293311 59.220299653358566), (38.51962583962711 59.204695957901556), (38.47844925903793 59.21480008836715), (38.51274783879646 59.2203500189283), (38.60554509713967 59.33654578671183), (38.505072484488934 59.2359971174807), (38.50382226411005 59.20631780143436), (38.458690520089704 59.21550003459099), (38.50794469836 59.217555232046024), (38.61602650050486 59.346951147556354), (38.42770913133627 59.242292959176204), (38.506955395216174 59.238744385845045), (38.518678041714566 59.234756511812726), (38.460392666861935 59.212782731161546), (38.50287053359995 59.210669930701016), (38.47948084547161 59.227857170003695), (38.475513807924415 59.2309362206018), (38.527055797994535 59.20747920573016), (38.512312537525375 59.224501798403665), (38.49170940819879 59.20549932301839), (38.58342693926955 59.26416991974461), (38.37756117592969 59.21364110446784), (38.52277506398457 59.20159691998894), (38.5090208322425 59.23287617467618), (38.50970171535238 59.2051148836398), (38.47603726347094 59.20219136810383), (38.57549283259245 59.261943264677456), (38.37220982877829 59.21753081612), (38.500502981892645 59.20594071106237), (38.5164817794306 59.2368007527138), (38.51727884679164 59.22844851133605), (38.47315942447604 59.199975918814424), (38.28562464566037 59.267949566294796), (38.506861523508846 59.238721891282395), (38.504184839957674 59.20814142148925), (38.49548057591101 59.20712942424032), (38.52662909173429 59.230846255695205), (38.47185918288039 59.197307572449866), (38.280968330809 59.267733990304485), (38.517259202352 59.20679093490027), (38.49462693004787 59.20642869970415), (38.82977751877886 59.19209382227612), (38.466047121369854 59.197786709463834), (38.26229388538454 59.17452604289841), (38.508981232232614 59.232967279020656), (38.52949131535662 59.20032293410691), (38.51510947207761 59.22389905168978), (38.83045040126567 59.19895547028192), (38.515666899119736 59.21082526996209), (38.55371143669681 59.21236556754353), (38.523218462153196 59.22962823662199), (38.52723033727562 59.22656817208639), (38.52077767092027 59.23043911703846), (38.83807620479286 59.20215069377391), (38.53478415069359 59.2110401880392), (38.42848982662716 59.24077357740069), (38.513533813081395 59.21692411707774), (38.515110602956554 59.23358086113831), (38.82408932126952 59.19592777345708), (38.538221613858205 59.22794296969757), (38.686227570702094 59.13056015555621), (38.511989669732706 59.21389564741809), (38.517093834317 59.204530880140005), (38.82308634136045 59.20446918940994), (38.5419616901156 59.2299618962702), (38.258673362271345 59.153625848377445), (38.49770732655306 59.207096301579064), (38.514995966304674 59.23810116695171), (38.8289547955201 59.20714005314176), (38.54316459680649 59.2291585987526), (38.26343480317622 59.155227800741486), (38.56769370503677 59.199232483222076), (38.826819843542864 59.196846082934506), (38.51615649434612 59.23159957775831), (38.627480231229555 59.379240561824766), (38.496266657598625 59.20463488333583), (38.56829585209978 59.19954000212122), (38.83213324446607 59.201875501770274), (38.56017918354331 59.210666916813736), (38.92701055855268 59.12920500871117), (38.520919925147574 59.20645422052987), (38.5596574640106 59.198000656386746), (38.83127868267636 59.188825879019625), (38.682980415259316 59.132982530350986), (38.59021069997384 59.266511660204706), (38.51118898825985 59.23424008483084), (38.509517267844686 59.23133134279432), (38.83623576083761 59.19366271745896), (38.68296875412818 59.13279161565055), (38.59222052009193 59.25879616147143), (38.512017593309764 59.208063412199586), (38.533009311884314 59.20738776289472), (38.81640643592429 59.19769094749021), (38.485806300460595 59.221860627891246), (38.49868379448223 59.192986351590875), (38.52788222781523 59.20800324897682), (38.53177088204371 59.20431077307884), (38.84138776885046 59.19954728083175), (38.587066916663204 59.265246071120586), (38.6147424206161 59.16556107828804), (38.51087837912599 59.22936583199069), (38.526240167056564 59.20290894990715), (38.83407327912713 59.19039005370243), (38.47011693778688 59.21617224093288), (38.50804198740799 59.23978017243689), (38.27015356248703 59.21093146343698), (38.42329575792519 59.251664151414026), (38.499463124425496 59.205909696250885), (38.472010686806925 59.21536017501939), (38.518719937528864 59.22187543012061), (38.26988456217145 59.21143693697829), (38.58923461288397 59.2477097462105), (38.51233337182153 59.203091641164704), (38.475062663439346 59.21604053328458), (38.50562470856753 59.21276177101966), (38.4639929751423 59.17683138121632), (38.475051419200845 59.51031981804958), (38.510690059924784 59.227763921398996), (38.473735996189966 59.213249914188516), (38.50688418543109 59.22768300734059), (38.77353486014087 59.10740165880056), (38.60800487243036 59.27702685286727), (38.509802911303524 59.23828331383859), (38.47732018799036 59.21797046182998), (38.509315428171675 59.2238766403924), (38.60762399874855 59.279596482246866), (38.38361752426529 59.20984505285797), (38.49333353084641 59.202732170365316), (38.540428060318156 59.208299936539575), (38.50852149430273 59.22559243138417), (38.4712060501754 59.21955527883141), (38.52780121270397 59.204883044461326), (38.54032176438184 59.230970215182715), (38.539028479923026 59.22854802248885), (38.7075750111547 59.16130138748632), (38.73239582071643 59.15454234400364), (38.463934564525715 59.22603235204484), (38.54194162256774 59.20814626635703), (38.51541662187084 59.14509280719818), (38.6158546486266 59.34066131733952), (38.77058445041102 59.16109396793038), (39.002886740485266 59.122004556868774), (38.55310951572269 59.22745785255337), (38.59401056738276 59.2697009897691), (38.8304504 59.19895547), (38.83213324 59.2018755), (38.47732019 59.217970460000004), (38.475252985954285 59.21702341692662), (38.47506266 59.21604052999996), (38.47011694 59.21617224), (38.47201069 59.21536018), (38.55310951999999 59.22745785000001), (38.54352593421936 59.22732688096778), (38.53822161 59.22794296999999), (38.5431646 59.229158600000005), (38.542721271514885 59.230329356553085), (38.540321760000005 59.230970220000046), (38.53822161 59.22794296999999), (38.538291603326805 59.22798926997075), (38.54191862046719 59.22994694326039), (38.54196169 59.229961900000006), (38.53822161 59.22794297), (38.54196169 59.2299619), (38.47506266 59.21604052999996), (38.47467362880707 59.21610642671237), (38.472490310668945 59.215192157452776), (38.47201069 59.215360180000005), (38.54316459680649 59.229158598752605), (38.539028479923026 59.228548022488866), (38.539028479923026 59.228548022488866), (38.538886442878585 59.22855646397562), (38.53810102975622 59.22802196764627), (38.5382216138582 59.22794296969758), (38.56769371 59.199232480000006), (38.5680828988552 59.19931106010236), (38.56829585 59.19954000000001), (38.50382226 59.206317799999965), (38.50362271070479 59.206066655601234), (38.50103437900542 59.20569727301586), (38.50050298 59.20594070999999), (38.511677384376526 59.23277313268906), (38.51140379905701 59.234013477625524), (38.51118899 59.234240080000006), (38.51739331 59.20678543), (38.5172592 59.20679093), (38.50050298 59.20594071), (38.49946312 59.2059097), (38.51739331 59.20678543), (38.51774990558625 59.206745677476306), (38.517159819602966 59.205158296833275), (38.51726174354553 59.205034708738935), (38.51709383 59.20453087999999), (38.55965745999999 59.19800065999999), (38.53233575820923 59.203863346035575), (38.529696464538574 59.20393475499401), (38.52780121000001 59.20488304), (38.51739331 59.20678543), (38.51733148097992 59.20687406533213), (38.51666361093521 59.20693997548773), (38.51672084999999 59.20725221000001), (38.51739331 59.20678543), (38.51763993501663 59.20682016995411), (38.51790815591812 59.20678927447614), (38.51762384176254 59.20603644602306), (38.518270254135125 59.20596160854393), (38.50995179 59.23134784), (38.50951727 59.23133134), (38.51739331 59.20678543), (38.51730197668075 59.206826005763475), (38.51611375808716 59.206949587374766), (38.515963554382324 59.20638591428195), (38.51413965225219 59.20650400490868), (38.51369440555572 59.20573778171004), (38.51136624813079 59.206031639951334), (38.510668873786926 59.20596572804246), (38.510255813598626 59.205070412012134), (38.509701719999995 59.205114879999996), (38.51069006 59.22776392), (38.5112589597702 59.22704830151034), (38.511940240859985 59.22655426338116), (38.51231254 59.224501799999985), (38.51739331 59.20678543), (38.51751307059479 59.20683162677443), (38.5176882147789 59.20686857281342), (38.52053940296173 59.20655412464424), (38.520919930000005 59.20645422000001), (38.50995179000001 59.23134784000001), (38.50991651415824 59.2313508481441), (38.509548716247075 59.231336612135294), (38.50951727000001 59.23133134), (38.50995179000001 59.23134784000001), (38.50992321968079 59.23158213957504), (38.511226773262024 59.23161781508813), (38.511216044425964 59.23184010013688), (38.511763215065 59.231856565638395), (38.51167738 59.23277313), (38.50995179000001 59.23134784000001), (38.513259887695305 59.231470996391266), (38.51398944854737 59.225913375482406), (38.51465463638305 59.22591063075464), (38.51707935333251 59.22520797317196), (38.51693987846373 59.2224356282633), (38.51871994 59.22187543000001), (38.50995179000001 59.23134784000001), (38.51014316082 59.23145384463314), (38.514904081821435 59.231628106094604), (38.51615649 59.231599579999994), (38.5069554 59.23874439), (38.50686152 59.23872189), (38.50221484 59.23510037), (38.50219577550889 59.23514547597344), (38.501341827213764 59.239317278513994), (38.50774560123682 59.23976620518724), (38.50804199 59.23978017000002), (38.509701719999995 59.205114879999996), (38.50936532020568 59.205251674207915), (38.507777452468865 59.20672508044913), (38.50790619850159 59.207300419400696), (38.50418484 59.208141420000004), (38.50995179000001 59.23134784000001), (38.50962817668915 59.23158282564296), (38.509346544742584 59.23241981821752), (38.50902083 59.23287616999997), (38.51739331 59.20678543), (38.51751118898392 59.20690427416923), (38.52063864469528 59.206570602349444), (38.520721793174744 59.20670654311411), (38.52281928062438 59.20647654200869), (38.524911403656 59.206204658106884), (38.529857397079475 59.205538670716805), (38.53227138519288 59.20502234990488), (38.56168448925018 59.19998094581592), (38.56735467910766 59.19865008874331), (38.56777846813202 59.19914590430173), (38.56769371 59.199232480000006), (38.50995179000001 59.23134784000001), (38.50992053747177 59.231249395011986), (38.50958526134491 59.231237045666774), (38.509665727615356 59.23043844518375), (38.510347008705125 59.23045148090873), (38.51063132286072 59.228697788113436), (38.51069006 59.22776392), (38.5069554 59.238744389999994), (38.50741267204285 59.23879126542957), (38.50750654935837 59.23860469388421), (38.508882522583015 59.23874187894336), (38.50980291 59.238283309999986), (38.50995179000001 59.23134784000001), (38.50996881723404 59.2311821596339), (38.5096362233162 59.23117255456907), (38.50965768098831 59.23099280214274), (38.51033091545106 59.23101064021213), (38.510465025901794 59.23009265360761), (38.51072520017624 59.230100886781116), (38.51087838 59.229365830000006), (38.50221484 59.23510037), (38.50135087966918 59.23931324877876), (38.50804199 59.23978017000002), (38.50418484 59.208141420000004), (38.50407600402832 59.20780846721689), (38.50329279899597 59.20682531919775), (38.500535488128655 59.206317256753096), (38.50064411759377 59.206099268183976), (38.50050298 59.20594070999999), (38.50507248 59.23599711999998), (38.50528299808502 59.23641445968073), (38.5069888830185 59.23786045532094), (38.50689768791197 59.23849974694144), (38.5069554 59.238744389999994), (38.49770733 59.2070963), (38.49548058 59.20712942), (38.51353381 59.21692411999999), (38.51319015026092 59.21665003466299), (38.51198967 59.213895649999984), (38.50995179000001 59.23134784000001), (38.5101243853569 59.231401703235434), (38.514566123485565 59.23156910428213), (38.51727885 59.22844850999999), (38.49770733 59.2070963), (38.49462693 59.2064287), (38.51069006 59.22776392), (38.51095050573349 59.227779053126596), (38.51084053516388 59.228708080000786), (38.51087838 59.229365830000006), (38.51118899 59.234240080000006), (38.51013243198394 59.23430160439628), (38.51002514362335 59.23465284135813), (38.505862355232246 59.234285140074945), (38.50507248 59.23599711999998), (38.51118899 59.234240080000006), (38.5115110874176 59.234090311669036), (38.51283073425292 59.2340820794584), (38.51288974285125 59.23372260432154), (38.51382851600647 59.23374181301244), (38.5151106 59.23358085999999), (38.52788223 59.20800325), (38.5270558 59.20747921), (38.49626666 59.204634879999986), (38.49583894014358 59.204715437424966), (38.49503025412559 59.20434912999312), (38.49504634737968 59.20418640171977), (38.49481701850891 59.20409885770766), (38.49427789449691 59.2035935012193), (38.494021743535995 59.20352998781644), (38.493902385234826 59.20341085695301), (38.49333353 59.20273217000002), (38.49462693 59.20642870000003), (38.49450051784515 59.206355018411045), (38.492631018161774 59.205886770900776), (38.49170941 59.20549932), (38.50902083 59.23287617), (38.50898123 59.23296728), (38.512017590000006 59.208063409999994), (38.50983202457428 59.20768214252007), (38.509665727615356 59.20745695385793), (38.50379705429078 59.208681742555314), (38.50342690944671 59.208346715034736), (38.501989245414734 59.20834946117532), (38.499253392219536 59.20789634499121), (38.49769234657287 59.20791282204871), (38.49714517593383 59.207802974848505), (38.497707330000004 59.20709629999999), (38.51672084999999 59.20725221000001), (38.51486384868622 59.20781121340079), (38.512017590000006 59.208063409999994), (38.50980291 59.238283309999986), (38.51035237312317 59.2372280112607), (38.514955043792725 59.2375586396619), (38.51648178 59.236800749999986), (38.51233337 59.203091640000025), (38.51100146770476 59.203210359114934), (38.51112216711043 59.20357152902844), (38.50867331027984 59.20424922728432), (38.50881814956664 59.204534858994606), (38.5054224729538 59.205029902526235), (38.50382226 59.206317799999965), (38.51739331 59.20678543), (38.51699352264404 59.20576799155245), (38.515453934669495 59.205935518375014), (38.51440787315369 59.203540630611144), (38.51307213306426 59.20365049152352), (38.51298630237579 59.20337034549843), (38.51141184568406 59.20349462624904), (38.51137161254883 59.2033463132569), (38.51238548755645 59.20326254359705), (38.51233337 59.203091640000025), (38.51827025 59.20596161), (38.51981788873672 59.205779663529825), (38.51940751075744 59.20481430886062), (38.51962584000001 59.20469595999998), (38.51867804 59.23475651000001), (38.51863771677017 59.23478138152001), (38.518235050141804 59.23508853823711), (38.51716183125972 59.23498323747427), (38.51610034704208 59.23402231011926), (38.515162914991386 59.233599891402434), (38.5151106 59.23358085999999), (38.49333353 59.20273217000002), (38.4930145740509 59.202873904618315), (38.49388629198074 59.20347540052717), (38.493838012218475 59.20460146027588), (38.494575619697564 59.20496948150881), (38.49429666996002 59.20530316897438), (38.494369089603424 59.20557231369031), (38.4941303730011 59.20588402456215), (38.49490821361542 59.20605429714067), (38.49462693 59.20642870000003), (38.51867804 59.23475651000001), (38.51823806762695 59.23509256847157), (38.51715713739395 59.234986924721426), (38.51609230041503 59.23402445392807), (38.5151106 59.23358085999999), (38.51648178 59.236800749999986), (38.51612448692322 59.237665647337536), (38.51499597 59.23810116999999), (38.51867804 59.23475651000001), (38.51863905787468 59.23483909152182), (38.51825550198556 59.23512378133512), (38.517583608627326 59.235058268588574), (38.51741731166839 59.235467806938715), (38.51669311523437 59.23540469582164), (38.51660192012787 59.2356701733199), (38.516478538513184 59.23566056951876), (38.51624250411987 59.236466593416225), (38.51648178 59.236800749999986), (38.520919930000005 59.20645422000001), (38.5229480266571 59.2062101507324), (38.522368669509895 59.20488640243531), (38.52599501609802 59.20447718355331), (38.52780121000001 59.20488304), (38.51962584000001 59.20469595999998), (38.51956576108932 59.204852758786046), (38.51964622735977 59.20504775417001), (38.520145118236535 59.20499419921069), (38.52047234773635 59.205849695310405), (38.52069228887558 59.205941697627395), (38.520919930000005 59.20645422000001), (38.51648178 59.236800749999986), (38.516441322863095 59.23687791550486), (38.516116105020046 59.23766298929837), (38.515032157301896 59.23808244246308), (38.51499597 59.23810116999999), (38.50902083 59.23287616999997), (38.50939214229583 59.232788911696616), (38.51333498954773 59.232905538917294), (38.51391166448593 59.233115466909595), (38.51705253124237 59.233277371276046), (38.518514335155494 59.2332320930137), (38.51881206035614 59.233868041283614), (38.51867804 59.23475651000001), (38.49946312 59.20590969999998), (38.49932849407196 59.20602340096971), (38.495943546295166 59.2053278864347), (38.4963458776474 59.20481430886062), (38.49626666 59.204634879999986), (38.51510947 59.22389905), (38.5145741701126 59.22259826956744), (38.513522744178765 59.22272042159844), (38.512597382068634 59.22064926790705), (38.513647466897964 59.22052058870429), (38.513463735580444 59.21995267869357), (38.51439177989959 59.21947226405527), (38.5134369134903 59.21706185310424), (38.51353381 59.21692411999999), (38.520919930000005 59.20645422000001), (38.52079689502716 59.20660287116581), (38.52111876010895 59.20750363943432), (38.524157702922814 59.20715143637801), (38.52528154850006 59.207621726195526), (38.52667629718781 59.2076272185931), (38.52666020393372 59.207986968709065), (38.52788223 59.20800324999999), (38.49548058 59.20712942), (38.49545538425446 59.20685896090356), (38.496270775794976 59.20584694896877), (38.49532127380371 59.20564646543312), (38.495503664016724 59.20540890465148), (38.49575042724609 59.20545833940119), (38.49623322486877 59.204826667769964), (38.49626666 59.204634879999986), (38.52780121000001 59.20488304), (38.52586627006529 59.205115727651275), (38.52681040763854 59.207268837800456), (38.5270558 59.20747921), (38.56769371 59.199232480000006), (38.56777042150499 59.199212430253), (38.56845572590828 59.19906358362263), (38.56793001294135 59.19839247813019), (38.566209711134434 59.19878168315182), (38.559788502752774 59.19802078061929), (38.55965745999999 59.19800065999999), (38.5151106 59.23358085999999), (38.51623713970185 59.23345642563399), (38.51630687713623 59.232720993307936), (38.51899445056916 59.23182363462735), (38.51880133152008 59.23105523534477), (38.52077767000001 59.23043912), (38.56769371 59.199232480000006), (38.56776170432567 59.199241873310115), (38.56808926910161 59.19930805571602), (38.568275347352014 59.19950797559014), (38.56829585 59.19954000000001), (38.51727885 59.22844850999999), (38.51989030838012 59.22924256775002), (38.52077767000001 59.23043912), (38.51231254 59.224501799999985), (38.512551784515374 59.224547846127564), (38.51381778717041 59.22442158336682), (38.51358711719512 59.2238780991934), (38.51419329643249 59.223806731941806), (38.51427376270294 59.22399063955615), (38.51510947 59.22389905), (38.52780121000001 59.20488304), (38.52907419204711 59.203077837637466), (38.5289990901947 59.201611140728005), (38.52855920791626 59.20050695655232), (38.52949132 59.20032293), (38.56769371 59.199232480000006), (38.56846511363983 59.19906555794782), (38.56793403625488 59.19838775682459), (38.5662093758583 59.198778507037076), (38.55965745999999 59.19800065999999), (38.51615649 59.231599579999994), (38.51866722106933 59.230521462084056), (38.52077767000001 59.23043912), (38.55310951999999 59.22745785000001), (38.54516744613647 59.22796911459713), (38.543407917022705 59.22856193490935), (38.53679895401 59.229330390353255), (38.5305118560791 59.23058183788467), (38.52662909 59.23084625999999), (38.51871994 59.22187543000001), (38.515512943267815 59.214040362973265), (38.51118922233581 59.21304091982347), (38.50878596305847 59.21395799239153), (38.50562471 59.212761769999986))";

[TestCase(0.1), TestCase(0.2), TestCase(0.3), TestCase(0.4), TestCase(0.5), TestCase(0.6), TestCase(0.7), TestCase(0.8), TestCase(0.9), TestCase(1)]
public void Test(double lengthRatio)
{
    var geom = new WKTReader().Read(WKT);
    Assert.That(geom.IsValid, Is.True);

    Geometry concaveHull = null;
    Assert.That(() => concaveHull = Algorithm.Hull.ConcaveHull.ConcaveHullByLengthRatio(geom, lengthRatio, true), Throws.Nothing);
    Assert.That(concaveHull.IsValid, Is.True);
        TestContext.WriteLine($"{lengthRatio}: {concaveHull.AsText()}");
}

No test fails, the following output is produced:

0.1: POLYGON ((38.60554509713967 59.33654578671183, 38.627480231229555 59.379240561824766, 38.6158546486266 59.34066131733952, 38.60800487243036 59.27702685286727, 38.7075750111547 59.16130138748632, 38.77058445041102 59.16109396793038, 38.81640643592429 59.19769094749021, 38.82308634136045 59.20446918940994, 38.8289547955201 59.20714005314176, 38.83807620479286 59.20215069377391, 38.84138776885046 59.19954728083175, 39.002886740485266 59.122004556868774, 38.92701055855268 59.12920500871117, 38.83407327912713 59.19039005370243, 38.83127868267636 59.188825879019625, 38.77353486014087 59.10740165880056, 38.73239582071643 59.15454234400364, 38.686227570702094 59.13056015555621, 38.68296875412818 59.13279161565055, 38.682980415259316 59.132982530350986, 38.6147424206161 59.16556107828804, 38.56793403625488 59.19838775682459, 38.5596574640106 59.198000656386746, 38.52949132 59.20032293, 38.51541662187084 59.14509280719818, 38.4639929751423 59.17683138121632, 38.460392666861935 59.212782731161546, 38.458690520089704 59.21550003459099, 38.42848982662716 59.24077357740069, 38.38361752426529 59.20984505285797, 38.37756117592969 59.21364110446784, 38.304000189460474 59.18059265130876, 38.26343480317622 59.155227800741486, 38.258673362271345 59.153625848377445, 38.26229388538454 59.17452604289841, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.28562464566037 59.267949566294796, 38.37220982877829 59.21753081612, 38.38724552851707 59.26836618370752, 38.42329575792519 59.251664151414026, 38.475513807924415 59.2309362206018, 38.501341827213764 59.239317278513994, 38.50774560123682 59.23976620518724, 38.39688109797687 59.36200579912337, 38.475051419200845 59.51031981804958, 38.60554509713967 59.33654578671183), (38.50804198740799 59.23978017243689, 38.51499597 59.23810116999999, 38.57549283259245 59.261943264677456, 38.50804198740799 59.23978017243689))

0.2: POLYGON ((38.60554509713967 59.33654578671183, 38.627480231229555 59.379240561824766, 38.6158546486266 59.34066131733952, 38.60800487243036 59.27702685286727, 38.7075750111547 59.16130138748632, 38.81640643592429 59.19769094749021, 38.82308634136045 59.20446918940994, 38.8289547955201 59.20714005314176, 38.83807620479286 59.20215069377391, 38.84138776885046 59.19954728083175, 39.002886740485266 59.122004556868774, 38.92701055855268 59.12920500871117, 38.83127868267636 59.188825879019625, 38.77353486014087 59.10740165880056, 38.686227570702094 59.13056015555621, 38.68296875412818 59.13279161565055, 38.6147424206161 59.16556107828804, 38.51541662187084 59.14509280719818, 38.4639929751423 59.17683138121632, 38.38361752426529 59.20984505285797, 38.304000189460474 59.18059265130876, 38.26343480317622 59.155227800741486, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.28562464566037 59.267949566294796, 38.38724552851707 59.26836618370752, 38.39688109797687 59.36200579912337, 38.475051419200845 59.51031981804958, 38.60554509713967 59.33654578671183))

0.3: POLYGON ((38.60554509713967 59.33654578671183, 38.627480231229555 59.379240561824766, 38.6158546486266 59.34066131733952, 38.60800487243036 59.27702685286727, 38.7075750111547 59.16130138748632, 38.81640643592429 59.19769094749021, 38.82308634136045 59.20446918940994, 38.8289547955201 59.20714005314176, 38.83807620479286 59.20215069377391, 39.002886740485266 59.122004556868774, 38.92701055855268 59.12920500871117, 38.77353486014087 59.10740165880056, 38.686227570702094 59.13056015555621, 38.51541662187084 59.14509280719818, 38.4639929751423 59.17683138121632, 38.304000189460474 59.18059265130876, 38.26343480317622 59.155227800741486, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.39688109797687 59.36200579912337, 38.475051419200845 59.51031981804958, 38.60554509713967 59.33654578671183))

0.4: POLYGON ((38.475051419200845 59.51031981804958, 38.627480231229555 59.379240561824766, 38.6158546486266 59.34066131733952, 38.82308634136045 59.20446918940994, 38.8289547955201 59.20714005314176, 38.83807620479286 59.20215069377391, 39.002886740485266 59.122004556868774, 38.77353486014087 59.10740165880056, 38.51541662187084 59.14509280719818, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.39688109797687 59.36200579912337, 38.475051419200845 59.51031981804958))

0.5: POLYGON ((38.475051419200845 59.51031981804958, 38.627480231229555 59.379240561824766, 38.83807620479286 59.20215069377391, 39.002886740485266 59.122004556868774, 38.77353486014087 59.10740165880056, 38.51541662187084 59.14509280719818, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.475051419200845 59.51031981804958))

0.6: POLYGON ((38.475051419200845 59.51031981804958, 38.627480231229555 59.379240561824766, 38.83807620479286 59.20215069377391, 39.002886740485266 59.122004556868774, 38.77353486014087 59.10740165880056, 38.51541662187084 59.14509280719818, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.475051419200845 59.51031981804958))

0.7: POLYGON ((38.475051419200845 59.51031981804958, 38.627480231229555 59.379240561824766, 39.002886740485266 59.122004556868774, 38.77353486014087 59.10740165880056, 38.51541662187084 59.14509280719818, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.475051419200845 59.51031981804958))

0.8: POLYGON ((38.475051419200845 59.51031981804958, 38.627480231229555 59.379240561824766, 39.002886740485266 59.122004556868774, 38.77353486014087 59.10740165880056, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.475051419200845 59.51031981804958))

0.9: POLYGON ((38.475051419200845 59.51031981804958, 38.627480231229555 59.379240561824766, 39.002886740485266 59.122004556868774, 38.77353486014087 59.10740165880056, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.475051419200845 59.51031981804958))

1.0: POLYGON ((38.475051419200845 59.51031981804958, 39.002886740485266 59.122004556868774, 38.77353486014087 59.10740165880056, 38.258673362271345 59.153625848377445, 38.26649365293311 59.220299653358566, 38.280968330809 59.267733990304485, 38.475051419200845 59.51031981804958))

@Evgeny1303
Copy link
Author

Magic happens ) Running the function with multipoint from my previous message fails with NetTopologySuite package 2.5.0 (nuget.org), but with 2.6.0-pre.196250762 or with current code from the repository it works fine.

But 3 another examples are still fails (with 2.6.0-pre.196250762 / current code).

@FObermaier
Copy link
Member

The issue with the sample geometries is that you have too many close points. This leads to trouble building a correct subdivision.
One idea to prevent this is to use a KdTree<T> filter to get rid of almost identical points. This seems to be valid when building a hull.

FObermaier added a commit that referenced this issue Oct 11, 2023
@FObermaier
Add example of how to avoid #716
d04ddd7
@Evgeny1303
Copy link
Author

@FObermaier , the idea with KdTree works fine for me. Thanks!

FObermaier added a commit that referenced this issue Jan 24, 2024
@FObermaier
Add sample code for discussion #713, update sample for #716
f70e8c0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@FObermaier @Evgeny1303