static getDelaunayTriangulation()

in src/core/MathUtils.js [110:237]
112 lines of code
18 McCabe index (conditional complexity)

  static getDelaunayTriangulation(vertices) {
    if (!vertices || vertices.length < 3) {
      throw new Error(
        `Cannot get delaunay triangulation for points ${vertices}. Input must contain at least three points.`
      );
    }

    let minX = Number.POSITIVE_INFINITY;
    let minY = Number.POSITIVE_INFINITY;
    let maxX = Number.NEGATIVE_INFINITY;
    let maxY = Number.NEGATIVE_INFINITY;

    vertices.forEach(v => {
      minX = v[0] < minX ? v[0] : minX;
      minY = v[1] < minY ? v[1] : minY;
      maxX = v[0] > maxX ? v[0] : maxX;
      maxY = v[1] > maxY ? v[1] : maxY;
    });

    const dX = maxX - minX;
    const dY = maxY - minY;
    const midX = (minX + maxX) / 2;
    const midY = (minY + maxY) / 2;
    const dMax = dX > dY ? dX : dY;

    const superIndices = [
      vertices.length,
      vertices.length + 1,
      vertices.length + 2,
    ];

    const vertsWithSuper = [
      ...vertices,
      [midX - 20 * dMax, midY - dMax],
      [midX, midY + 20 * dMax],
      [midX + 20 * dMax, midY - dMax],
    ];

    const superSortedIndices = MathUtils.sortPointsCCW(
      superIndices,
      vertsWithSuper
    );

    const superTriangle = {
      indices: superSortedIndices,
      edges: [
        [superSortedIndices[0], superSortedIndices[1]],
        [superSortedIndices[1], superSortedIndices[2]],
        [superSortedIndices[2], superSortedIndices[0]],
      ],
    };

    const triangles = [superTriangle];

    vertsWithSuper.forEach((newVert, newIndex) => {
      const invalidTriangles = [];
      triangles.forEach(triangle => {
        if (
          MathUtils.isPointInCircumCircle(
            vertsWithSuper[triangle.indices[0]],
            vertsWithSuper[triangle.indices[1]],
            vertsWithSuper[triangle.indices[2]],
            newVert
          )
        ) {
          invalidTriangles.push(triangle);
        }
      });

      const boundingPoly = [];
      invalidTriangles.forEach(triangle => {
        triangle.edges.forEach(edge => {
          let count = 0;
          invalidTriangles.forEach(otherTriangle => {
            if (triangle !== otherTriangle) {
              otherTriangle.edges.forEach(otherEdge => {
                if (
                  (edge[0] === otherEdge[0] && edge[1] === otherEdge[1]) ||
                  (edge[1] === otherEdge[0] && edge[0] === otherEdge[1])
                ) {
                  count += 1;
                }
              });
            }
          });
          if (count === 0) boundingPoly.push(edge);
        });
      });

      invalidTriangles.forEach(triangle => {
        triangles.splice(triangles.indexOf(triangle), 1);
      });

      boundingPoly.forEach(edge => {
        const sortedIndices = MathUtils.sortPointsCCW(
          [edge[0], edge[1], newIndex],
          vertsWithSuper
        );

        triangles.push({
          indices: sortedIndices,
          edges: [
            [sortedIndices[0], sortedIndices[1]],
            [sortedIndices[1], sortedIndices[2]],
            [sortedIndices[2], sortedIndices[0]],
          ],
        });
      });
    });

    const trianglesToRemove = [];
    triangles.forEach(triangle => {
      triangle.indices.forEach(index => {
        if (superIndices.includes(index)) {
          trianglesToRemove.push(triangle);
        }
      });
    });

    trianglesToRemove.forEach(triangle => {
      const index = triangles.indexOf(triangle);
      if (index !== -1) {
        triangles.splice(index, 1);
      }
    });

    return triangles.map(triangle => triangle.indices);
  }