You can subscribe to this list here.
2009 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}
(3) 
_{Dec}


2010 
_{Jan}
(30) 
_{Feb}
(41) 
_{Mar}
(69) 
_{Apr}
(131) 
_{May}
(67) 
_{Jun}
(24) 
_{Jul}
(28) 
_{Aug}
(52) 
_{Sep}
(9) 
_{Oct}
(24) 
_{Nov}
(36) 
_{Dec}
(24) 
2011 
_{Jan}
(20) 
_{Feb}
(53) 
_{Mar}
(31) 
_{Apr}
(74) 
_{May}
(71) 
_{Jun}
(51) 
_{Jul}
(28) 
_{Aug}
(91) 
_{Sep}
(72) 
_{Oct}
(46) 
_{Nov}
(90) 
_{Dec}
(38) 
2012 
_{Jan}
(80) 
_{Feb}
(77) 
_{Mar}
(98) 
_{Apr}
(78) 
_{May}
(56) 
_{Jun}
(85) 
_{Jul}
(53) 
_{Aug}
(87) 
_{Sep}
(74) 
_{Oct}
(67) 
_{Nov}
(85) 
_{Dec}
(66) 
2013 
_{Jan}
(50) 
_{Feb}
(34) 
_{Mar}
(45) 
_{Apr}
(36) 
_{May}
(22) 
_{Jun}
(10) 
_{Jul}
(30) 
_{Aug}
(39) 
_{Sep}
(25) 
_{Oct}
(11) 
_{Nov}
(64) 
_{Dec}
(42) 
2014 
_{Jan}
(27) 
_{Feb}
(6) 
_{Mar}
(10) 
_{Apr}
(14) 
_{May}
(25) 
_{Jun}
(6) 
_{Jul}
(25) 
_{Aug}
(3) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 





1
(2) 
2
(1) 
3
(3) 
4

5

6
(17) 
7
(2) 
8
(9) 
9
(4) 
10

11
(2) 
12
(8) 
13
(8) 
14
(3) 
15
(3) 
16
(1) 
17
(1) 
18

19

20
(4) 
21
(8) 
22
(9) 
23
(6) 
24
(8) 
25
(7) 
26
(4) 
27
(9) 
28
(7) 
29
(3) 
30
(2) 

From: Michael Bedward <michael.bedward@gm...>  20100430 04:20:16

On 30 April 2010 10:47, Martin Davis wrote: > Looks great. I look forward to seeing the code. > > It would be great to have all your examples coded up as a unit test... > Yes, we're getting there :) The edgeflipping code needs more work. It presently has problems with the 5squareholes test. I also still have to address the issue of using all vertices in the triangulation. However, it is able to handle the OGC evil polygon with the hole touching the shell... POLYGON ((30 40, 30 180, 210 180, 210 40, 30 40), (80 110, 160 110, 120 180, 80 110)) http://imagebin.org/95044 Good idea about the test cases. I'll also break the current code up a bit so that it's more amenable to unit tests. Michael 
From: Martin Davis <mtnclimb@te...>  20100430 00:45:41

Looks great. I look forward to seeing the code. It would be great to have all your examples coded up as a unit test... Michael Bedward wrote: > A bit more progress... > > Housewithdiamondhole polygon: triangulation followed by edgeflipping... > http://imagebin.org/94930 > > Michael > >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: Michael Bedward <michael.bedward@gm...>  20100429 10:03:59

A bit more progress... Housewithdiamondhole polygon: triangulation followed by edgeflipping... http://imagebin.org/94930 Michael 
From: Martin Davis <mtnclimb@te...>  20100429 03:55:04

Yes, I don't think the Polygon Triangulation algorithm should remove any collinear vertices which are present in the input. If the user desires to do that, it can be accomplished in a separate procedure (which would be useful to have provided in JTS). At very least this should be made an option to the triangulator. Unless there's an issue with being able to correctly execute an algorithm, I think it's always better to try and modularize functionality as far as possible. Michael Bedward wrote: > On 29 April 2010 02:11, Martin Davis <mbdavis@...> wrote: > >> I agree. I think it's standard that for a valid triangualation all vertices >> must be used. >> >> > > Including, for example, colinear vertices on the polygon's exterior ? > > In Asger's example the colinear vertices might have different Z > values but how common is that use case ? (e.g. TINs are normally > generated from point clouds, not polygons). > > I guess we need to sort out the rules before I do any more on the > basic algorithm. In the meantime I'm working on edgeflipping. > > Michael > >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: Michael Bedward <michael.bedward@gm...>  20100429 00:33:07

On 29 April 2010 02:11, Martin Davis <mbdavis@...> wrote: > I agree. I think it's standard that for a valid triangualation all vertices > must be used. > Including, for example, colinear vertices on the polygon's exterior ? In Asger's example the colinear vertices might have different Z values but how common is that use case ? (e.g. TINs are normally generated from point clouds, not polygons). I guess we need to sort out the rules before I do any more on the basic algorithm. In the meantime I'm working on edgeflipping. Michael 
From: Martin Davis <mbdavis@re...>  20100428 16:08:44

I agree. I think it's standard that for a valid triangualation all vertices must be used. Asger Sigurd Skovbo Petersen wrote: > Hi Michael, > > I vote that it is not valid. > > A common usage scenario of a polygon triangulator is to be able to > interpolate a continuous surface from an attribute value on the > vertices. In a simple case this attribute value could be the Z > coordinate and the surface could then represent the terrain. > > To be able to do this, all vertices must be used (also colinear). > > Best regards > Asger > > Original Message > From: Michael Bedward [mailto:michael.bedward@...] > Sent: 28. april 2010 11:48 > To: jtstoposuiteuser@... > Subject: Re: [Jtstoposuiteuser] Triangulating polygons? > > >> Actually this prompts a definitional question: for a triangulation to >> be valid must it use all hole vertices (other than colinear ones) ? >> >> > > A little more on this question... Looking at a few geometry papers it > seems that what constitutes a valid triangulation varies. For instance, > some papers triangulate convex polygons be adding additional internal > nodes. > > Take this example: > POLYGON( (50 100, 100 200, 200 0, 100 0, 100 100, 50 100) > > Here is the "obvious" minimal triangulation... > http://imagebin.org/94784 > > Do we call that a valid triangulation or is the larger triangle branded > as a quadrilateral ? I vote that it's valid :) > > Michael > >  >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > > >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > >  Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 3833022 
From: Michael Bedward <michael.bedward@gm...>  20100428 11:53:43

Hi Asger, Yes, TINs are a good example (even though it's not what I wanted to hear :) I think I can add an option to the algorithm to either accept or reject such sneaky triangles. Michael On 28 April 2010 21:13, Asger Sigurd Skovbo Petersen <ASP@...> wrote: > Hi Michael, > > I vote that it is not valid. > > A common usage scenario of a polygon triangulator is to be able to > interpolate a continuous surface from an attribute value on the > vertices. In a simple case this attribute value could be the Z > coordinate and the surface could then represent the terrain. > > To be able to do this, all vertices must be used (also colinear). > > Best regards > Asger > 
From: Asger Sigurd Skovbo Petersen <ASP@blominfo.dk>  20100428 11:25:55

Hi Michael, I vote that it is not valid. A common usage scenario of a polygon triangulator is to be able to interpolate a continuous surface from an attribute value on the vertices. In a simple case this attribute value could be the Z coordinate and the surface could then represent the terrain. To be able to do this, all vertices must be used (also colinear). Best regards Asger Original Message From: Michael Bedward [mailto:michael.bedward@...] Sent: 28. april 2010 11:48 To: jtstoposuiteuser@... Subject: Re: [Jtstoposuiteuser] Triangulating polygons? > Actually this prompts a definitional question: for a triangulation to > be valid must it use all hole vertices (other than colinear ones) ? > A little more on this question... Looking at a few geometry papers it seems that what constitutes a valid triangulation varies. For instance, some papers triangulate convex polygons be adding additional internal nodes. Take this example: POLYGON( (50 100, 100 200, 200 0, 100 0, 100 100, 50 100) Here is the "obvious" minimal triangulation... http://imagebin.org/94784 Do we call that a valid triangulation or is the larger triangle branded as a quadrilateral ? I vote that it's valid :) Michael   _______________________________________________ Jtstoposuiteuser mailing list Jtstoposuiteuser@... https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser 
From: Michael Bedward <michael.bedward@gm...>  20100428 09:48:07

> Actually this prompts a definitional question: for a triangulation to > be valid must it use all hole vertices (other than colinear ones) ? > A little more on this question... Looking at a few geometry papers it seems that what constitutes a valid triangulation varies. For instance, some papers triangulate convex polygons be adding additional internal nodes. Take this example: POLYGON( (50 100, 100 200, 200 0, 100 0, 100 100, 50 100) Here is the "obvious" minimal triangulation... http://imagebin.org/94784 Do we call that a valid triangulation or is the larger triangle branded as a quadrilateral ? I vote that it's valid :) Michael 
From: Michael Bedward <michael.bedward@gm...>  20100428 06:46:40

Hi Martin, > This one has a problem  there is a quadrilateral off the right edge of > the bottomright hole. > Ah, yes  bummer. I'll look into that one. Actually this prompts a definitional question: for a triangulation to be valid must it use all hole vertices (other than colinear ones) ? By the way, I've now modified the triangulate method to use CGAlgorithms.computeOrientation. It only required a trivial change to the stepping code and makes the whole program shorter and simpler. Michael 
From: Martin Davis <mtnclimb@te...>  20100428 06:31:34

Michael Bedward wrote: > Hi Martin, > > >> Also, is it necessary to removing collinear points too often (or maybe >> at all). I notice that in the "4squareholes" figure, there is at >> least one internal "triangle" which actually has 4 sides! (in the >> bottom right). >> > > The original 4squareholes triangulation had a few problems. Here it > is again, generated with the current code... > http://imagebin.org/94755 > > This looks OK to me and the dump of polygon coords seems to make > sense. Can you spot any problems ? > Nope, looks fine > Here is the 5square hole solution... > http://imagebin.org/94756 > This one has a problem  there is a quadrilateral off the right edge of the bottomright hole. 
From: Michael Bedward <michael.bedward@gm...>  20100428 03:35:00

Hi Martin, > Also, is it necessary to removing collinear points too often (or maybe > at all). I notice that in the "4squareholes" figure, there is at > least one internal "triangle" which actually has 4 sides! (in the > bottom right). The original 4squareholes triangulation had a few problems. Here it is again, generated with the current code... http://imagebin.org/94755 This looks OK to me and the dump of polygon coords seems to make sense. Can you spot any problems ? Here is the 5square hole solution... http://imagebin.org/94756 > I think this must be due to the collinear point removal > code. It seems to me that if you use the robust computeOrientation > predicate, you can just avoid creating triangles which have all 3 points > collinear. Thanks ! I think to implement that I'd need to also modify the way the algorithm tracks the shell coords as it's stepping through them (?) Have to think about it. > I also notice that in the "4squareholes" result there is at least one > triangle pair which could be improved by edge flipping (the top one). Yes, sorry. I haven't attempted improvement yet. I wanted to get the basic triangulation working first. I'll try your lexicographic ordering suggestion. The current code is attached. Michael 
From: Martin Davis <mbdavis@re...>  20100427 17:52:44

Sorry to have to point this out, but the OGC specs allow for holes which touch the polygon shell at a single point. Eg.: POLYGON ((30 40, 30 180, 210 180, 210 40, 30 40), (80 110, 160 110, 120 180, 80 110)) I suspect this may cause problems for your triangulation algorithm, Michael. One solution is to node the outer shell to add the incident vertex. (And the same applies to touching holes, which are also allowed). This is somewhat nontrival to implement efficiently, however.  Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 3833022 
From: Martin Davis <mbdavis@re...>  20100427 15:59:56

I also notice that in the "4squareholes" result there is at least one triangle pair which could be improved by edge flipping (the top one). Martin Davis wrote: > Correction  that should be "use the CGAlgorithms.computeOrientation() > predicate". > > Also, is it necessary to removing collinear points too often (or maybe > at all). I notice that in the "4squareholes" figure, there is at > least one internal "triangle" which actually has 4 sides! (in the > bottom right). I think this must be due to the collinear point removal > code. It seems to me that if you use the robust computeOrientation > predicate, you can just avoid creating triangles which have all 3 points > collinear. > > Martin Davis wrote: > >> One thing I notice is that you're using the covers predicate. This >> should be perfectly robust, but it's always something I'm a little bit >> hesitant to use as a core part of another algorithm. It's also much >> slower than desirable. It's better to achieve the same result via a >> direct test. (I can't provide an substitute algorithm right now, but >> will try to soon). >> >> Also, your test for collinear points isn't going to be robust, since it >> uses mathematical computation and is thus subject to roundoff error. >> Better to use the CGAlgorithms.isCCW predicate, which is robust. >> >> All I can suggest right now... will try and do more testing later. >> >> Michael Bedward wrote: >> >> >>> Hi Ian, Martin, >>> >>> I just did a bit more testing of yesterday's code (EarClipping3.java). >>> The following polygon is handled successfully... >>> >>> "POLYGON ((0 0, 0 200, 200 200, 200 0, 0 0), " + >>> "(20 20, 20 40, 40 40, 40 20, 20 20), " + >>> "(20 160, 20 180, 40 180, 40 160, 20 160), " + >>> "(160 160, 160 180, 180 180, 180 160, 160 160), " + >>> "(90 90, 90 110, 110 110, 110 90, 90 90) )"); >>> >>> Here is an image of the result... >>> http://imagebin.org/94614 >>> >>> However, if I add an extra hole near the lower right corner... >>> "(160 20, 160 40, 180 40, 180 20, 160 20), " >>> >>> The algorithm gets stuck. >>> >>> Any ideas ? >>> >>> Michael >>> >>>  >>> _______________________________________________ >>> Jtstoposuiteuser mailing list >>> Jtstoposuiteuser@... >>> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >>> >>> >>> >>> >>  >> _______________________________________________ >> Jtstoposuiteuser mailing list >> Jtstoposuiteuser@... >> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >> >> > >  Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 3833022 
From: Martin Davis <mbdavis@re...>  20100427 15:51:15

Correction  that should be "use the CGAlgorithms.computeOrientation() predicate". Also, is it necessary to removing collinear points too often (or maybe at all). I notice that in the "4squareholes" figure, there is at least one internal "triangle" which actually has 4 sides! (in the bottom right). I think this must be due to the collinear point removal code. It seems to me that if you use the robust computeOrientation predicate, you can just avoid creating triangles which have all 3 points collinear. Martin Davis wrote: > One thing I notice is that you're using the covers predicate. This > should be perfectly robust, but it's always something I'm a little bit > hesitant to use as a core part of another algorithm. It's also much > slower than desirable. It's better to achieve the same result via a > direct test. (I can't provide an substitute algorithm right now, but > will try to soon). > > Also, your test for collinear points isn't going to be robust, since it > uses mathematical computation and is thus subject to roundoff error. > Better to use the CGAlgorithms.isCCW predicate, which is robust. > > All I can suggest right now... will try and do more testing later. > > Michael Bedward wrote: > >> Hi Ian, Martin, >> >> I just did a bit more testing of yesterday's code (EarClipping3.java). >> The following polygon is handled successfully... >> >> "POLYGON ((0 0, 0 200, 200 200, 200 0, 0 0), " + >> "(20 20, 20 40, 40 40, 40 20, 20 20), " + >> "(20 160, 20 180, 40 180, 40 160, 20 160), " + >> "(160 160, 160 180, 180 180, 180 160, 160 160), " + >> "(90 90, 90 110, 110 110, 110 90, 90 90) )"); >> >> Here is an image of the result... >> http://imagebin.org/94614 >> >> However, if I add an extra hole near the lower right corner... >> "(160 20, 160 40, 180 40, 180 20, 160 20), " >> >> The algorithm gets stuck. >> >> Any ideas ? >> >> Michael >> >>  >> _______________________________________________ >> Jtstoposuiteuser mailing list >> Jtstoposuiteuser@... >> https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser >> >> >> > >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > >  Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 3833022 
From: Martin Davis <mbdavis@re...>  20100427 15:47:04

Sweet! Can you post your fixed code? Michael Bedward wrote: > Another one... > > http://imagebin.org/94647 > > Starting to feel that the basic algorithm is OK (albeit in stream of > consciousness code at the moment) > > Michael > >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > >  Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 3833022 
From: Michael Bedward <michael.bedward@gm...>  20100427 09:32:11

Another one... http://imagebin.org/94647 Starting to feel that the basic algorithm is OK (albeit in stream of consciousness code at the moment) Michael 
From: Michael Bedward <michael.bedward@gm...>  20100427 08:16:07

Success... http://imagebin.org/94626 Michael 
From: Michael Bedward <michael.bedward@gm...>  20100427 06:57:49

Thanks Martin. When I have a chance I'll try following it in the debugger and see if I can understand why it's failing with this case. Michael 
From: Martin Davis <mtnclimb@te...>  20100427 06:08:05

One thing I notice is that you're using the covers predicate. This should be perfectly robust, but it's always something I'm a little bit hesitant to use as a core part of another algorithm. It's also much slower than desirable. It's better to achieve the same result via a direct test. (I can't provide an substitute algorithm right now, but will try to soon). Also, your test for collinear points isn't going to be robust, since it uses mathematical computation and is thus subject to roundoff error. Better to use the CGAlgorithms.isCCW predicate, which is robust. All I can suggest right now... will try and do more testing later. Michael Bedward wrote: > Hi Ian, Martin, > > I just did a bit more testing of yesterday's code (EarClipping3.java). > The following polygon is handled successfully... > > "POLYGON ((0 0, 0 200, 200 200, 200 0, 0 0), " + > "(20 20, 20 40, 40 40, 40 20, 20 20), " + > "(20 160, 20 180, 40 180, 40 160, 20 160), " + > "(160 160, 160 180, 180 180, 180 160, 160 160), " + > "(90 90, 90 110, 110 110, 110 90, 90 90) )"); > > Here is an image of the result... > http://imagebin.org/94614 > > However, if I add an extra hole near the lower right corner... > "(160 20, 160 40, 180 40, 180 20, 160 20), " > > The algorithm gets stuck. > > Any ideas ? > > Michael > >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 
From: Michael Bedward <michael.bedward@gm...>  20100427 05:12:49

Hi Ian, Martin, I just did a bit more testing of yesterday's code (EarClipping3.java). The following polygon is handled successfully... "POLYGON ((0 0, 0 200, 200 200, 200 0, 0 0), " + "(20 20, 20 40, 40 40, 40 20, 20 20), " + "(20 160, 20 180, 40 180, 40 160, 20 160), " + "(160 160, 160 180, 180 180, 180 160, 160 160), " + "(90 90, 90 110, 110 110, 110 90, 90 90) )"); Here is an image of the result... http://imagebin.org/94614 However, if I add an extra hole near the lower right corner... "(160 20, 160 40, 180 40, 180 20, 160 20), " The algorithm gets stuck. Any ideas ? Michael 
From: Michael Bedward <michael.bedward@gm...>  20100426 12:12:57

Hi Martin, Ian, I've now extended the code to add holes to the shell by scanning from bottom to top. The new code (EarClipping3.java) successfully processes the MEP (Martin's Evil Polygon)... POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440), (105 230, 443 228, 106 208, 105 230), (280 210, 260 190, 310 190, 280 210)) Finding these ears... POLYGON ((50 50, 260 190, 310 190, 50 50)) POLYGON ((280 210, 260 190, 106 208, 280 210)) POLYGON ((280 210, 106 208, 443 228, 280 210)) POLYGON ((310 190, 280 210, 443 228, 310 190)) POLYGON ((50 50, 310 190, 443 228, 50 50)) POLYGON ((106 208, 260 190, 50 50, 106 208)) POLYGON ((105 230, 106 208, 50 50, 105 230)) POLYGON ((105 230, 50 50, 50 440, 105 230)) POLYGON ((105 230, 50 440, 280 240, 105 230)) POLYGON ((443 228, 105 230, 280 240, 443 228)) POLYGON ((443 228, 280 240, 510 440, 443 228)) POLYGON ((443 228, 510 440, 510 50, 443 228)) POLYGON ((50 50, 443 228, 510 50, 50 50)) Feeling pretty pleased about that :) I've commented the code enough (I hope) to make clear what it's doing. I haven't yet tried to do anything about 'improving' the triangulation. Michael 
From: Martin Davis <mtnclimb@te...>  20100426 04:56:17

Great, that works now. re the triangulation improvement algorithm: The algorithm requires being able to find neighbouring triangles across triangle sides. This can be done by embedding the triangles in a topological structure such as a Quadtree, but that gets a bit complex. A simpler option is to index the triangles by their edge coordinates, as normalized line segments (eg with coordinates in lexicographic order). A simple Java Map can be used to do this. Then it's easy to find neighbouring triangles. Also, Maps are easy to update, which is required if edges are flipped. And, as long as a check is made to ensure that candidate quadrilaterals are convex, I don't think flipping can ever violate the polygonal boundary constraints. Michael Bedward wrote: > On 26 April 2010 13:24, Martin Davis wrote: > >> Michael, >> >> The code you provided doesn't work for me. Any chance you sent out an >> older version? >> > > Oops  sorry about that Martin. I've attached the correct version. > > Thanks for the new tips about connecting holes and improving the > triangulation. I'll play with the holes idea first. > > Michael > >  > >  > >  > > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > 
From: Michael Bedward <michael.bedward@gm...>  20100426 04:47:53

On 26 April 2010 13:24, Martin Davis wrote: > Michael, > > The code you provided doesn't work for me. Any chance you sent out an > older version? Oops  sorry about that Martin. I've attached the correct version. Thanks for the new tips about connecting holes and improving the triangulation. I'll play with the holes idea first. Michael 
From: Martin Davis <mtnclimb@te...>  20100426 03:23:08

Michael, The code you provided doesn't work for me. Any chance you sent out an older version? Michael Bedward wrote: > Normalizing the polygon did the trick. For the housewithdiamond polygon... > POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3)) > > the algorithm returns these ears... > POLYGON ((0 0, 0 5, 3 5, 0 0)) > POLYGON ((0 0, 3 5, 5 3, 0 0)) > POLYGON ((5 7, 3 5, 0 5, 5 7)) > POLYGON ((5 7, 0 5, 5 10, 5 7)) > POLYGON ((7 5, 5 7, 5 10, 7 5)) > POLYGON ((7 5, 5 10, 10 5, 7 5)) > POLYGON ((5 3, 7 5, 10 5, 5 3)) > POLYGON ((0 0, 5 3, 10 5, 0 0)) > POLYGON ((0 0, 10 5, 10 0, 0 0)) > > Not the prettiest solution, the second last ear in particular is a > sliver, but it works. The code for this is below. > > >> By the way, I can definitely visualize situations where the "choose >> shortest segment to connect hole" algorithm won't work. Eg the following: >> >> POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440), >> (105 230, 443 228, 106 208, 105 230), >> (280 210, 260 190, 310 190, 280 210)) >> > > That's a nefarious polygon :) I'll puzzle over that next. > > Michael > > /** > * Demonstrates brute force approach to the ear clipping algorithm > * to triangulate a polygon. This demo can deal with polygons having > * nonchallenging holes > * > * @author Michael Bedward > */ > public class EarClipping2 { > private static final double EPS = 1.0E4; > > GeometryFactory gf = new GeometryFactory(); > > public static void main(String[] args) throws Exception { > new EarClipping2().demo(); > } > > /** > * Demonstrate the earclipping algorithm > * @throws Exception > */ > private void demo() throws Exception { > WKTReader reader = new WKTReader(gf); > Polygon poly = (Polygon) reader.read( > "POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), " + > "(5 3, 7 5, 5 7, 3 5, 5 3))"); > > Geometry ears = triangulate(poly); > > for (int i = 0; i < ears.getNumGeometries(); i++) { > System.out.println(ears.getGeometryN(i)); > } > } > > /** > * Brute force approach to ear clipping > * > * @param inputPoly input polygon > * @return GeometryCollection of triangular polygons > */ > private Geometry triangulate(Polygon inputPoly) { > List<Polygon> ears = new ArrayList<Polygon>(); > List<Coordinate> coords = connectHoles(inputPoly); > > removeColinearVertices(coords); > int N = coords.size()  1; > > boolean finished = false; > boolean found = false; > boolean reversed = false; > int k0 = 0; > do { > int k1 = (k0 + 1) % N; > int k2 = (k1 + 2) % N; > LineString ls = gf.createLineString(new Coordinate[] > {coords.get(k0), coords.get(k2)}); > > found = false; > if (inputPoly.covers(ls)) { > Polygon ear = gf.createPolygon(gf.createLinearRing( > new Coordinate[]{coords.get(k0), > coords.get(k1), coords.get(k2), coords.get(k0)}), > null); > // additional check for hole over ear > if (inputPoly.covers(ear)) { > found = true; > ears.add(ear); > coords.remove(k1); > removeColinearVertices(coords); > N = coords.size()  1; > k0 = 0; > if (N == 3) { // triangle > > ears.add(gf.createPolygon(gf.createLinearRing(coords.toArray(new > Coordinate[4])), null)); > finished = true; > } > } > } > > if (!found) { > k0++; > > if (k0 == N) { > throw new IllegalStateException("Algorithm failed"); > } > } > > } while (!finished); > > return gf.createGeometryCollection(ears.toArray(new Geometry[0])); > } > > /** > * Remove colinear vertices. TopologyPreservingSimplifier could be > * used for this but that seems like overkill. > * > * @param coords polygon vertices > * @return coordinates with any colinear vertices removed > */ > private void removeColinearVertices(List<Coordinate> coords) { > int N = coords.size()  1; > List<Coordinate> coordList = new ArrayList<Coordinate>(); > > for (int j = 1; j <= N; ) { > int i = (j  1) % N; > int k = (j + 1) % N; > if (Math.abs(Math.PI  Angle.angleBetween(coords.get(i), > coords.get(j), coords.get(k))) < EPS) { > coords.remove(j); > N ; > } else { > j++ ; > } > } > } > > /** > * Connect any holes in the input polygon to the exterior ring to > * form a selfintersecting shell > * > * @param inputPoly input polygon > * @return a new polygon with holes (if any) connected to the exterior > * ring > */ > private List<Coordinate> connectHoles(Polygon inputPoly) { > // defensively copy the input polygon > Polygon poly = (Polygon) inputPoly.clone(); > poly.normalize(); > > Coordinate[] coords = poly.getExteriorRing().getCoordinates(); > List<Coordinate> shellCoords = new ArrayList<Coordinate>(); > shellCoords.addAll(Arrays.asList(coords)); > > for (int i = 0; i < inputPoly.getNumInteriorRing(); i++) { > List<Coordinate> holeCoords = > Arrays.asList(poly.getInteriorRingN(i).getCoordinates()); > joinClosest(shellCoords, holeCoords); > } > > return shellCoords; > } > > private void joinClosest(List<Coordinate> shellCoords, > List<Coordinate> holeCoords) { > double minD2 = Double.MAX_VALUE; > int minIh = 1, minIs = 1; > > final int Ns = shellCoords.size()  1; > final int Nh = holeCoords.size()  1; > > for (int is = 0; is < Ns; is++) { > Coordinate cs = shellCoords.get(is); > for (int ih = 0; ih < Nh; ih++) { > Coordinate ch = holeCoords.get(ih); > double d2 = (ch.x  cs.x)*(ch.x  cs.x) + (ch.y  > cs.y)*(ch.y  cs.y); > if (d2 < minD2) { > minD2 = d2; > minIh = ih; > minIs = is; > } > } > } > > /* > * Insert the join, then the hole coords, then the join again into > * shell coords list > */ > List<Coordinate> toAdd = new ArrayList<Coordinate>(); > toAdd.add(new Coordinate(shellCoords.get(minIs))); > > int i = minIh; > do { > toAdd.add(new Coordinate(holeCoords.get(i))); > i = (i + 1) % Nh; > } while (i != minIh); > > toAdd.add(new Coordinate(holeCoords.get(minIh))); > shellCoords.addAll(minIs, toAdd); > } > > } > >  > _______________________________________________ > Jtstoposuiteuser mailing list > Jtstoposuiteuser@... > https://lists.sourceforge.net/lists/listinfo/jtstoposuiteuser > > 