I have following two geometries and trying to establish relation between them. (a) POLYGON ((1368.62186660165 17722.3281808793, -1653 9287.5, 4038.14058906538 8613.02390521266, 1368.62186660165 17722.3281808793)) (b) POLYGON ((-5846 9287.5, 7453 8380, 9082 16600, -6326.5 18842, -5846 9287.5)) The polygon (a) is fully inside the polygon (b) with two of its vertices on the edge of the polygon (b). However, when I load them into the JTS Test Builder and run the predicates, it reports then to be having Overlap relationship. Is there anything wrong here? These geometries come from a popular CAD program and according to it, they don't have any overlap. I think this could be due to numerical precision issues across different software and I was wondering if anyone has any advice on avoiding them. Thanks! Jatin _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
JTS predicates are computed exactly, using the full precision of the
double-precision coordinates. The Overlaps result is correct - the bottom right point in the triangle (b) lies outside the quadrilateral (a). (You can see this if you intersect the edge of (a) LINESTRING (-5846 9287.5, 7453 8380) with (b) - the value of the intersection is a line segment LINESTRING (4038.140589065375 8613.02390521266, 4038.14058906538 8613.02390521266) It's possible that your CAD package is computing in lower precision, or rounding the coordinates, or using some sort of tolerance. One way to reduce these issues is to ensure that all input coordinates are rounded to a reasonable precision (e.g. less than 16 digits!). However, if a software package is using an internal tolerance for intersections there will always be cases where it produces a different result to JTS, which uses the exact geometry for computation. At that point you might choose to fund me to develop a tolerance-based model for JTS.... 8^) [hidden email] wrote: > I have following two geometries and trying to establish relation > between them. > > (a) POLYGON ((1368.62186660165 17722.3281808793, -1653 9287.5, > 4038.14058906538 8613.02390521266, 1368.62186660165 17722.3281808793)) > > (b) POLYGON ((-5846 9287.5, 7453 8380, 9082 16600, -6326.5 18842, > -5846 9287.5)) > > The polygon (a) is fully inside the polygon (b) with two of its > vertices on the edge of the polygon (b). However, when I load them > into the JTS Test Builder and run the predicates, it reports then to > be having Overlap relationship. Is there anything wrong here? > > These geometries come from a popular CAD program and according to it, > they don't have any overlap. I think this could be due to numerical > precision issues across different software and I was wondering if > anyone has any advice on avoiding them. > > Thanks! Jatin > > > > ------------------------------------------------------------------------ > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
In reply to this post by triplederby100-propos
HI Martin, Thanks for the reply. Yes, I did try playing with reasonable precision, but with different use cases it was different precision that yielded "expected" results. IMO, this is not the desired approach to address this issue. I have recognized the fact that NTS results could be different from other models that use some tolerances as you mention. For now I have relaxed some of the spatial relation conditions at the application logic level to "solve" (aka avoid) this issue - and I wish I had the resources available to fund the tolerance based model :) BTW, can you share some insight on how such tolerance based model could \be designed/implemented in JTS? Thank you, Jatin =============== Date: Thu, 18 Sep 2008 16:59:33 -0700 From: Martin Davis <[hidden email]> Subject: Re: [jts-devel] Problems with relations To: JTS Topology Suite Development <[hidden email]> Message-ID: <[hidden email]> Content-Type: text/plain; charset=ISO-8859-1; format=flowed JTS predicates are computed exactly, using the full precision of the double-precision coordinates. The Overlaps result is correct - the bottom right point in the triangle (b) lies outside the quadrilateral (a). (You can see this if you intersect the edge of (a) LINESTRING (-5846 9287.5, 7453 8380) with (b) - the value of the intersection is a line segment LINESTRING (4038.140589065375 8613.02390521266, 4038.14058906538 8613.02390521266) It's possible that your CAD package is computing in lower precision, or rounding the coordinates, or using some sort of tolerance. One way to reduce these issues is to ensure that all input coordinates are rounded to a reasonable precision (e.g. less than 16 digits!). However, if a software package is using an internal tolerance for intersections there will always be cases where it produces a different result to JTS, which uses the exact geometry for computation. At that point you might choose to fund me to develop a tolerance-based model for JTS.... 8^) _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Adding a tolerance capability to the predicates would actually be fairly
straightforward, I think. It would basically involve snap-rounding the input geometries together using the given tolerance. What snap-rounding does is to replace every node/vertex with a "tolerance square". Every line segment which intersects a tolerance square is considered to have a node introduced at that point. The geometries computed by the snap-rounding would then have the existing predicate code run on them to produce the final result. For efficiency, the snap-rounding would be carried out in an "on-the-fly, as needed" kind of way. I think this approach is similar to the way Oracle Spatial works. I also *think* it will produce results which correspond to a "reasonable" idea of what a "tolerance" should do. One problem here is that AFAIK there is no formal theory of tolerance-based geometric functions (and Oracle certainly doesn't provide full semantics for their operations). This means that it's a bit hard to tell if my understanding of "tolerance-based" is the same as yours. You clearly have at least an intuition of what "expected" results should be. Absent a formal description, it would probably need some test cases to be tried to confirm that the two models are compatible. Your approach of "relaxing spatial relation conditions" sounds like a wise approach, to avoid issues of inexactness. Can you give some more details of what conditions you are relaxing? [hidden email] wrote: > HI Martin, > > Thanks for the reply. Yes, I did try playing with > reasonable precision, but with different use cases it was different > precision that yielded "expected" results. IMO, this is not the desired > approach to address this issue. I have recognized the fact that > NTS results could be different from other models that use some > tolerances as you mention. > > For now I have relaxed some of the spatial relation conditions at the > application logic level to "solve" (aka avoid) this issue - and I wish > I had the > resources available to fund the tolerance based model :) BTW, can > you share some insight on how such tolerance based model could > \be designed/implemented in JTS? > > Thank you, > > Jatin > =============== > > Date: Thu, 18 Sep 2008 16:59:33 -0700 > From: Martin Davis <[hidden email] > <mailto:[hidden email]>> > Subject: Re: [jts-devel] Problems with relations > To: JTS Topology Suite Development <[hidden email] > <mailto:[hidden email]>> > Message-ID: <[hidden email] > <mailto:[hidden email]>> > Content-Type: text/plain; charset=ISO-8859-1; format=flowed > > JTS predicates are computed exactly, using the full precision of the > double-precision coordinates. The Overlaps result is correct - the > bottom right point in the triangle (b) lies outside the quadrilateral > (a). (You can see this if you intersect the edge of (a) > > LINESTRING (-5846 9287.5, 7453 8380) > > with (b) - the value of the intersection is a line segment > > LINESTRING (4038.140589065375 8613.02390521266, 4038.14058906538 > 8613.02390521266) > > It's possible that your CAD package is computing in lower precision, or > rounding the coordinates, or using some sort of tolerance. > > One way to reduce these issues is to ensure that all input coordinates > are rounded to a reasonable precision (e.g. less than 16 digits!). > However, if a software package is using an internal tolerance for > intersections there will always be cases where it produces a different > result to JTS, which uses the exact geometry for computation. At that > point you might choose to fund me to develop a tolerance-based model for > JTS.... 8^) > > > ------------------------------------------------------------------------ > > _______________________________________________ > jts-devel mailing list > [hidden email] > http://lists.refractions.net/mailman/listinfo/jts-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel |
Free forum by Nabble | Edit this page |