@mathigon/euclid - npm Package Compare versions

Comparing version 1.1.19 to 1.1.20

dist/boolean.d.ts

 import { Point } from './point';
 type MultiPolygon = Point[][];
-export declare const union: (p1: MultiPolygon, p2: MultiPolygon) => Point[][];
-export declare const intersect: (p1: MultiPolygon, p2: MultiPolygon) => Point[][];
-export declare const difference: (p1: MultiPolygon, p2: MultiPolygon) => Point[][];
-export declare const xor: (p1: MultiPolygon, p2: MultiPolygon) => Point[][];
+export declare const union: (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => Point[][];
+export declare const intersect: (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => Point[][];
+export declare const difference: (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => Point[][];
+export declare const xor: (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => Point[][];
 export {};

dist/polygon.d.ts

@@ -24,6 +24,8 @@ import { Circle } from './circle';
     /** Cut this polygon along a line, and return multiple parts. */
-    cut(line: Line): Polygon[];
+    cut(line: Line, precision?: number): Polygon[];
     /** Checks if two polygons p1 and p2 collide. */
     static collision(p1: Polygon, p2: Polygon): boolean;
-    static union(...polygons: Polygon[]): Polygon[];
+    static union(polygons: Polygon[], precision?: number): Polygon[];
+    static intersection(polygons: Polygon[], precision?: number): Polygon[];
+    static difference(p1: Polygon, p2: Polygon, precision?: number): Polygon[];
     /** Creates a regular polygon. */
@@ -30,0 +32,0 @@ static regular(n: number, radius?: number): Polygon;

package.json

 {
   "name": "@mathigon/euclid",
-  "version": "1.1.19",
+  "version": "1.1.20",
   "license": "MIT",
@@ -5,0 +5,0 @@ "homepage": "https://mathigon.io/euclid",

src/boolean.ts

@@ -20,3 +20,4 @@ // =============================================================================
 
-const PRECISION = 0.001;
+const DEFAULT_PRECISION = 0.000001;
+let PRECISION = DEFAULT_PRECISION;
 
@@ -50,4 +51,4 @@ function pointAboveOrOnLine(pt: Point, left: Point, right: Point) {
   // returns -1 if p1 is smaller, 1 if p2 is smaller, 0 if equal
-  if (nearlyEquals(p1.x, p2.x)) {
-    return nearlyEquals(p1.y, p2.y) ? 0 : (p1.y < p2.y ? -1 : 1);
+  if (nearlyEquals(p1.x, p2.x, PRECISION)) {
+    return nearlyEquals(p1.y, p2.y, PRECISION) ? 0 : (p1.y < p2.y ? -1 : 1);
   }
@@ -65,7 +66,8 @@ return p1.x < p2.x ? -1 : 1;
  */
-function getOffset(A: number): -2|-1|0|1|2 {
-  if (A <= -PRECISION) return -2;
-  if (A < PRECISION) return -1;
-  if (A - 1 <= -PRECISION) return 0;
-  if (A - 1 < PRECISION) return 1;
+function getOffset(A: number, length: number): -2|-1|0|1|2 {
+  const precision = PRECISION / length;
+  if (A <= -precision) return -2;
+  if (A < precision) return -1;
+  if (A - 1 <= -precision) return 0;
+  if (A - 1 < precision) return 1;
   return 2;
@@ -81,3 +83,3 @@ }
   const axb = adx * bdy - ady * bdx;
-  if (nearlyEquals(axb, 0)) return false;  // lines are coincident
+  if (nearlyEquals(axb, 0, PRECISION)) return false;  // lines are coincident
 
@@ -88,5 +90,7 @@ const dx = a0.x - b0.x;
   const B = (adx * dy - ady * dx) / axb;
+  const aLength = Math.hypot(adx, ady);
+  const bLength = Math.hypot(bdx, bdy);
 
   const pt = new Point(a0.x + A * adx, a0.y + A * ady);
-  return {alongA: getOffset(A), alongB: getOffset(B), pt};
+  return {alongA: getOffset(A, aLength), alongB: getOffset(B, bLength), pt};
 }
@@ -201,3 +205,3 @@
   // If the non-selected points are the same too then the segments are equal.
-  if (Point.equals(p12, p22)) return 0;
+  if (Point.equals(p12, p22, PRECISION)) return 0;
 
@@ -254,4 +258,4 @@ // If one is a start and the other isn't favor the one that isn't the start.
 
-  if (!Point.colinear(a1, b1, b2)) return pointAboveOrOnLine(a1, b1, b2) ? 1 : -1;
-  if (!Point.colinear(a2, b1, b2)) return pointAboveOrOnLine(a2, b1, b2) ? 1 : -1;
+  if (!Point.colinear(a1, b1, b2, PRECISION)) return pointAboveOrOnLine(a1, b1, b2) ? 1 : -1;
+  if (!Point.colinear(a2, b1, b2, PRECISION)) return pointAboveOrOnLine(a2, b1, b2) ? 1 : -1;
   return 1;
@@ -275,7 +279,7 @@ }
     // on top of each other somehow (aka coincident)
-    if (!Point.colinear(a1, a2, b1)) return false;
-    if (Point.equals(a1, b2) || Point.equals(a2, b1)) return false;
+    if (!Point.colinear(a1, a2, b1, PRECISION)) return false;
+    if (Point.equals(a1, b2, PRECISION) || Point.equals(a2, b1, PRECISION)) return false;
 
-    const a1isb1 = Point.equals(a1, b1);
-    const a2isb2 = Point.equals(a2, b2);
+    const a1isb1 = Point.equals(a1, b1, PRECISION);
+    const a2isb2 = Point.equals(a2, b2, PRECISION);
 
@@ -438,3 +442,3 @@ if (a1isb1 && a2isb2) return ev2;  // Segments are exactly equal
     const pt2 = seg.end;
-    if (Point.equals(pt1, pt2)) return;  // Zero-length segment: maybe PRECISION is too small or too large!
+    if (Point.equals(pt1, pt2, PRECISION)) return;  // Zero-length segment: maybe PRECISION is too small or too large!
 
@@ -462,9 +466,9 @@ // Search for two chains that this segment matches.
       const tail = last(chain);
-      if (Point.equals(head, pt1)) {
+      if (Point.equals(head, pt1, PRECISION)) {
         if (setMatch(i, true, true)) break;
-      } else if (Point.equals(head, pt2)) {
+      } else if (Point.equals(head, pt2, PRECISION)) {
         if (setMatch(i, true, false)) break;
-      } else if (Point.equals(tail, pt1)) {
+      } else if (Point.equals(tail, pt1, PRECISION)) {
         if (setMatch(i, false, true)) break;
-      } else if (Point.equals(tail, pt2)) {
+      } else if (Point.equals(tail, pt2, PRECISION)) {
         if (setMatch(i, false, false)) break;
@@ -494,3 +498,3 @@ }
 
-      if (Point.colinear(grow2, grow, pt)) {
+      if (Point.colinear(grow2, grow, pt, PRECISION)) {
         // Grow isn't needed because it's directly between grow2 and pt.
@@ -501,7 +505,7 @@ addToHead ? chain.shift() : chain.pop();
 
-      if (Point.equals(oppo, pt)) {
+      if (Point.equals(oppo, pt, PRECISION)) {
         // We're closing the loop, so remove chain from chains.
         chains.splice(index, 1);
 
-        if (Point.colinear(oppo2, oppo, grow)) {
+        if (Point.colinear(oppo2, oppo, grow, PRECISION)) {
           // Oppo isn't needed because it's directly between oppo2 and grow.
@@ -535,3 +539,3 @@ addToHead ? chain.pop() : chain.shift();
 
-      if (Point.colinear(tail2, tail, head)) {
+      if (Point.colinear(tail2, tail, head, PRECISION)) {
         // Tail isn't needed because it's directly between tail2 and head
@@ -542,3 +546,3 @@ chain1.pop();
 
-      if (Point.colinear(tail, head, head2)) {
+      if (Point.colinear(tail, head, head2, PRECISION)) {
         // Head isn't needed because it's directly between tail and head2
@@ -630,3 +634,4 @@ chain2.shift();
 
-function operate(poly1: MultiPolygon, poly2: MultiPolygon, selection: number[]) {
+function operate(poly1: MultiPolygon, poly2: MultiPolygon, selection: number[], precision?: number) {
+  if (precision !== undefined) PRECISION = precision;
   const root = new LinkedList<Event>();
@@ -636,4 +641,5 @@ for (const s of segments(poly1)) addSegment(root, copy(s.start, s.end, s), true);
 
-  const results = select(calculate(root, false), selection);
-  return segmentChainer(results);
+  const results = segmentChainer(select(calculate(root, false), selection));
+  PRECISION = DEFAULT_PRECISION;
+  return results;
 }
@@ -652,5 +658,5 @@
 
-export const union = (p1: MultiPolygon, p2: MultiPolygon) => operate(p1, p2, UNION);
-export const intersect = (p1: MultiPolygon, p2: MultiPolygon) => operate(p1, p2, INTERSECT);
-export const difference = (p1: MultiPolygon, p2: MultiPolygon) => operate(p1, p2, DIFFERENCE);
-export const xor = (p1: MultiPolygon, p2: MultiPolygon) => operate(p1, p2, XOR);
+export const union = (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => operate(p1, p2, UNION, precision);
+export const intersect = (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => operate(p1, p2, INTERSECT, precision);
+export const difference = (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => operate(p1, p2, DIFFERENCE, precision);
+export const xor = (p1: MultiPolygon, p2: MultiPolygon, precision?: number) => operate(p1, p2, XOR, precision);

src/polygon.ts

@@ -92,3 +92,3 @@ // =============================================================================
   /** Cut this polygon along a line, and return multiple parts. */
-  cut(line: Line) {
+  cut(line: Line, precision?: number) {
     // This feels a bit hacky... can we find the bounding box of the Polygon?
@@ -101,4 +101,4 @@ const t = this.radius / line.length * 10;
 
-    const side1 = intersect([this.points], [mask]);
-    const side2 = difference([this.points], [mask]);
+    const side1 = intersect([this.points], [mask], precision);
+    const side2 = difference([this.points], [mask], precision);
     return [...side1, ...side2].map(p => new Polygon(...p));
@@ -123,3 +123,3 @@ }
 
-  static union(...polygons: Polygon[]): Polygon[] {
+  static union(polygons: Polygon[], precision?: number): Polygon[] {
     const [first, ...other] = polygons;
@@ -129,6 +129,28 @@ if (!other.length) return [first];
     const p1 = [first.points];
-    const p2 = other.length > 1 ? Polygon.union(...other).map(p => p.points) : [polygons[1].points];
-    return union(p1, p2).map(p => new Polygon(...p));
+    const p2 = other.length > 1 ? Polygon.union(other, precision).map(p => p.points) : [polygons[1].points];
+    return union(p1, p2, precision).map(p => new Polygon(...p));
   }
 
+  static intersection(polygons: Polygon[], precision?: number): Polygon[] {
+    const [first, ...other] = polygons;
+    if (!other.length) return [first];
+
+    let intersection = [first.points];
+
+    for (const poly of other) {
+      const p1 = intersection;
+      const p2 = [poly.points];
+      intersection = intersect(p1, p2, precision);
+      if (!intersection.length) return [];
+    }
+
+    return intersection.map(p => new Polygon(...p));
+  }
+
+  static difference(p1: Polygon, p2: Polygon, precision?: number): Polygon[] {
+    const poly12 = difference([p1.points], [p2.points], precision);
+    const poly21 = difference([p2.points], [p1.points], precision);
+    return poly12.concat(poly21).map(p => new Polygon(...p));
+  }
+
   /** Creates a regular polygon. */
@@ -135,0 +157,0 @@ static regular(n: number, radius = 1) {

test/boolean-test.ts

@@ -8,3 +8,3 @@ // =============================================================================
 import tape from 'tape';
-import {difference, intersect, union, xor} from '../src/boolean';
+import {difference, intersect, Polygon, union, xor} from '../src';
 import {Point} from '../src';
@@ -51,1 +51,14 @@
 });
+
+tape('intersections', (test) => {
+  const hexagon = Polygon.regular(6, 100);
+  const result = Polygon.intersection([hexagon, hexagon]);
+  test.equal(hexagon.area, result[0].area);
+
+  const p1 = new Polygon(new Point(340, 300), new Point(341.95, 210), new Point(360, 250));
+  const p2 = new Polygon(new Point(340, 300), new Point(341.953125, 210), new Point(360, 250));
+  const r2 = Polygon.intersection([p1, p2]);
+  test.equal(r2.length, 1);
+
+  test.end();
+});

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

572272

increased by1.74%

Lines of code

7623

increased by1.15%

No dependency changes