mapbox / vector-tile-spec

Mapbox Vector Tile specification
https://www.mapbox.com/vector-tiles/specification/
Other
879 stars 209 forks source link

Splines Type #114

Open flippmoke opened 6 years ago

flippmoke commented 6 years ago

We have a preliminary working set of vector tiles being created with a new data type that includes splines. The type of splines being used are b-splines. The control points of the spline are encoded in the same way a linestring would be encoded, with the knots being added to a new field of a repeated double in the Feature message.

Currently, the Spline is denoted by a GeomType

        enum GeomType {
             UNKNOWN = 0;
             POINT = 1;
             LINESTRING = 2;
             POLYGON = 3;
             SPLINE = 4;
        }

and knots for the Feature message being added to field 5:

repeated double knots = 5 [ packed = true ];

An example implementation of this is located here.

Pros

Cons

williamscraigm commented 6 years ago

CurveTo with variations as in SVG would be much more flexible for the polygon case. It would also better match most graphic design and GIS use cases.

flippmoke commented 6 years ago

@williamscraigm The one thing about a CurveTo that would worry me is that it could suddenly confuse existing geometry models if we did not properly have a different type. Granted interpolation could be used if you had a non curved model, but this could be challenging for a variety of reasons -- the one that concerns me the most is polygon validity. That said, I am not against such an introduction..

peterqliu commented 6 years ago

Whoa cool, I just cut a parallel ticket on the rendering side for this. Glad that it's on people's minds!

@flippmoke how would we handle splines when the line is chopped into tiles? I imagine that the curve on either side of the tile edge have different neighboring control points, potentially causing them to bend away from each other and not meet.

flippmoke commented 6 years ago

From my current level of understanding, there are time where splines are good and there are times where CurveTo would be good. I am wondering if both have a place here in the spec.

Splines would be difficult to chop across tile boundaries, but @mourner has found a way of doing this. The summary of how to do it would be to add extra control points at the point where the cut would take place etc.

Splines seem like they are superior for:

Curves seem like they are superior for:

joto commented 6 years ago

Thinking about the implementation of this I am a bit concerned about the repeated double knots being "external" to the rest of the geometry. Before this change the geometry was this self-contained unit with some magic inside. Anything that got the GeomType and this buffer with the geometry in it could interpret it without knowing anything else. Now we have to take the knots into account, lugging it around in a data structure even though most of the times it will not even be used.

Here is a (maybe whacky) idea: If you look at our current geometry

repeated uint32 geometry = 4 [ packed = true ];

This is encoded in the protobuf in the same way as

string geometry = 4

would be. So from now on we could treat the geometry as a black box, some blob that magically contains the geometry without Protobuf "knowing" about its contents. It mostly is anyways, because those uint32 values already encode a special format. For the existing geometry types nothing would change, but if you want to support the spline geom types, you need to understand the geometry blob in a new way.

Also: Do we need floating point values for the knots? Can we use some kind of fixed point here? What about delta-encoding or other schemes to reduce the amount of data?

ansis commented 6 years ago

My gut reaction here is that for a format that is used for delivering processed geodata (opposed to storing the original version) it isn't important to have the accuracy of curves/splines and that this adds unnecessary complexity.

williamscraigm commented 6 years ago

Curve data is fairly common in the geo world. It's especially common in land records where legal descriptions of parcels contain curved segments. A single parcel may have a curved segment and then a few straight segments. They're authored via manual editing in GIS applications or by entering a COGO traverse. Additionally, many cartographic workflows only work with Bezier curves for editing. Several GIS applications and data formats support curves: POSTGIS, Geopackage, Esri Geodatabases. A spec example would be the Esri JSON spec: https://developers.arcgis.com/documentation/common-data-types/geometry-objects.htm#CURVE

Approximating these curves with points is how they're handled in vector tiles now and it just bloats storage.

Additionally, I'd hope that curve support could lead to smaller storage for types that are not currently curves but could be (curvy lines).