Splitting polygonal geometry at a meridian

[tzakharko]

Many legacy tools do not support true geometry on the sphere, leading to artifacts and processing problem when working with polygons that "wrap around" the antimeridian. Similar problem exists when plotting maps centered on a meridian different from the prime. So avoid artifacts, the affected geometry should be split along the target meridians so that no edge intersects it, creating new geometry that touch but not cross the meridian.

There is some mention of such a procedure in S2 code, which involves subtracting a degenerate polygon loop modeling the meridian from the original polygon .e.g. here. While this splits the edges (introducing new vertices), it does not actually split the geometry (you get the original geometry with extra vertices inserted). I'd like the operation to produce the list of polygons splits along the line instead. Is there a straightforward way to achieve that?

[jmr]

It seems if you're going to draw polygons on a planar map, you're going to need to break up the geodesic edges anyway. Handling the anti-meridian can be part of that process.

[tzakharko]

Is there a particular approach you can recommend? I can do it easily enough for simpler loops, but it gets tricky if I have holes etc. I hoped to use S2 to do the heavy lifting for me.

[smcallis]

Edges are guaranteed to be < 180 degrees, so if an edge crosses the anti-meridian, one of its vertices will be on the positive half of the plane defined by the anti-merdian's normal, and the other on the negative half. You could use SignDotProd to test this and split the edge manually: https://github.com/google/s2geometry/blob/master/src/s2/s2predicates.h#L167-L170 .

…

On Fri, Jul 4, 2025 at 6:24 AM Taras Zakharko ***@***.***> wrote: Is there a particular approach you can recommend? I can do it easily enough for simpler loops, but it gets tricky if I have holes etc. I hoped to use S2 to do the heavy lifting for me. — Reply to this email directly, view it on GitHub <#439 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGEMKQMLFBIDNTTN67HI433GZW77AVCNFSM6AAAAACAY7GS36VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTGNRWGI4TCNY> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[ericveach]

HI Tara, The technique of subtracting a degenerate antimeridian is intended to do the "heavy lifting" as you supposed. And in fact there is (or was) internal Google code that uses this technique to reliably convert S2 geometry to JSON or similar standard encodings. In addition to subtracting the antimeridian, this code uses S2EdgeTessellator to split geodesic edges until they can be represented by straight edges in a given projection (e.g. Mercator) to within a given tolerance. Unfortunately this code isn't part of the open-source S2 library, I think because it has additional dependencies. I no longer have access to it, but perhaps Jesse does. The main trick is that after subtracting the antimeridian, you need to use the appropriate options to S2Builder to prevent polygons from being put back together across the antimeridian again. In particular you need to use s2builderutil::LaxPolygonLayer just like the test code you found does. That's pretty much all that's necessary in the case of polygons. For polylines, you need some additional logic; extra vertices will have been added wherever they cross the antimeridian, but you need to split the polylines at those vertices yourself. Note that even though you might think you could just do this yourself easily, without involving S2Builder, that S2Builder makes the additional guarantee that despite doing all this extra splitting and subtracting, the original topology is preserved, i.e. no new edge crossings will be created due to edges moving slightly when new vertices are introduced. If you're seeing the original polygons being put back together across the antimeridian, that's probably because you are trying to represent the result as an S2Polygon. You need to use S2LaxPolygonShape to represent the result correctly. Eric

…

On Fri, Jul 4, 2025 at 8:48 AM smcallis ***@***.***> wrote: Edges are guaranteed to be < 180 degrees, so if an edge crosses the anti-meridian, one of its vertices will be on the positive half of the plane defined by the anti-merdian's normal, and the other on the negative half. You could use SignDotProd to test this and split the edge manually: https://github.com/google/s2geometry/blob/master/src/s2/s2predicates.h#L167-L170 . On Fri, Jul 4, 2025 at 6:24 AM Taras Zakharko ***@***.***> wrote: > Is there a particular approach you can recommend? I can do it easily > enough for simpler loops, but it gets tricky if I have holes etc. I hoped > to use S2 to do the heavy lifting for me. > > — > Reply to this email directly, view it on GitHub > < #439 (reply in thread)>, > or unsubscribe > < https://github.com/notifications/unsubscribe-auth/AAGEMKQMLFBIDNTTN67HI433GZW77AVCNFSM6AAAAACAY7GS36VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTGNRWGI4TCNY> > . > You are receiving this because you are subscribed to this thread.Message > ID: ***@***.***> > — Reply to this email directly, view it on GitHub <#439 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AICG3CWBRM4ADOGXT3AEVKD3G2O5HAVCNFSM6AAAAACAY7GS36VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTGNRWGQ3DCNI> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[tzakharko]

Many thanks, Eric!

Ultimately, I want to output validated polygons, so I suppose that I should pass the output LaxPolygonLayer through an additional S2Builder step. Is there sample code showing the best way to do it? Still trying to get my bearings.

[ericveach]

Hi Taras, This is a complex topic. What do you mean by "validated"? S2Builder guarantees that as long as you provide valid input geometry, it will generate valid output geometry with no need for additional validation. S2LaxPolygons (really S2LaxPolygonShape) are just as valid as S2Polygons, and can be used as inputs to pretty much any S2 operation, it's just that they are capable of representing degenerate geometry (unlike S2Polygon). Pretty much all S2 operations, including subtraction, use S2Builder for their output stage. So if by "validated polygons" you mean "validated S2LaxPolygons", that should already be true (as long as your input geometry was valid). If you mean "validated S2Polygons", then running the output through S2Builder again won't help because S2Polygons are not capable of representing the output you want---that's why you need to use S2LaxPolygon in the first place. The problem is that when you split a polygon at the antimeridian, the resulting polygon has two coincident edges in opposite directions (following the antimeridian), and S2Polygon doesn't allow that. (A pair of such edges defines a degenerate hole in the polygon.) So it's essential to keep the output as an S2LaxPolygon if you don't want the split along the antimeridian to be merged back together. Alternatively, if by "validated geometry" you mean "geometry that can be processed by other 2D geometry tools", things get more complicated. Generally 2D software represents polygon edges as straight lines in a given projection (such as Mercator or the simple rectangular or "plate carree" projection), but S2 uses spherical geodesic edges. That means that when you have a long edge, it needs to be broken into shorter segments to create an adequate approximation. That's where S2EdgeTessellator comes in. That brings up another issue, because when you approximate geodesics with straight edges in this way it can create new intersections. For example, suppose your polygon has two edges 10 km long and 1 cm apart that turn into two curved lines in your chosen 2D projection. If these two lines are approximated separately as a sequence of straight edges, they will likely cross each many times. Now many "legacy tools" actually deal just fine with this sort of geometry, but if your goal is to have 2D projected geometry without self-intersections, you need to "snap" the input geometry first to ensure that no edges are too close together. This is the sort of finicky detail that the non-open-source code that converts S2 geometry to 2D geometry deals with. Anyway, I hope some of this was helpful. Cheers, Eric

…

On Sat, Jul 5, 2025 at 12:32 AM Taras Zakharko ***@***.***> wrote: Many thanks, Eric! Ultimately, I want to output validated polygons, so I suppose that I should pass the output LaxPolygonLayer through an additional S2Builder step. Is there sample code showing the best way to do it? Still trying to get my bearings. — Reply to this email directly, view it on GitHub <#439 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AICG3CS4YYLHJTL4GDYK5DT3G55QFAVCNFSM6AAAAACAY7GS36VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTGNRWG44TONA> . You are receiving this because you commented.Message ID: ***@***.***>

[tzakharko]

Many thanks for the detailed write up, Eric. I see that this is a complicated matter. What I was hoping to obtain as a result is a list of S2Polygons such that each of them meets the meridian at the boundary (but not in the interior), and, when joined together, would produce the original polygon again.

I do have some hand-written code for doing such splits for convex polygons (which is quite trivial — find two intersection points and run two loops in opposite directions), but things get considerably more complex when concave polygons and polygons with holes are concerned.

I was hoping for an out of the box solution since unfortunately I don't have the engineering bandwidth to tackle this property at this point. For the time being, I work around the issue by subtracting a very thin polygon modeling the meridian from the problematic geometry. While this does clip some of the edges, the resulting error is minimal and good enough for my application.

Many thanks again!

[ericveach]

Yes, that's a fine workaround. Another approach that might work is to subtract the degenerate antimeridian and one other meridian, but that approach would still be more complicated because you would need to convert the output to a set of S2Polygons rather than a single S2Polygon with multiple loops. Cheers, Eric

…

On Thu, Jul 10, 2025 at 8:24 AM Taras Zakharko ***@***.***> wrote: Many thanks for the detailed write up, Eric. I see that this is a complicated matter. What I was hoping to obtain as a result is a list of several S2Polygons such that each of them meets the meridian at the boundary (but not in the interior), and, when joined together, would produce the original polygon again. I do have some hand-written code for doing such splits for convex polygons (which is quite trivial — find two intersection points and run two loops in opposite directions), but things get considerably more complex when concave polygons and polygons with holes are concerned. I was hoping for an out of the box solution since unfortunately I don't have the engineering bandwidth to tackle this property at this point. For the time being, I work around the issue by subtracting a very thin polygon modeling the meridian from the problematic geometry. While this does clip some of the edges, the resulting error is minimal and good enough for my application. Many thanks again! — Reply to this email directly, view it on GitHub <#439 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AICG3CQNKLUNS46EHYZT3O33H2AUBAVCNFSM6AAAAACAY7GS36VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTGNZSGIZDCNQ> . You are receiving this because you commented.Message ID: ***@***.***>