Thread: Re: [Jts-topo-suite-user] Triangulating polygons? (Page 2)
Brought to you by:
dr_jts
Menu
▾
▴
jts-topo-suite-user
|
From: Michael B. <mic...@gm...> - 2010-04-27 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: Martin D. <mtn...@te...> - 2010-04-27 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 round-off 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 > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |
|
From: Michael B. <mic...@gm...> - 2010-04-27 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: Michael B. <mic...@gm...> - 2010-04-27 08:16:07
Attachments:
EarClipping4.java
|
Success... http://imagebin.org/94626 Michael |
|
From: Michael B. <mic...@gm...> - 2010-04-27 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: Martin D. <mb...@re...> - 2010-04-27 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 > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 |
|
From: Martin D. <mb...@re...> - 2010-04-27 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 "4-square-holes" 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 round-off 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 >> >> ------------------------------------------------------------------------------ >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts...@li... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> >> >> > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 |
|
From: Martin D. <mb...@re...> - 2010-04-27 15:59:56
|
I also notice that in the "4-square-holes" 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 "4-square-holes" 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 round-off 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 >>> >>> ------------------------------------------------------------------------------ >>> _______________________________________________ >>> Jts-topo-suite-user mailing list >>> Jts...@li... >>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >>> >>> >>> >>> >> ------------------------------------------------------------------------------ >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts...@li... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> >> >> > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 |
|
From: Michael B. <mic...@gm...> - 2010-04-28 03:35:00
Attachments:
EarClipping5.java
|
Hi Martin, > Also, is it necessary to removing collinear points too often (or maybe > at all). I notice that in the "4-square-holes" figure, there is at > least one internal "triangle" which actually has 4 sides! (in the > bottom right). The original 4-square-holes 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 5-square 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 "4-square-holes" 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 D. <mtn...@te...> - 2010-04-28 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 "4-square-holes" figure, there is at >> least one internal "triangle" which actually has 4 sides! (in the >> bottom right). >> > > The original 4-square-holes 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 5-square hole solution... > http://imagebin.org/94756 > This one has a problem - there is a quadrilateral off the right edge of the bottom-right hole. |
|
From: Michael B. <mic...@gm...> - 2010-04-28 06:46:40
|
Hi Martin, > This one has a problem - there is a quadrilateral off the right edge of > the bottom-right 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 co-linear 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: Michael B. <mic...@gm...> - 2010-04-28 09:48:07
|
> Actually this prompts a definitional question: for a triangulation to > be valid must it use all hole vertices (other than co-linear 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: Asger S. S. P. <AS...@bl...> - 2010-04-28 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:mic...@gm...] Sent: 28. april 2010 11:48 To: jts...@li... Subject: Re: [Jts-topo-suite-user] Triangulating polygons? > Actually this prompts a definitional question: for a triangulation to > be valid must it use all hole vertices (other than co-linear 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 ------------------------------------------------------------------------ ------ _______________________________________________ Jts-topo-suite-user mailing list Jts...@li... https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user |
|
From: Michael B. <mic...@gm...> - 2010-04-28 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 <AS...@bl...> 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: Martin D. <mb...@re...> - 2010-04-28 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:mic...@gm...] > Sent: 28. april 2010 11:48 > To: jts...@li... > Subject: Re: [Jts-topo-suite-user] Triangulating polygons? > > >> Actually this prompts a definitional question: for a triangulation to >> be valid must it use all hole vertices (other than co-linear 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 > > ------------------------------------------------------------------------ > ------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 |
|
From: Michael B. <mic...@gm...> - 2010-04-29 00:33:07
|
On 29 April 2010 02:11, Martin Davis <mb...@re...> wrote: > I agree. I think it's standard that for a valid triangualation all vertices > must be used. > Including, for example, co-linear vertices on the polygon's exterior ? In Asger's example the co-linear 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 edge-flipping. Michael |
|
From: Martin D. <mtn...@te...> - 2010-04-29 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 <mb...@re...> wrote: > >> I agree. I think it's standard that for a valid triangualation all vertices >> must be used. >> >> > > Including, for example, co-linear vertices on the polygon's exterior ? > > In Asger's example the co-linear 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 edge-flipping. > > Michael > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |
|
From: Michael B. <mic...@gm...> - 2010-04-29 10:03:59
|
A bit more progress... House-with-diamond-hole polygon: triangulation followed by edge-flipping... http://imagebin.org/94930 Michael |
|
From: Martin D. <mtn...@te...> - 2010-04-30 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... > > House-with-diamond-hole polygon: triangulation followed by edge-flipping... > http://imagebin.org/94930 > > Michael > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |
|
From: Michael B. <mic...@gm...> - 2010-04-30 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 edge-flipping code needs more work. It presently has problems with the 5-square-holes 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: Michael B. <mic...@gm...> - 2010-05-02 12:39:39
Attachments:
triangulate.zip
|
Hi all, The triangulation code now handles co-linear vertices as discussed and does 'edge-flipping' improvement of the preliminary result. The attached zip file contains all of the code (as a Netbeans project). Demo.java is a demo app that lets you choose from several test polygons (the ones that I've been posting images of) and displays the result in swing widget. These test polygons are also used for unit tests which check that all polygon vertices are used in the triangulation and that the result polygons match up to the original polygon. See TestPolygonProvider.java if you want to add some more polygons. I've concentrated on getting the code to work with all test cases but haven't spent any time at all on making it efficient or elegant. I figure that can come later as it is incorporated into JTS. Please let me know if it works for you or not. cheers Michael |
|
From: Michael B. <mic...@gm...> - 2010-05-03 02:45:37
Attachments:
EarClipper.java
|
Hi folks, Small update. I realized the improvement algorithm was missing some opportunities to flip edges between pairs of triangles that had become adjacent after earlier improvements. The attached new version of EarClipper.java fixes this (in a brute force fashion). It also adds a few extra comments to the code. Michael |
|
From: Michael B. <mic...@gm...> - 2010-05-05 05:28:58
Attachments:
triangulate_05052010.zip
|
Attached is another update of the code. This just adds a couple of extra test cases: a simple triangle to make sure that the algorithm doesn't fail when there's nothing to do and a square with extra vertices on opposite edges. Michael |
Thanks for helping keep SourceForge clean.
X