Re: [Jts-topo-suite-user] Polygon Triangulation

[Stanisław G. <sta...@gm...>]

Ok, thank you for your help and tips,
I will attempt to write sth like this myself

On Mon, Jan 25, 2016 at 9:28 PM Martin Davis <mtn...@gm...> wrote:

> There's no code in JTS to do this.
>
> I guess the algorithm would be to inspect triples of segments and flip the
> middle segment if the ends intersect.
>
> On Mon, Jan 25, 2016 at 12:26 PM, Stanisław Góra <sta...@gm...>
> wrote:
>
>> 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
>>>>>>
>>>>>>
>>>>>
>>>
>