5 ms·

Explaining it in terms of points and distances is an effort at making the content accessible, but the issues arise when you're dealing with complex shapes, whic

• zokier 6y ago
  > given a sequence of points representing a polygon, it will not always the case that the shorter line connecting two points is the intended one, for example > intersected polygon (under the same set of assumptions) has lines that suddenly go the other way around the world would be really cool to actually see these examples I do not doubt that naive great circle shortest path might fall apart in pathological cases, but I have difficulty understanding why that would be the case. And the article does nothing to explain why this seemingly obvious solution wouldn't work, your comment already was more enlightening.
  • NovemberWhiskey 6y ago
    Your simplest Euclidean polygon is the triangle. Imagine the triangle is defined by the cities of London, Tokyo and New York. Assuming the world is a sphere (which we know it isn't, but it's not disastrously wrong for these purposes), that gives you something that looks like this: http://gc.kls2.com/cgi-bin/gc?PATH=NYC-TYO-LON-NYC http://gc.kls2.com/cgi-bin/gc?PATH=NYC-TYO-LON-NYC The slightly-curved lines represent the shortest distance between those points; the great circle routes. Now take your typical world map (probably a Mercator projection) and draw the same triangle on it using straight lines along the shortest distances on the map. Notice that the triangle on the world map includes within its area a significant chunk of Central Asia and absolutely none of Greenland. Imagine how unsuccessful you would be trying to intersect the world-map triangle with another polygon; it would be completely meaningless.
    • zokier 6y ago
      obviously straight lines on (some) projections are very wonky on a sphere (or geoid), as would be shapes built on those lines. That was not really the question though, the question was that if you have shapes defined by points connected with shortest great circle paths then when (and how) would that fail? Sibling comment already raised the good point that great circles do not work that well on spheroids and other more complex models of Earth, but I got the impression that it was not what apendleton was referring to
  • apendleton 6y ago
    The situation I was talking about above is one I've observed in production but don't have samples at the ready for, so maybe I'll give another example of weird antemeridian stuff that doesn't require example idiosyncratic polygons: bounding boxes. We see cases in computational geometry all the time where people use [min_x,min_y,max_x,max_y] bounding boxes when operating on sets of points or polygons or whatever, usually either (a) as entries in some sort of a spatial index like an R-Tree, or (b) as part of some short-circuit to avoid a more expensive polygon operation (like, if the question is "is this point in this polygon?" if you have the polygon's bounding box pre-calculated, you can first cheaply check if the point is in the box before doing the expensive point-in-poly operation; likewise to see if two polygons intersect, you can see if their bounding boxes intersect first, etc.). Turns out though, that with the usual naive bounding box math, features like the US or Russia end up with bounding boxes that wrap all the way around the world in the X direction, which makes them pretty useless for those kinds of operations. So then you inevitably think "well, okay, we can have the bounding box cross the antemeridian." But then all kinds of assumptions about bounding boxes start to break down: suddenly your "minimum" can be bigger than your "maximum," and your point_in_bbox function that wasn't AM-aware breaks, as does your bboxes_intersect function. So then you fix those, but it turns out even the process of figuring out what the optimal bounding box of a multi-part geometry that can cross the antemeridian should be is non-trivial; imagining a multi-point geometry comprised of three points spaced equally in the X direction around the world, there are three possible distinct, equally optimally sized bounding boxes one could draw, so it turns out a given set of points doesn't have a unique optimal bounding box anymore either. Even assuming a set of points does though, you usually end up with an algorithm that looks for the biggest X-direction "gap" between components and makes that the part not in the bounding box, and the rest in. But that leads to yet more subtle weirdness: in non-wrapping geometry, for example, you can assume that if you have two sets of points, and calculate the bounding boxes for each, the bounding box of the union of the sets of points is the bounding box of the union of the bounding boxes. But in the wrapping/AM-crossing context, that's not necessarily the case anymore: your points could combine in such a way that that optimal largest "gap" is now in a different position, and you have a totally different bounding box over the combined sets of points than you would over the combined bounding boxes. etc., etc., etc. None of this is impossible to handle, but it's sort of akin to those "things programmers assume about dates" blog posts: most people, and especially people who live in the continental US, just don't think about any of this, and don't encounter it in US testing, and then their code totally breaks in bizarre ways once usage extends to other parts of the world because these corner cases are unaccounted for.