[Jts-topo-suite-user] Polygon Triangulation

Discussion:

Stanisław Góra

2016-01-23 13:37:44 UTC

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/***@telus.net/
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"

Martin Davis

2016-01-23 23:30:49 UTC

Permalink

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?

Post by StanisÅaw GÃ³ra
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
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
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

Stanisław Góra

2016-01-25 20:01:43 UTC

Permalink

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

Post by Martin Davis
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?

Martin Davis

2016-01-25 20:10:52 UTC

Permalink

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

Post by StanisÅaw GÃ³ra
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
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,
"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

Post by StanisÅaw GÃ³ra
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
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
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

Stanisław Góra

2016-01-25 20:26:22 UTC

Permalink

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?

Post by Martin Davis
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

Post by StanisÅaw GÃ³ra
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
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,
"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

Post by Martin Davis
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?

Post by StanisÅaw GÃ³ra
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
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
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

Martin Davis

2016-01-25 20:28:40 UTC

Permalink

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.

Post by StanisÅaw GÃ³ra
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?

Post by StanisÅaw GÃ³ra
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
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,
"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

Post by Martin Davis
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?

Post by StanisÅaw GÃ³ra
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
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
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user

Stanisław Góra

2016-01-25 20:39:32 UTC

Permalink

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

Post by Martin Davis
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.

Post by Martin Davis
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

Post by StanisÅaw GÃ³ra
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
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,
"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

Post by Martin Davis
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?

Post by StanisÅaw GÃ³ra
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
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
https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user