Splitting large polygons can take hours

[xivk]

Splitting large polygons can take hours while there is a lot of room for improvement.

• Most of the tiles are 100% covered by the polygons.
• The polygons are split along the same lines at multiple zoom levels.

We should change the PolygonTiler to take advantage of these properties.

[xivk]

As a test case take the Russia boundary from OSM.

[FObermaier]

Adding an additional PreparedGeometry.Contains check to return the whole tile as geometry should improve the performance a lot:

    /// <summary>
    /// Returns all the tiles this polygon is part of and the polygonal portion in it..
    /// </summary>
    /// <param name="polygon">The linestring.</param>
    /// <param name="zoom">The zoom.</param>
    /// <param name="margin">The margin for the tiles polygon (in %)</param>
    /// <returns>An enumerable of all tiles.</returns>
    public static IEnumerable<(ulong, IPolygonal)> Tiles(Polygon polygon, int zoom, int margin = 5)
    {
        // Get the envelope
        var envelope = polygon.EnvelopeInternal;
        var lt = Tile.CreateAroundLocation(envelope.MaxY, envelope.MinX, zoom);
        if (lt == null) throw new Exception();
        var rb = Tile.CreateAroundLocation(envelope.MinY, envelope.MaxX, zoom);
        if (rb == null) throw new Exception();

        // Compute the possible tile range
        var tileRange = new TileRange(lt.X, lt.Y, rb.X,rb.Y, zoom);

        // Build a prepared geometry to perform faster intersection predicate
        var prep = Geometries.Prepared.PreparedGeometryFactory.Prepare(polygon);

        // Test polygon tiles.
        foreach (var tile in tileRange)
        {
            if (tile == null) continue;
            var testPolygon = tile.ToPolygon(margin);
            if (prep.Contains(testPolygon))
            {
                // the whole tile polygon is inside the geometry
                yield return (tile.Id, testPolygon);
            }
            else if (prep.Intersects(testPolygon))
            {
                // Compute the intersection geometry
                var result = polygon.Intersection(testPolygon);

                // Only return if result is polygonal
                if (result is IPolygonal polygonalResult)
                    yield return (tile.Id, polygonalResult);
            }
        }
    }