Skip to content

Geometry calculations

Position and position series objects introduced by coordinates and the geometry model discussed in simple geometry chapters provide multiple ways to manipulate coordinate data and access some common 2D cartesian geometric calculations.

This chapter guides you how to use the geometry model.

The following polygon geometry object is applied in all samples of this chapter:

// A polygon geometry (with an exterior ring and one interior ring as a hole).
final polygon = Polygon.build([
[35.0, 10.0, 45.0, 45.0, 15.0, 40.0, 10.0, 20.0, 35.0, 10.0],
[20.0, 30.0, 35.0, 35.0, 30.0, 20.0, 20.0, 30.0],
]);

This sample polygon illustrated:


Bounding box

The previous chapter explained how to access and populate bounding boxes on geometry objects.

As a short recap let’s calculate a bounding box for our sample polygon.

// Prints: "Bounding box: 10.0,10.0,45.0,45.0"
// Values contained in the bbox in this case: min-x, min-y, max-x, max-y
final bbox = polygon.calculateBounds();
print('Bounding box: ${bbox?.toText(decimals: 1, compactNums: false)}');

You can calculate also the center point of a bounding box.

// Bbox center, prints: "Bbox center: 27.5,27.5"
final center = bbox?.aligned2D();
print('Bbox center: ${center?.toText(decimals: 1)}');

It’s also possible to calculate aligned points inside a bounding box, not only the center point. Here are the aligment attributes:

  • x = The horizontal distance fraction.
    • The value -1.0 represents the west side edge of the box.
    • The value 0.0 represents the center horizontally.
    • The value 1.0 represents the east side edge of the box.
  • y = The vertical distance fraction.
    • The value -1.0 represents the south side edge of the box.
    • The value 0.0 represents the center vertically.
    • The value 1.0 represents the north side edge of the box.

Below Aligned(x: 0.5, y: 0.5) is used.

// Bbox aligned, prints: "Bbox aligned: 36.250,36.250"
final aligned = bbox?.aligned2D(Aligned(x: 0.5, y: 0.5));
print('Bbox aligned: ${aligned?.toText(decimals: 3)}');

Centroid

The centroid is - as by definition - a geometric center of mass of a geometry.

The centroid is computed according to dimensionality of a geometry:

  • areal geometries: weighted by the area of areal geometries like polygons.
  • linear geometries: computed from midpoints of line segments that are weighted by the length of each line segment.
  • punctual geometries: the arithmetic mean of all separate positions.

Note that a centroid do not always locate inside a geometry.

The following sample shows how to calculate it for a polygon.

// Prints: "Centroid pos: 27.407,28.765"
final centroid = polygon.centroid2D();
print('Centroid pos: ${centroid?.toText(decimals: 3)}');

Also other geometry types provide centroid2D method.

Polylabel

The problem with centroids for polygons is that they do not always locate inside a geometry.

To counter this issue Mapbox has developed an Open-Source algorithm called polylabel that is a fast algorithm for finding polygon pole of inaccessibility, the most distant internal point from the polygon exterior ring.

For more background details please see also the blog post (Aug 2016) by Vladimir Agafonkin introducing the algorithm.

The geobase package has a ported version of this algorithm. Using it is as easy as calling centroid.

// Prints: "Polylabel pos: 17.65625,24.21875 dist: 5.745242597140699"
final p = polygon.polylabel2D(precision: 2.0);
print('Polylabel pos: ${p.position} dist: ${p.distance}');

The result position is inside polygon area and you also get a distance from this point to the polygon outline.

Point-in-polygon

The point-in-polygon algorithm can be used for checking whether a position is inside a polygon:

  • polygons without holes: checks whether a position is inside a polygon outer ring
  • polygons with holes: checks whether a position is inside a polygon outer ring, but not inside any holes or inner rings
// prints: (20,20) => true, (10,10) => false
final inside = polygon.isPointInPolygon2D([20.0, 20.0].xy);
final outside = polygon.isPointInPolygon2D([10.0, 10.0].xy);
print('(20,20) => $inside, (10,10) => $outside');

Distance to point

All geometry classes has also the method distanceTo2D that returns a distance from a geometry to a destination position calculated in a cartesian 2D plane.

The distance is computed according to dimensionality of a geometry:

  • areal geometries: a shortest distance to the outline of a polygon
  • linear geometries: a distance to the nearest line segment
  • punctual geometries: a distance to the nearest position
// prints: (20,20) => 3.7139067635410368, (10,10) => 9.284766908852593
final dist1 = polygon.distanceTo2D([20.0, 20.0].xy);
final dist2 = polygon.distanceTo2D([10.0, 10.0].xy);
print('(20,20) => $dist1, (10,10) => $dist2');

As noted this functionality is supported for other geometry types too.

Outline length

Polygons are formed of exactly one exterior or outer ring, and of 0 to N interior or inner rings (holes).

You can calculate outline lengths of these rings too.

// Polygon outer ring length, inner ring length and total outline length.
// "Outer 114.35571426165451 + inner 45.76491222541475 = 160.12062648706927"
final outerLength = polygon.exterior?.length2D();
final innerLength = polygon.interior.first.length2D();
final totalLength = polygon.length2D();
print('Outer $outerLength + inner $innerLength = $totalLength');

Naturally the length2D method can be applied to other geometry types too, like line strings (polylines). There’s also a method called length3D that calculates lengths in 3D coordinates if a geometry just contain Z or elevation values.

Polygon area

Calculating area for polygons is supported too.

// Polygon outer ring area, inner ring area and total outline area.
// Prints: "Outer 775.0 - inner 100.0 = 675.0"
final outerArea = polygon.exterior?.signedArea2D().abs();
final innerArea = polygon.interior.first.signedArea2D().abs();
final totalArea = polygon.area2D();
print('Outer $outerArea - inner $innerArea = $totalArea');

Polygon data structure



Our sample polygon in all previous sample was defined earlier.

// A polygon geometry (with an exterior ring and one interior ring as a hole).
final polygon = Polygon.build([
[35.0, 10.0, 45.0, 45.0, 15.0, 40.0, 10.0, 20.0, 35.0, 10.0],
[20.0, 30.0, 35.0, 35.0, 30.0, 20.0, 20.0, 30.0],
]);

There are multiple constructors available on the Polygon class. The build factory is defined in the library code:

/// Builds a polygon geometry from one exterior and 0 to N interior [rings].
///
/// Use [type] to specify the type of coordinates, by default `Coords.xy` is
/// expected.
///
/// An optional [bounds] can used set a minimum bounding box for a geometry.
///
/// Each ring in the polygon is represented by an `Iterable<double>` array.
/// Such arrays contain coordinate values as a flat structure. For example for
/// `Coords.xyz` the first three coordinate values are x, y and z of the first
/// position, the next three coordinate values are x, y and z of the second
/// position, and so on.
///
/// An empty polygon has no rings.
///
/// For "normal" polygons the [rings] list must be non-empty. The first
/// element is the exterior ring, and any other rings are interior rings (or
/// holes). All rings must be closed linear rings. As specified by GeoJSON,
/// they should "follow the right-hand rule with respect to the area it
/// bounds, i.e., exterior rings are counterclockwise, and holes are
/// clockwise".
factory Polygon.build(
Iterable<Iterable<double>> rings, {
Coords type = Coords.xy,
Box? bounds,
}) =>
Polygon(
rings
.map(
(ring) => PositionSeries.view(
ring is List<double> ? ring : toFloatNNList(ring),
type: type,
),
)
.toList(growable: false),
bounds: bounds,
);

That’s a lot of definition… But the key idea from this is that each ring takes Iterable<double> with a list of coordinate values as input and is transformed to a PositionSeries object when constructing a polygon.

Position series manipulation

The PositionSeries class is introduced in the coordinates chapter.

You could create exactly the same polygon as used already also using code below.

// Polygon linear rings each an `PositionSeries` instance constructed by
// `positions()` method.
final exteriorRing =
[35.0, 10.0, 45.0, 45.0, 15.0, 40.0, 10.0, 20.0, 35.0, 10.0].positions();
final interiorRing =
[20.0, 30.0, 35.0, 35.0, 30.0, 20.0, 20.0, 30.0].positions();
// Polygon data as `Iterable<PositionSeries>`.
final polygonData = [exteriorRing, interiorRing];
// A polygon geometry (with an exterior ring and one interior ring as a hole).
final polygon = Polygon(polygonData);

It’s possible to modify position series objects before constructing actual polygon geometry objects.

// `PositionSeries` objects can be modified and used to construct new polygons
final exteriorRingEnlargenedBy10percent = exteriorRing * 1.1;
final interiorRingPositionsChanged = interiorRing.rangeReplaced(1, 3, [
[35.5, 35.5].xy,
[30.5, 20.5].xy,
]);
final modifiedPolygon = Polygon(
[exteriorRingEnlargenedBy10percent, interiorRingPositionsChanged],
);

Other manipulation method shown by definitions.

/// Returns a position series with all positions in reversed order compared to
/// this.
PositionSeries reversed();
/// Returns a subseries with positions from [start] (inclusive) to [end]
/// (exclusive).
PositionSeries range(int start, [int? end]);
/// Returns a position series with positions from [start] (inclusive) to [end]
/// (exclusive) removed.
PositionSeries rangeRemoved(int start, [int? end]);
/// Returns a position series with positions from [start] (inclusive) to [end]
/// (exclusive) replaced with [replacements].
PositionSeries rangeReplaced(
int start,
int end,
Iterable<Position> replacements,
);
/// Returns a position series with [iterable] of positions inserted at [index]
/// of this series.
PositionSeries inserted(
int index,
Iterable<Position> iterable,
);
/// Returns a position series with [iterable] of positions added to positions
/// of this series.
PositionSeries added(Iterable<Position> iterable) => PositionSeries.from(
positions.followedBy(iterable),
type: coordType,
);
/// Returns a position series with all positions of this series sorted to the
/// order specified by [compare].
PositionSeries sorted(int Function(Position a, Position b) compare) =>
PositionSeries.from(
positions.toList(growable: false)..sort(compare),
type: coordType,
);
/// Returns a position series with all positions of this series that satisfy
/// the predicate [test].
///
/// The test predicate defined by
/// `bool Function(int count, int index, Position element)` has arguments
/// `count` (the count of all positions in this series), `index` (the current
/// index of element tested) and `element` (the current element tested).
PositionSeries filtered(
bool Function(int count, int index, Position element) test,
);

PositionSeries objects contain 0 to N Position objects.

You can access position coordinate values easily.

// Create a `PositionSeries` object from (x,y) positions.
final exteriorRing =
[35.0, 10.0, 45.0, 45.0, 15.0, 40.0, 10.0, 20.0, 35.0, 10.0].positions();
// Accessing coordinate value data in PositionSeries object.
print('Position count: ${exteriorRing.positionCount}'); // 5
print('Value count: ${exteriorRing.valueCount}'); // 10
print('Is closed: ${exteriorRing.isClosed}'); // true
print('Is 3D: ${exteriorRing.is3D}'); // false
print('Is measured: ${exteriorRing.isMeasured}'); // false
print('Coordinate dimension: ${exteriorRing.coordinateDimension}'); // 2
print('Spatial dimension: ${exteriorRing.spatialDimension}'); // 2
print('Coordinate type: ${exteriorRing.coordType}'); // Coords.xy
print('First position: ${exteriorRing.firstOrNull}'); // 35.0,10.0
print('Last position: ${exteriorRing.lastOrNull}'); // 35.0,10.0
print('X coordinate at position 1: ${exteriorRing.x(1)}'); // 45.0
print('Y coordinate at position 3: ${exteriorRing.y(3)}'); // 20.0
// Looping positions by accessing coordinate values (best to use this option
// when a position series is constructed from a double coordinate value array)
for(int i = 0, len = exteriorRing.positionCount; i < len; i++) {
print('X: ${exteriorRing.x(i)} Y: ${exteriorRing.y(i)} (at $i)');
}
// Looping positions by accessing `Position` objects (best to use this option
// when a position series is constructed from `Position` instances)
for(final pos in exteriorRing.positions) {
print('X: ${pos.x} Y: ${pos.y}');
}

Position manipulation

Position objects can also be manipulated in cartesian coordinate system using operators and functions available.

// a position containing x, y and z
final pos = [708221.0, 5707225.0, 45.0].xyz;
// multiplication operator - prints "708.221,5707.225,0.045" (values in km)
// (the operand is a factor value applied to all coordinate values)
print(pos * 0.001);
// negate operator - prints "-708221.0,-5707225.0,-45.0"
print(-pos);
// following operators expect an operand to be another position object
// add operator - prints "708231.0,5707245.0,50.0"
print(pos + [10.0, 20.0, 5.0].xyz);
// subtraction operator - prints "708211.0,5707205.0,40.0"
print(pos - [10.0, 20.0, 5.0].xyz);
// division operator - prints "708.221,5707.225,45.0" (x and y values in km)
print(pos / [1000.0, 1000.0, 1.0].xyz);
// modulo operator - prints "221.0,225.0,45.0"
print(pos % [1000.0, 1000.0, 1000.0].xyz);
// there is support also for basic calculations in cartesian coordinates
// other point 1000.0 meters to the direction of 45° (north-east)
final other = pos.destinationPoint2D(distance: 1000.0, bearing: 45.0);
// distance between points - prints "1000.0"
print(pos.distanceTo2D(other).toStringAsFixed(1));
// bearing from point to another - prints "45.0"
print(pos.bearingTo2D(other).toStringAsFixed(1));
// midpoint between two points - prints "708574.6,5707578.6"
print(pos.midPointTo(other).toText(decimals: 1));
// intermediate point between two point (fraction range: 0.0 to 1.0)
// prints "708397.8,5707401.8"
print(pos.intermediatePointTo(other, fraction: 0.25).toText(decimals: 1));

Other options to apply coordinate transforms on position objects are to use transform (with a custom transform as a parameter) or project (geospatial projections, discussed in the separate chapter).

Calculations along the Earth surface

Cartesian geometry used in the previous section is not enough when measuring distances between geographic positions located far apart.

The geobase package provides geodesy functions that are based on calculations on a spherical earth model (with errors up to 0.3% compared to an ellipsoidal earth model). Distance, bearing, destination point and midpoint are provided both for great circle paths and rhumb lines. Intermediate points, intersections and areas are available for great circle paths only.

There’s a separate chapter about these calculations.