[OSM-dev] Area clipping in OSM

[Sandor Seres]

	Generally, clipping a set A by a set B means extract from A elements being elements of B as well. In GIS and digital mapping, we are interested in 2D clipping of the RW's geometry models by a polygon defined area. While clipping of the node/point and polyline subjects is a simple procedure, clipping areas is much more complex and complicated. As a rule, the areas are defined by enclosing and excluding border polygons. These polygons may be huge (in number of nodes/edges) and complicated (in shapes) like the global ocean, continents, lakes, rivers, forests... At the end, the area clipping is based on polygon by polygon clipping. As we know, there are four typical clipping cases depending on the relation between the subject and the clipping polygon. The two polygons have no common points, the subject polygon is inside the clipping polygon, the clipping polygon is inside the subject polygon and the two polygons intersect. There are simple filters and algorithms to detect the first three cases. The situation with the last case is much more complicate. As someone said, "the hunt for the perfect/best clipping algorithm is still open". 
	Most of the polygon clipping algorithms come from the Polygon Algebra and at a general level it is the same simple model: part(s) of the subject polygon being outside the clipping polygon are replaced by polyline(s) created from the clipping polygon edge vectors or segments of these. Because the subject polygon may have a strange course around the clipping polygon (going back and forth around) the replacement polyline, as a rule, has overlapping segments. Consequently, the clipped polygon is frequently a "degenerated polygon". Robust rendering systems should handle degenerated polygons, but most users transform them to simple polygons. However, even after the mentioned transformation "degenerated areas" are inevitably present where clipped hole polygons partly overlap the clipped outer polygon. In the latter case even more complex transformation is needed if we want to satisfy the OGC requirements. All these transformations are very expensive in form of time/performance. One special option of the polygon clipping is of particular interest, namely, when the clipping polygon is a rectangular frame. Applying a general clipping algorithm for rectangular clipping, though formally correct, may be highly impractical. It is too slow for essential GIS functions like the vector tiling, change detection... just to mention some. While the tiling speed is less relevant for the traditional (old fashioned) pre-tiling-based map-making technologies, it is a strong limiting factor in the modern online/on-the-fly tiling-based vector data service.
	Searching the Web for rectangular polygon clipping algorithms will, as a rule, end up with high level model specifications as described earlier. Searching for performance related data ends up even worse. There are some open-source benchmarks, but the subject polygons are exceptionally simple. Also, it is strongly underlined, the clipping performance depends how the clipping program is applied. For instance, tiling the OSM land polygons to 5km square tiles may drastically differ in performance whether the same clipping algorithm is applied in a single procedure or in a multistep/multi-tiling procedure. So, the real benchmark of a clipping program is done via repeated vector tiling procedure performed on the large set of complicated polygons like the Planet land polygons, or lakes, or forests, or rivers... Such clipping performance related data will be forwarded next time in the context of notes in "Coastline, from another angle". A very fast clipping algorithm uses (almost) exclusively comparations and some integer Boolean operations. If you want to make your own fast clipping algorithm, here are the basic hints.
	Assume, all areas are in the primitive (simplest) representation, one outer and, eventually, some inner polygons. The outer and the inner polygons have opposite orientations, e.g., cw and ccw. For the areas to be clipped, following the polygons (outer and some inner) in the correct direction , detect all polylines (PLi) starting with an out-in (OI) crossing point and ending with an in-out (IO) crossing point. Besides these strictly inside polylines, detect all polylines (PLj) on the edges of the clipping rectangle between two consecutive IO and OI points in the cw direction. Combining/connecting the PLi and PLj polylines result in a new set of clipped outer polygons. Note that there is no need for the complicated transformations mentioned before. The outer polygons in the result are all simple closed polygons and degenerated polylines and areas should never appear. Any of the remaining inner polygons strictly inside the clipping rectangle must be an inner polygon in one of the new outer polygons. In which one, it is enough to check a single point of the subject inner polygon. A program, based on this algorithm, is compact and extraordinary fast. Don't regret the time to try it.
Regards, Sandor.