harrystevens/geometric

A JavaScript library for doing geometry.

Geometric.js

A JavaScript library for doing geometry.

Installation

Web browser

In vanilla, a geometric global is exported. You can use the latest version from unpkg.

<script src="https://unpkg.com/[email protected]/build/geometric.js"></script>
<script src="https://unpkg.com/[email protected]/build/geometric.min.js"></script>

If you'd rather host it yourself, download the latest release from the build directory.

npm

npm i geometric -S

const geometric = require("geometric");

API

Geometric.js uses the geometric primitives points, lines, and polygons.

• Points are represented as arrays of two numbers, such as [0, 0].
• Lines are represented as arrays of two points, such as [[0, 0], [1, 0]]. Because they have endpoints, these are technically line segments, but Geometric.js refers to them as lines for simplicity's sake.
• Polygons are represented as arrays of vertices, each of which is a point, such as [[0, 0], [1, 0], [1, 1], [0, 1]]. Polygons can be closed – the first and last vertex are the same – or open.
• There are also functions to calculate relationships between these primitives.

You will also encounter angles, areas, distances, and lengths.

• Angles are represented as numbers, measured in degrees. Geometric.js also provides functions to convert angles from degrees to radians or vice versa.
• Areas, distances, and lengths are represented as numbers, measured in pixels.

---

Points

# geometric.pointRotate(point, angle[, origin]) · Source, Example

Returns the coordinates resulting from rotating a point about an origin by an angle in degrees. If origin is not specified, the origin defaults to [0, 0].

# geometric.pointTranslate(point, angle, distance) · Source, Example

Returns the coordinates resulting from translating a point by an angle in degrees and a distance.

---

Lines

# geometric.lineAngle(line) · Source, Example

Returns the angle of a line, in degrees, with respect to the horizontal axis.

# geometric.lineInterpolate(line[, clamp]) · Source, Example

Returns an interpolator function given a line [a, b]. The returned interpolator function takes a single argument t, where t is a number in [0, 1]; a value of 0 returns a, while a value of 1 returns b. Intermediate values interpolate from a to b along the line segment.

By default, the interpolator will return points outside of the line segment if t is less than 0 or greater than 1. You can pass an optional boolean indicating whether to clamp the returned point to inside of the line segment, even if t is greater than 1 or less than 0.

# geometric.lineLength(line) · Source, Example

Returns the length of a line.

# geometric.lineMidpoint(line) · Source, Example

Returns the midpoint of a line.

# geometric.lineRotate(line, angle[, origin]) · Source, Example

Returns the coordinates resulting from rotating a line about an origin by an angle in degrees. If origin is not specified, the origin defaults to the midpoint of the line.

# geometric.lineTranslate(line, angle, distance) · Source, Example

Returns the coordinates resulting from translating a line by an angle in degrees and a distance.

---

Polygons

# geometric.polygonArea(polygon[, signed]) · Source, Example

Returns the area of a polygon. You can pass a boolean indicating whether the returned area is signed, which defaults to false.

# geometric.polygonBounds(polygon) · Source, Example

Returns the bounds of a polygon, ignoring points with invalid values (null, undefined, NaN, Infinity). The returned bounds are represented as an array of two points, where the first point is the top-left corner and the second point is the bottom-right corner. For example:

const rectangle = [[0, 0], [0, 1], [1, 1], [1, 0]];
const bounds = geometric.polygonBounds(rectangle); // [[0, 0], [1, 1]]

Returns null if the polygon has fewer than three points.

# geometric.polygonCentroid(polygon) · Source, Example

Returns the weighted centroid of a polygon. Not to be confused with a mean center.

# geometric.polygonHull(points) · Source, Example

Returns the convex hull, represented as a polygon, for an array of points. Returns null if the input array has fewer than three points. Uses Andrew’s monotone chain algorithm.

# geometric.polygonInterpolate(polygon]) · Source, Example

Returns an interpolator function given a polygon of vertices [a, ..., n]. The returned interpolator function takes a single argument t, where t is a number in [0, 1]; a value of 0 returns a, while a value of 1 returns n. Intermediate values interpolate from a to n along the polygon's perimeter.

# geometric.polygonLength(polygon) · Source, Example

Returns the length of a polygon's perimeter.

# geometric.polygonMean(polygon) · Source, Example

Returns the arithmetic mean of the vertices of a polygon. Keeps duplicate vertices, resulting in different values for open and closed polygons. Not to be confused with a centroid.

# geometric.polygonRandom([sides[, area[, centroid]]]) · Source, Example

Returns the vertices of a random convex polygon of the specified number of sides, area, and centroid coordinates. If sides is not specified, defaults to 3. If area is not specified, defaults to 100. If centroid is not specified, defaults to [0, 0]. The returned polygon's winding order will be counter-clockwise. Based on an algorithm by Pavel Valtr and an implementation by Maneesh Agrawala.

# geometric.polygonReflectX(polygon[, reflectFactor]) · Source, Example

Reflects a polygon over its vertical midline. Pass an optional reflectFactor between 0 and 1, where 1 indicates a full reflection, 0 leaves the polygon unchanged, and 0.5 collapses the polygon on its vertical midline.

# geometric.polygonReflectY(polygon[, reflectFactor]) · Source, Example

Reflects a polygon over its horizontal midline. Pass an optional reflectFactor between 0 and 1, where 1 indicates a full reflection, 0 leaves the polygon unchanged, and 0.5 collapses the polygon on its horizontal midline.

# geometric.polygonRegular([sides[, area[, center]]]) · Source, Example

Returns the vertices of a regular polygon of the specified number of sides, area, and center coordinates. If sides is not specified, defaults to 3. If area is not specified, defaults to 100. If center is not specified, defaults to [0, 0]. The returned polygon's winding order will be counter-clockwise.

# geometric.polygonRotate(polygon, angle[, origin]) · Source, Example

Returns the vertices resulting from rotating a polygon about an origin by an angle in degrees. If origin is not specified, the origin defaults to [0, 0].

# geometric.polygonScale(polygon, scaleFactor[, origin]) · Source, Example

Returns the vertices resulting from scaling a polygon by a scaleFactor (where 1 is the polygon's current size) from an origin point. If origin is not specified, the origin defaults to the polygon's centroid.

The returned polygon's area is equal to the input polygon's area multiplied by the square of the scaleFactor. To scale the polygon's area by the scaleFactor itself, see geometric.polygonScaleArea.

# geometric.polygonScaleArea(polygon, scaleFactor[, origin]) · Source, Example

Returns the vertices resulting from scaling a polygon by a scaleFactor (where 1 is the polygon's current size) from an origin point. If origin is not specified, the origin defaults to the polygon's centroid.

The returned polygon's area is equal to the input polygon's area multiplied by the scaleFactor. To scale the polygon's area by the square of the scaleFactor, see geometric.polygonScale.

# geometric.polygonScaleX(polygon, scaleFactor[, origin]) · Source, Example

Returns the vertices resulting from scaling the horizontal coordinates of a polygon by a scaleFactor (where 1 is the polygon's current size) from an origin point. The vertical coordinates remain unchanged. If origin is not specified, the origin defaults to the polygon's centroid.

The returned polygon's area is equal to the input polygon's area multiplied by the scaleFactor.

# geometric.polygonScaleY(polygon, scaleFactor[, origin]) · Source, Example

Returns the vertices resulting from scaling the vertical coordinates of a polygon by a scaleFactor (where 1 is the polygon's current size) from an origin point. The horizontal coordinates remain unchanged. If origin is not specified, the origin defaults to the polygon's centroid.

The returned polygon's area is equal to the input polygon's area multiplied by the scaleFactor.

# geometric.polygonTranslate(polygon, angle, distance) · Source, Example

Returns the vertices resulting from translating a polygon by an angle in degrees and a distance.

# geometric.polygonWind(polygon[, order]) · Source, Example

Returns a polygon in the specified winding order. If an order string is passed as either "cw" or "clockwise", returns a polygon with a clockwise winding order. Otherwise, returns a polygon with a counter-clockwise winding order. Returns null if the polygon has fewer than three points.

On computer screens where the top-left corner is at [0, 0], a polygon with a negative signed area has a counter-clockwise winding order.

---

Relationships

# geometric.lineIntersectsLine(lineA, lineB) · Source, Example

Returns a boolean representing whether lineA intersects lineB.

# geometric.lineIntersectsPolygon(line, polygon) · Source, Example

Returns a boolean representing whether a line intersects a polygon.

# geometric.pointInPolygon(point, polygon) · Source, Example

Returns a boolean representing whether a point is inside of a polygon. Uses ray casting.

# geometric.pointOnPolygon(point, polygon[, epsilon]) · Source, Example

Returns a boolean representing whether a point is located on one of the edges of a polygon. An optional epsilon number, such as 1e-6, can be passed to reduce the precision with which the relationship is measured.

# geometric.pointOnLine(point, line[, epsilon]) · Source, Example

Returns a boolean representing whether a point is collinear with a line and is also located on the line segment. An optional epsilon number, such as 1e-6, can be passed to reduce the precision with which the relationship is measured. See also pointWithLine.

# geometric.pointWithLine(point, line[, epsilon]) · Source, Example

Returns a boolean representing whether a point is collinear with a line. An optional epsilon number, such as 1e-6, can be passed to reduce the precision with which the relationship is measured. See also pointOnLine.

# geometric.pointLeftofLine(point, line) · Source, Example

Returns a boolean representing whether a point is to the left of a line.

# geometric.pointRightofLine(point, line) · Source, Example

Returns a boolean representing whether a point is to the right of a line.

# geometric.polygonInPolygon(polygonA, polygonB) · Source, Example

Returns a boolean representing whether polygonA is contained by polygonB.

# geometric.polygonIntersectsPolygon(polygonA, polygonB) · Source, Example

Returns a boolean representing whether polygonA intersects but is not contained by polygonB.

---

Angles

# geometric.angleReflect(incidence, surface) · Source, Example

Returns the angle of reflection given a starting angle, also known as the angle of incidence, and the angle of the surface off of which it is reflected.

# geometric.angleToDegrees(angle) · Source

Returns the result of converting an angle in radians to the same angle in degrees.

# geometric.angleToRadians(angle) · Source

Returns the result of converting an angle in degrees to the same angle in radians.

geometric's Issues

Zones and intersection

Good afternoon!

I need to draw three polygons - outer and two inner ones. They can be edited.

All three polygons form zones. I marked them - 1, 2, 3.

I need to be able to switch between zones and look for the intersection of each of the zones with a moving point, for example, the mouse cursor.

Can you please tell me if your library will help me?

Support for parsing geometries from WKT strings

We communicate geometric shapes a lot via WKT strings. Does this project consider parsing from such a string within scope? For example:

const polygon = geometric.wkt.parse("POLYGON (( 0.0 0.0, 0.0 10.0, 10.0 10.0, 10.0 0.0, 0.0 0.0 ))");

If so, we might be able to contribute this.

Or alternatively, does geometric envision other ways to instantiate a shape, perhaps from a geojson, without manually recognizing the geometry type and juggling coordinates?

Make polygonScale arithmetically correct

The function should return a polygon whose area is the scaleFactor times the input polygon's area.

Add polygonInterpolate

Like lineInterpolate but for a series of line segments.

Add polygonWind

Integrate typescript types

Currently, typescript types are given and maintained through DefinitelyTyped (code, npm).

I saw some missing types like the new epsilons.
Would you consider adding the types to the repo and maintaining them here to avoid unsynchronised types?

'isClosed' does not detect closed polygons

In version 2.2.1 'isClosed' has a simple implementation: return polygon[0] === polygon[polygon.length - 1]; which does not work as comparing arrays with '===' gives always 'false', ([10, 0] === [10, 0] returns 'false') therefore this implementation cannot really detect closed polygons.

Something like

function isClosed(polygon) {
    let last = polygon.length - 1;
    for (let i = 0; i < polygon[0].length; i++) {
      if (polygon[0][i] !== polygon[last][i]) {
        return false;
      }
    }
    return true;
}

worked for me (I am not fluent in Javascript, so there might be a more elegant implementation).

Tested in Safari Version 13.1 (15609.1.20.111.8).

Simplify and speed up lineInterpolate

Feature Request: Add polygonScale for scaleX and scaleY independently

Great library.

I think it would be useful to be able to calculate vertices based on axis independent scales (X or Y), as opposed to just a general scale (X and Y).

Perhaps something to the tune of:

export function polygonScaleX(polygon, scaleX, origin){
   ...etc
}

export function polygonScaleY(polygon, scaleY, origin){
   ...etc
}

polygonIntersectsPolygon() returns false if overlapping rectangles share two edges

var a = [
  [562.6875, 304.4375],
  [601.09375, 304.4375],
  [601.09375, 322.9375],
  [562.6875, 322.9375]
];

var b = [
  [562.6875, 298.4375],
  [601.09375, 298.4375],
  [601.09375, 316.9375],
  [562.6875, 316.9375],
];

geometric.polygonIntersectsPolygon(a, b); // false but should be true

lineIntersectsLine is not commutative

Hi,

I noticed this:

const line1 = [
  [50.054358, 8.693184],
  [50.055604, 8.685873]
];
const line2 = [
  [50.054228, 8.69338],
  [50.054358, 8.693184]
];
lineIntersectsLine(line1, line2);
// false
lineIntersectsLine(line2, line1);
// true

Note that the start of line1 and the end of line2 are identical.

What do you think is the expected result? Since the lines share a point, they arguably do intersect. However my use case is around multiple lines fanning out from a single point and I don't want to count those as intersecting.

I'd suggest adding a parameter excludeEndpoints that determines wether sharing a start/end-point should count as intersecting. What do you think?

I can probably open a PR if we decide on something.

Kind regards,
yeldiRium

multipolygons

Do you plan to support multi-polygons?

polygonInPolygon() returns true even if segments of polygonA fall outside polygonB

See: https://observablehq.com/d/ad24b20348adb412

Add lineRotate and lineTranslate

Should just be:

function lineRotate(line, angle, origin){
  return line.map(point => pointRotate(point, angle, origin));
}

function lineTranslate(line, angle, distance){
  return line.map(point => pointTranslate(point, angle, distance));
}

Feature Request: Avoid Rounding Errors

I'm using 'geometric' in a CAD project. I lately discovered false negatives from the function pointWithLine.

I copied the function and added an epsilon test. This resolved the issue.

export function pointWithLineWithEpsilon(point: Point, line: Line, epsilon: number = 1e-10) {
    const x = cross(point, line[0], line[1]);
    return Math.abs(x) < epsilon;
}

My suggeston would be to add an optional epsilon parameter to that function, as well as functions with similar cases.

Make lineInterpolate handle values outside of [0; 1]

In the library, lines are actually line segments.
Current implementation of lineInterpolate gives an interpolator that returns points outside of the line segment if values passed are outside the interval [0;1].

export function lineInterpolate(line){
  return t => t === 0 ? line[0] : t === 1 ? line[1] : pointTranslate(line[0], lineAngle(line), lineLength(line) * t);
}

The following change would allow passing any number value and get the appropriate point on the line segment:

export function lineInterpolate(line){
  return t => t <= 0 ? line[0] : t >= 1 ? line[1] : pointTranslate(line[0], lineAngle(line), lineLength(line) * t);
}

Add polygonRandom

polygonInPolygon -> Accept if PolygonA touches segment of PolygonB

Currently I'm trying to use your library to detect if polygons are contained inside another polygon.

But for my case it's also fine if on segments (lines) of the "inside" polygon touches one or more of the "outer" polygon segments (point/line on line case). How can I handle this case with your library? Is there any possibility to do this without breaking the "inside" polygon into single lines and check if they are all inside or on the "outer" polygon segments?

Best regards,
Michael

Support for other GeoJSON shapes

Hi, would it be possible to add support for other GeoJSON shapes, especially polygon with holes? Your library is well structured for tree-shaking, so I'm considering to use it in my https://github.com/zakjan/leaflet-lasso.

Typescript support?

Hi, great work!
It would be awesome if the lib came with typescript support.
Either by manually declaring typescript defs or even better, rewriting the entire project to TS.

What do you think?
I can lend a hand to help.

new fun

i think u can add distance between points and lines, as well as the vertical foot function between points and lines，这个也很有用

Better boolean operations for V3

The current relationship methods return only booleans, i.e. if the relationship exists. Better would be to return where the relationship exists, or false if it does not exist.

• lineIntersectsLine: https://observablehq.com/d/6222f0815840b5e4
• lineIntersectsPolygon: https://observablehq.com/d/efb47e989a0bbc9c

The polygon relationship methods will likely be somewhat time consuming to implement. The most modern algorithms for performing boolean operations on polygons can be found here: http://www.cs.ucr.edu/~vbz/cs230papers/martinez_boolean.pdf

These will likely not be compatible with current methods, so it may be necessary to bump major versions.

polygonInPolygon return false with same polygon or polygon with same point

var poly1 = [[1,2], [215,1], [215,215]];
var poly2 = [[1,2], [215,1], [215,215]];
let res = geometric.polygonInPolygon(poly1, poly2) // false

// another situation
var poly1 = [[1,2], [215,1], [214,214]];
var poly2 = [[1,2], [215,1], [215,215]];
let res = geometric.polygonInPolygon(poly1, poly2) // false

Add polygonReflectX and polygonReflectY

Add lineInterpolate?

Like d3.geoInterpolate but for planar geometry. Demo: https://observablehq.com/d/747dbe82f8169724.

Missing "Super" Beginner Documentation : How to use this lib ?

Hello, I am not very used to javascript , can anyone point me out how to actually draw lines and polygons that would be visible to me on screen ? I mean to say how this lib would interact with the html elements ? , I don't know how to do it , and there will always be someone like me who want to use this lib but don't know how to set it up. Request the maintainers of the lib to add some super beginner steps so the lines and polygons object created by this "geometric" lib will show up on the screen.

Thanks.

Ongoing development?

Hi, I'm trying to find a good geometry library to use on top of p5.js for drawing.

I see this library doesn't do anything with curves, paths, or vectors. Or altering polygons, like clipping, union, etc.

Do you plan to add more features at any time? Or do you know of a more advanced geometry library please? This is the only one I can find :(

Make polygonClose and polygonClosed first-order functions

Polygon Offset？

Bug in polygonIntersectsPolygon()

Package version: 2.2.8

Hi, it seems you have a bug in polygonIntersectsPolygon() . I have tested this with these arguments:
Polygon A)

[
  [3, 3],
  [3, 4],
  [4, 4],
  [4, 3]
]

Polygon B)

[
  [1, 1],
  [1, 4],
  [2, 4],
  [2, 2],
  [5, 2],
  [5, 4],
  [6, 4],
  [6, 1]
]

The first polygon is a simple rectangle. The second is an upside down U. The rectangle is in the opening of U but it never intersects the polygon.

The method incorrectly returns true.

cc @HarryStevens

'polygonIntersectsPolygon' fails detecting intersecting polygons in special cases

In version 2.2.1, using the following two polygons:

[[180, 140], [180, 205]] and

[[160, 180], [170, 181.72], [180, 187.64], [185, 193.41]]

'polygonIntersectsPolygon' gives false, though these two polygons clearly do intersect. The problem is in the 'lineIntersectsLine' function, where replacing the original

return 0 < lambda && lambda < 1 && 0 < gamma && gamma < 1;

line by

return 0 <= lambda && lambda <= 1 && 0 <= gamma && gamma <= 1;

allows detecting 'endpoint intersections'.

With this modification the 'polygonIntersectsPolygon' function gives a correct result.

Tested in Safari Version 13.1 (15609.1.20.111.8).