Algorithm for splitting polygons/polylines into multiple sections at 180° E/W

Question

I have code (in C++) that draws various polygons on a map that uses a cylindrical projection (typically Mercator, sometimes Miller Equidistant if you want to be precise). For simple polygons, curves are drawn between vertices through a set of tiepoints such that the line roughly forms either the great circle segment or rhumb line between the two vertices. The more complex polygons also include arcs which generally don't form part of a great circle or rhumb line. At the time of drawing, the tiepoints that make up the polygons are translated into screen positions and drawn using built-in Windows C++ drawing commands.

For the most part, all my polygons and polylines are drawing fine, but I'm encountering problems when at least one line crosses the 180° meridian. My display is effectively limited to 180° W to 180° E.

One solution I've considered is to unwrap the points that make up the polygon, perform some mathematical wizardry to calculate the screen position for points outside of [-180, 180], and then draw the object twice, once for 180° W and then again for 180° E. Unfortunately this method falls apart if there are 2 consecutive crossings in the same direction. As unlikely as that is to happen in my case, the mere possibility has me worried. It also doesn't work for objects that enclose one of the poles.

Is there an algorithm for splitting a polygon along the 180° meridian while also properly closing it? Bonus points if it also works for polygons that enclose one of the poles. Extra bonus points if it'll also work for polar and/or conic projections (not currently supported, but may be required in a later project).

Answer 1

For the polygon clipping part, I recommend using the Clipper library, it's available in several programming languages. If you want to keep the great circle, you can always adjust/recalculate the latitudes of the new partition vertices after the polygon has been split.

Answer 2

In order to simplify the problem, I switched from drawing curves through a set of tie points from one vertex to the next to just drawing straight lines between each tie point/vertex. This effectively means that I don't have to worry about starting a new curve at each vertex.

So as where I had a vector of curves (which was a vector of points) that comprised a polygon, I now have a single vector of points, and don't distinguish between a vertex and a tie point, at least as far as drawing is concerned.

From here, I pass this vector of points into my unwrap-split-rewrap routine, which doesn't actually unwrap or rewrap the points of the polygon, although conceptually, that's what's happening. The routine splits the polygon by returning a vector of lines, where none of the lines cross the antimeridian. The routine determines if a line needs to be split based on the difference of the longitude of the two endpoints: if the difference is more than 180°, then split the line. I use a naive Cartesian method for determining the latitude on the antimeridian that the line crosses. I know this isn't very accurate, but it's sufficiently close that I'm not worried about drawing errors; I have larger errors elsewhere.

At this point, I have a vector of lines in which none of the lines cross the antimeridian, and I go about merging these lines in order to have closed polygons on the screen. Of course, if the object to be drawn isn't closed, the following routine isn't run. Also, if a closed polygon crosses the antimeridian an odd number of times, meaning that the object encloses one of the poles, then the routine isn't run. The reason for this should become apparent. In order to close a polygon that has been split across the antimeridian, the latitudes at which the polygon crosses the antimeridian are ordered from North to South. On each side of the antimeridian, the line that corresponds with the first latitude are merged (concatenated) with the line that corresponds with the second latitude in the list. If the two latitudes correspond to the same line on a single side, then that line is effectively set aside since it has just been closed. The first and second latitudes are removed from the list, and this process is repeated (recursively) until the latitude list is empty. For anyone interested in the implementation details of this routine, I can expand on them in the comments. Suffice it to say they aren't terribly important for the solution.

I now have a vector of closed polygons (or simple polylines if the object isn't or couldn't be closed). It's a simple matter to convert the lat/lon pairs of the polygons to screen x/y coordinates for drawing.

While this solution doesn't work for an object that encloses a pole, it should be relatively straight forward to modify it to, for instance, always assume that an object that encloses a pole always encloses the north pole, or to use the most extreme latitude to determine which pole is enclosed. Objects that enclose a pole are still split properly (excepting one edge case right now), though, so their component lines are still drawn, albeit the object isn't closed and filled. Additionally, this solution should also work for a polar projection, excepting the above issue.