org.locationtech.jts.algorithm.hull.ConcaveHull.concaveHullByLength can lead to infinite loops #1153
Description
Hey JTS team!
I have a somewhat obscure bug that happens in openrouteservice: GIScience/openrouteservice#1897
I observe infinite loops in that application from time to time. I was not yet able to find an actual reproducable example for when this happens, but this is what one thread was at while it was in that infinite loop (copied from GIScience/openrouteservice#1897 (comment)):
"http-nio-8082-exec-1684" #1737 [1971] daemon prio=5 os_prio=0 cpu=169975881.04ms elapsed=174790.38s tid=0x000073a5c5335fb0 nid=1971 runnable [0x000073a5c4fb4000]
java.lang.Thread.State: RUNNABLE
at org.locationtech.jts.triangulate.tri.Tri.isInteriorVertex(Tri.java:564)
at org.locationtech.jts.algorithm.hull.HullTri.isConnecting(HullTri.java:124)
at org.locationtech.jts.algorithm.hull.ConcaveHull.isRemovableBorder(ConcaveHull.java:416)
at org.locationtech.jts.algorithm.hull.ConcaveHull.computeHullBorder(ConcaveHull.java:287)
at org.locationtech.jts.algorithm.hull.ConcaveHull.computeHull(ConcaveHull.java:272)
at org.locationtech.jts.algorithm.hull.ConcaveHull.getHull(ConcaveHull.java:234)
at org.locationtech.jts.algorithm.hull.ConcaveHull.concaveHullByLength(ConcaveHull.java:110)
at org.locationtech.jts.algorithm.hull.ConcaveHull.concaveHullByLength(ConcaveHull.java:93)
at org.heigit.ors.isochrones.builders.AbstractIsochroneMapBuilder.addIsochrone(AbstractIsochroneMapBuilder.java:268)
at org.heigit.ors.isochrones.builders.concaveballs.ConcaveBallsIsochroneMapBuilder.compute(ConcaveBallsIsochroneMapBuilder.java:135)
at org.heigit.ors.isochrones.IsochroneMapBuilderFactory.buildMap(IsochroneMapBuilderFactory.java:35)
at org.heigit.ors.routing.RoutingProfile.buildIsochrone(RoutingProfile.java:671)
at org.heigit.ors.routing.RoutingProfileManager.buildIsochrone(RoutingProfileManager.java:605)
at org.heigit.ors.api.services.IsochronesService.generateIsochronesFromRequest(IsochronesService.java:59)
at org.heigit.ors.api.controllers.IsochronesAPI.getGeoJsonIsochrones(IsochronesAPI.java:139)
at org.heigit.ors.api.controllers.IsochronesAPI.getDefaultIsochrones(IsochronesAPI.java:111)
at java.lang.invoke.LambdaForm$DMH/0x000073a5d0314c00.invokeVirtual([email protected]/LambdaForm$DMH)
at java.lang.invoke.LambdaForm$MH/0x000073a5d06cc400.invoke([email protected]/LambdaForm$MH)
at java.lang.invoke.LambdaForm$MH/0x000073a5d0151400.invokeExact_MT([email protected]/LambdaForm$MH)
at jdk.internal.reflect.DirectMethodHandleAccessor.invokeImpl([email protected]/DirectMethodHandleAccessor.java:155)
at jdk.internal.reflect.DirectMethodHandleAccessor.invoke([email protected]/DirectMethodHandleAccessor.java:103)
at java.lang.reflect.Method.invoke([email protected]/Method.java:580)
at org.springframework.web.method.support.InvocableHandlerMethod.doInvoke(InvocableHandlerMethod.java:255)
at org.springframework.web.method.support.InvocableHandlerMethod.invokeForRequest(InvocableHandlerMethod.java:188)
at org.springframework.web.servlet.mvc.method.annotation.ServletInvocableHandlerMethod.invokeAndHandle(ServletInvocableHandlerMethod.java:118)
at org.springframework.web.servlet.mvc.method.annotation.RequestMappingHandlerAdapter.invokeHandlerMethod(RequestMappingHandlerAdapter.java:926)
at org.springframework.web.servlet.mvc.method.annotation.RequestMappingHandlerAdapter.handleInternal(RequestMappingHandlerAdapter.java:831)
at org.springframework.web.servlet.mvc.method.AbstractHandlerMethodAdapter.handle(AbstractHandlerMethodAdapter.java:87)
at org.springframework.web.servlet.DispatcherServlet.doDispatch(DispatcherServlet.java:1089)
at org.springframework.web.servlet.DispatcherServlet.doService(DispatcherServlet.java:979)
at org.springframework.web.servlet.FrameworkServlet.processRequest(FrameworkServlet.java:1014)
at org.springframework.web.servlet.FrameworkServlet.doPost(FrameworkServlet.java:914)
at jakarta.servlet.http.HttpServlet.service(HttpServlet.java:547)
at org.springframework.web.servlet.FrameworkServlet.service(FrameworkServlet.java:885)
at jakarta.servlet.http.HttpServlet.service(HttpServlet.java:614)
at org.apache.catalina.core.ApplicationFilterChain.internalDoFilter(ApplicationFilterChain.java:195)
at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:140)
at org.apache.tomcat.websocket.server.WsFilter.doFilter(WsFilter.java:51)
at org.apache.catalina.core.ApplicationFilterChain.internalDoFilter(ApplicationFilterChain.java:164)
at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:140)
at org.springframework.web.filter.RequestContextFilter.doFilterInternal(RequestContextFilter.java:100)
at org.springframework.web.filter.OncePerRequestFilter.doFilter(OncePerRequestFilter.java:116)
at org.apache.catalina.core.ApplicationFilterChain.internalDoFilter(ApplicationFilterChain.java:164)
at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:140)
at org.springframework.web.filter.FormContentFilter.doFilterInternal(FormContentFilter.java:93)
at org.springframework.web.filter.OncePerRequestFilter.doFilter(OncePerRequestFilter.java:116)
at org.apache.catalina.core.ApplicationFilterChain.internalDoFilter(ApplicationFilterChain.java:164)
at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:140)
at org.springframework.web.filter.ServerHttpObservationFilter.doFilterInternal(ServerHttpObservationFilter.java:113)
at org.springframework.web.filter.OncePerRequestFilter.doFilter(OncePerRequestFilter.java:116)
at org.apache.catalina.core.ApplicationFilterChain.internalDoFilter(ApplicationFilterChain.java:164)
at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:140)
at org.springframework.web.filter.CharacterEncodingFilter.doFilterInternal(CharacterEncodingFilter.java:201)
at org.springframework.web.filter.OncePerRequestFilter.doFilter(OncePerRequestFilter.java:116)
at org.apache.catalina.core.ApplicationFilterChain.internalDoFilter(ApplicationFilterChain.java:164)
at org.apache.catalina.core.ApplicationFilterChain.doFilter(ApplicationFilterChain.java:140)
at org.apache.catalina.core.StandardWrapperValve.invoke(StandardWrapperValve.java:167)
at org.apache.catalina.core.StandardContextValve.invoke(StandardContextValve.java:90)
at org.apache.catalina.authenticator.AuthenticatorBase.invoke(AuthenticatorBase.java:483)
at org.apache.catalina.core.StandardHostValve.invoke(StandardHostValve.java:115)
at org.apache.catalina.valves.ErrorReportValve.invoke(ErrorReportValve.java:93)
at org.apache.catalina.core.StandardEngineValve.invoke(StandardEngineValve.java:74)
at org.apache.catalina.connector.CoyoteAdapter.service(CoyoteAdapter.java:344)
at org.apache.coyote.http11.Http11Processor.service(Http11Processor.java:384)
at org.apache.coyote.AbstractProcessorLight.process(AbstractProcessorLight.java:63)
at org.apache.coyote.AbstractProtocol$ConnectionHandler.process(AbstractProtocol.java:904)
at org.apache.tomcat.util.net.NioEndpoint$SocketProcessor.doRun(NioEndpoint.java:1741)
at org.apache.tomcat.util.net.SocketProcessorBase.run(SocketProcessorBase.java:52)
at org.apache.tomcat.util.threads.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1190)
at org.apache.tomcat.util.threads.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:659)
at org.apache.tomcat.util.threads.TaskThread$WrappingRunnable.run(TaskThread.java:63)
at java.lang.Thread.runWith([email protected]/Thread.java:1596)
at java.lang.Thread.run([email protected]/Thread.java:1583)
I'm happy to provide more context if that helps. It is that we're calculating many isochrones with openrouteservice, and that function is used by it to then generate the result. This only happens very rarely, and upon a retry, this usually does not happen anymore. It is a bit hard to say how to reproduce it. Do you have any ideas (you know the code better than I do) for when this could happen? If possible, I'll try to debug this further, but I currently also have no good idea what I could do additionally.
All the best,
Lena