Java Port

[Eric Angle]

I'm interested in trying the S2 Java port but am weary of the statement

"Be aware that this port is based on the 2011 release of the S2 library, and does not have the same robustness, performance, or features as the current C++ implementation."

found here: http://s2geometry.io/about/overview

Is there any detailed information on what the Java port might lack in robustness? If it helps, I'm specifically interested in computing intersections of polygons (not the intersects predicate / boolean).

[Mark Heath]

I can't give detailed information about it.  But I can say that the polygon intersection (initToIntersection) is not robust. I've had it fail when a line segment falls ontop of another line segment.  This also occurs with the union polygon builder.  I've been unsuccessful in implementing a work around to the issue.  I don't know all the cases where it fails I was using triangular polygons that would frequently be adjoining and mainly doing unions.  

I haven't had any issues with intersecting polygons with cell generated polygons using the s2regioncoverer, where there is a clear overlap.

I'm not sure how much of an easy task it would be to port the existing C++ code to Java.   I'm contemplating writing my own boolean operations with S2, since all the libraries which have boolean operations don't support spherical geometry,  so it might be simpler just to port the c++ code.   

interested in helping with such a port?

[Eric Engle]

Mark, can you say more about the conditions in which you get invalid results? In particular, the line segment falling on top of line segment criteria makes it sound like you're expecting an OGC-like sensitivity to the boundary of polygons, but S2's data model is slightly different. I'm happy to set more concrete expectations, if you can cook up a specific example that isn't behaving in the manner you expect.

Kind regards,

Eric

--
You received this message because you are subscribed to the Google Groups "s2geometry-io" group.
To unsubscribe from this group and stop receiving emails from it, send an email to s2geometry-i...@googlegroups.com.
To post to this group, send email to s2geom...@googlegroups.com.
Visit this group at https://groups.google.com/group/s2geometry-io.
To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/2f9d94ac-d58b-478b-93f9-e7a3d559f3a9%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Mark Heath]

The overview of my example is; I'm drawing a polygon of a region that can/cannot be seen from a single point.  There are a number of objects in the way that create this shadow.

I end up with a polygon of points [A,B,C,D] and [A,B,E,F] where BE crosses CD and AD is a segment of AF I then call the static method initToUnion and get the Bad Directed Edges assertion.  And one of the polygons is dropped from the result.  I believe initToIntersection also has the same assertion.

(com.google.common.geometry.S2Polygon initToUnionSloppy

SEVERE: Bad directed edges)

Unfortunately due to my data set, these duplicate AB edges are inherent to the data. I'm also using a clipping polygon (otherwise the shadows would extend to the antipode) and end up with shared segments.

I've also tried using the PolygonBuilder and adding the two polygons without success. 

just synthesising some data off the top of my head, A=0,0 B=0,2 C=-2,2 D=-2,0 E=-3,1 F=-3,0

Sorry I had written this code several months ago and left it in the too hard basket when I couldn't solve this issue.  There's now been renewed interest in this project so I went looking for boolean operations on geodesic polygons libraries or algorithms and discovered that the C++ S2 code has robust boolean operations, which led me here.

I can dig up some more specific examples.

On Saturday, 25 May 2019 01:27:45 UTC+10, Eric Engle wrote:

Mark, can you say more about the conditions in which you get invalid results? In particular, the line segment falling on top of line segment criteria makes it sound like you're expecting an OGC-like sensitivity to the boundary of polygons, but S2's data model is slightly different. I'm happy to set more concrete expectations, if you can cook up a specific example that isn't behaving in the manner you expect.

Kind regards,

Eric

On Fri, May 24, 2019 at 12:20 AM Mark Heath <silic...@gmail.com> wrote:

I can't give detailed information about it.  But I can say that the polygon intersection (initToIntersection) is not robust. I've had it fail when a line segment falls ontop of another line segment.  This also occurs with the union polygon builder.  I've been unsuccessful in implementing a work around to the issue.  I don't know all the cases where it fails I was using triangular polygons that would frequently be adjoining and mainly doing unions.  

I haven't had any issues with intersecting polygons with cell generated polygons using the s2regioncoverer, where there is a clear overlap.

I'm not sure how much of an easy task it would be to port the existing C++ code to Java.   I'm contemplating writing my own boolean operations with S2, since all the libraries which have boolean operations don't support spherical geometry,  so it might be simpler just to port the c++ code.   

interested in helping with such a port?

On Tuesday, 6 November 2018 04:58:08 UTC+11, Eric Angle wrote:

I'm interested in trying the S2 Java port but am weary of the statement

"Be aware that this port is based on the 2011 release of the S2 library, and does not have the same robustness, performance, or features as the current C++ implementation."

found here: http://s2geometry.io/about/overview

Is there any detailed information on what the Java port might lack in robustness? If it helps, I'm specifically interested in computing intersections of polygons (not the intersects predicate / boolean).

--
You received this message because you are subscribed to the Google Groups "s2geometry-io" group.

To unsubscribe from this group and stop receiving emails from it, send an email to s2geom...@googlegroups.com.

[Eric Engle]

"Bad directed edges" would be more accurate if it said "unused directed edges". It isn't an exception, it's just a log statement, and many users disable those logs because they're not usually indications of a problem.

More examples of your problem might be helpful, but first it'd be better to focus on this example a little closer. What is the actual result polygon that you get out? You said something was dropped, but what's left?

To unsubscribe from this group and stop receiving emails from it, send an email to s2geometry-i...@googlegroups.com.

To post to this group, send email to s2geom...@googlegroups.com.
Visit this group at https://groups.google.com/group/s2geometry-io.

To view this discussion on the web visit https://groups.google.com/d/msgid/s2geometry-io/a876bd73-a577-48f3-b550-8cdcad91558b%40googlegroups.com.

[Mark Heath]

Here is my test case.  The result is an empty polygon.  If you could help solve this it would be fantastic!

import com.google.common.geometry.*;

public class polyfail

{

       public static void main(String[] args) {

                S2LatLng a = S2LatLng.fromDegrees(0,0);

                S2LatLng b = S2LatLng.fromDegrees(0,2);

                S2LatLng c = S2LatLng.fromDegrees(-2,2);

                S2LatLng d = S2LatLng.fromDegrees(-2,0);

                S2LatLng e = S2LatLng.fromDegrees(-3,1);

                S2LatLng f = S2LatLng.fromDegrees(-3,0);

                S2PolygonBuilder pb;

pb = new S2PolygonBuilder(S2PolygonBuilder.Options.UNDIRECTED_XOR);

                pb.addEdge(a.toPoint(),b.toPoint());

                pb.addEdge(b.toPoint(),c.toPoint());

                pb.addEdge(c.toPoint(),d.toPoint());

                pb.addEdge(d.toPoint(),a.toPoint());

                S2Polygon p1 =  pb.assemblePolygon();

pb = new S2PolygonBuilder(S2PolygonBuilder.Options.UNDIRECTED_XOR);

                pb.addEdge(a.toPoint(),b.toPoint());

                pb.addEdge(b.toPoint(),e.toPoint());

                pb.addEdge(e.toPoint(),f.toPoint());

                pb.addEdge(f.toPoint(),a.toPoint());

                S2Polygon p2 =  pb.assemblePolygon();

System.out.println("polygon 1 " + p1);

System.out.println("polygon 2 " + p2);

S2Polygon p3 = new S2Polygon();

p3.initToUnion(p1,p2);

System.out.println("Result " + p3);

}

}

polygon 1 Polygon: (1) loops:

loop <

(-2.0, 0.0)

(-1.9999999999999996, 2.0)

(0.0, 2.0)

(0.0, 0.0)

>

polygon 2 Polygon: (1) loops:

loop <

(0.0, 2.0)

(0.0, 0.0)

(-3.0000000000000004, 0.0)

(-3.0000000000000004, 1.0)

>

May 26, 2019 10:04:22 AM com.google.common.geometry.S2Polygon initToUnionSloppy

SEVERE: Bad directed edges

Result Polygon: (0) loops:

[Mark Heath]

May 26, 2019 10:04:22 AM com.google.common.geometry.S2Polygon initToUnionSloppy

SEVERE: Bad directed edges

Result Polygon: (0) loops:

I forgot to mention that I get the same results with the initToIntersection method

May 26, 2019 10:19:09 AM com.google.common.geometry.S2Polygon initToIntersectionSloppy

SEVERE: Bad directed edges

Intersection Polygon: (0) loops: 

[Mark Heath]

Would you agree that this is a bug in the library?

Or I'm using an outdated library, and this has been fixed in a more recent version?

Or I'm using the library incorrectly?

Or this is just not a case that this library handles?

what might be the easiest fix?