Re: [Jts-topo-suite-user] Polygon Triangulation
Brought to you by:
dr_jts
From: Stanisław G. <sta...@gm...> - 2016-01-25 20:26:40
|
Thanks for the advice. I am thinking that since these are rounding problems, it is likely that those self-intersections will be just pairs of flipped points very close to each other. Isn't there a simple way of detecting them and than just flipping their order in polygon? On Mon, Jan 25, 2016 at 9:10 PM Martin Davis <mtn...@gm...> wrote: > Thanks for the issue report. > > it is liikely to be too difficult/non-performant to enhance EarClipper to > handle invalid inputs. So I recommend checking the input for validity. > > It can be tricky to fix invalid polygons. It's better to avoid creating > invalid geometry in the first place. There's some code in the JTS Lab that > uses snap-rounding to accomplish this [1]. > > [1] > http://sourceforge.net/p/jts-topo-suite/code/HEAD/tree/trunk/jts-lab/src/main/java/com/vividsolutions/jtslab/SnapRoundOverlayFunctions.java > > On Mon, Jan 25, 2016 at 12:01 PM, Stanisław Góra <sta...@gm...> > wrote: > >> Hi, >> First of all, thank you for sharing this code with me. >> Yes, I still can't subscribe, but since I got in contact with you, it >> isn't that big of a problem. >> I tested all four versions but if I understand correctly EarClip and >> EarClipperO are the older ones. EarClipper is working much faster - don't >> see any more performance issues. >> (In my app I am triangulating some polygons each screen refresh to draw >> them) >> However after some time running my java app started Not Responding. >> After investigating my input I found out that when app generate incorrect >> (self-intersecting) polygon like these: >> POLYGON ((5670 4363, 6465 2509, 6458 2500, 5670 4364, 5670 4363)) >> POLYGON ((8235 3680, 7868 3610, 7454 3890, 7360 4381, 7640 4795, 7763 >> 4818, 7821 4679, 7821 4680, 7535 4213, 7891 3796, 8144 3901, 8235 3680)) >> through some robustness issue in previously used intersection() - it >> happens randomly, >> EarClipper hangs app. I've done ThreadDump and found specific line: >> >> "LWJGL Application" #15 prio=5 os_prio=0 tid=0x000000001911a800 >> nid=0x1be0 runnable [0x000000001d73e000] >> java.lang.Thread.State: RUNNABLE >> at >> com.vividsolutions.jts.polytriangulate.EarClipper.computeEars(EarClipper.java:116) >> at >> com.vividsolutions.jts.polytriangulate.EarClipper.triangulate(EarClipper.java:80)... >> >> I suppose I haven't done proper stress testing because I usually have >> from 5 to 30 points in polygon. Can you make a fix to ear clip algorithm or >> should I do an extra check for my polygons? If so how would you recommend >> fixing them using jts? >> Thanks >> >> On Sun, Jan 24, 2016 at 12:30 AM Martin Davis <mtn...@gm...> wrote: >> >>> Have a look at this - this is the code that is intended to wind up in >>> JTS at some point. Feedback welcome. >>> >>> https://github.com/dhtong/jts/tree/master/src/polytriangulate >>> >>> Not sure about the subscribe issue - is it still happening? >>> >>> On Sat, Jan 23, 2016 at 5:37 AM, Stanisław Góra <sta...@gm...> >>> wrote: >>> >>>> Hi, >>>> >>>> I am looking for a best way to triangulate polygons using JTS. Since it >>>> does not have Constrained Delaunay implementation (which would really help >>>> me) i looked at using Conforming Delaunay and setting constraints. Then i >>>> needed to get rid of the triangles that lie outside (concave) polygons and >>>> inside their holes. Testing each triangle with disjoint() and covers() >>>> functions takes much longer than triangulation itself and doesn't even >>>> produce reliable results because of some robustness issue. (triangles >>>> around added Steiner points lying on constrained segments return incorrect >>>> inside/outside polygon result). >>>> Then I found this thread >>>> http://sourceforge.net/p/jts-topo-suite/mailman/jts-topo-suite-user/thread/4BD...@te.../ and >>>> tried Michael's Ear Clipping code. It does great job at triangulating >>>> polygons but is a lot slower (92% time is spent on covers() function) and >>>> is killing performance on a android device even more than delaunay. >>>> >>>> In this article >>>> http://lin-ear-th-inking.blogspot.com/2011/04/polygon-triangulation-via-ear-clipping.html Martin >>>> Davis said that the Ear Clipping code will get added to JTS in the next >>>> release, and while it didn't maybe it was further optimized. >>>> Also, are there any plans to implement Constrained Delaunay? I realized >>>> I can't use Conforming Delaunay for yet another reason: I have some very >>>> long rectangle-like polygons to triangulate, which forces delaunay property >>>> to generate countless small triangles and produces "Too many splitting >>>> iterations" error. >>>> Otherwise can You point me to a fastest (runtime) way of triangulating >>>> polygons using either Conforming Delaunay or Ear Clipping given my problems? >>>> >>>> Thank You very much, >>>> Stanisław Góra >>>> >>>> PS. It seems I'm unable to subscribe jts user list - getting "Bug in >>>> Mailman version 2.1.9" >>>> >>>> >>>> ------------------------------------------------------------------------------ >>>> Site24x7 APM Insight: Get Deep Visibility into Application Performance >>>> APM + Mobile APM + RUM: Monitor 3 App instances at just $35/Month >>>> Monitor end-to-end web transactions and take corrective actions now >>>> Troubleshoot faster and improve end-user experience. Signup Now! >>>> http://pubads.g.doubleclick.net/gampad/clk?id=267308311&iu=/4140 >>>> _______________________________________________ >>>> Jts-topo-suite-user mailing list >>>> Jts...@li... >>>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >>>> >>>> >>> > |