Problems with relations

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Problems with relations

triplederby100-propos
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Problems with relations

Martin Davis
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Problems with relations

triplederby100-propos
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Re: Problems with relations

Martin Davis
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
Loading...