Polygon

Introduction

vtkPolygon represents a 2D n-sided polygon.

The polygons cannot have any internal holes, and cannot self-intersect.
Define the polygon with n-points ordered in the counter-clockwise direction.
Do not repeat the last point.

Methods

extend

Method used to decorate a given object (publicAPI+model) with vtkPolygon characteristics.

Argument	Type	Required	Description
publicAPI		Yes	object on which methods will be bounds (public)
model		Yes	object on which data structure will be bounds (protected)
initialValues	IPolygonInitialValues	No	(default: {})

getPointArray

Get the array of triangles that triangulate the polygon.

newInstance

Method used to create a new instance of vtkPolygon.

Argument	Type	Required	Description
initialValues	IPolygonInitialValues	No	for pre-setting some of its content

setPoints

Set the polygon’s points

Argument	Type	Required	Description
points	Array.	Yes	The polygon’s points.

triangulate

Triangulate this polygon.
The output data must be accessed through getPointArray.
The output data contains points by group of three: each three-group
defines one triangle.

Source

index.d.ts

import { vtkObject } from "../../../interfaces" ;
import { Vector3 } from "../../../types";


export interface IPolygonInitialValues {
	firstPoint?: Vector3,
	pointCount?: number,
	tris?: Vector3[],
}

export interface vtkPolygon extends vtkObject {

	/**
	 * Get the array of triangles that triangulate the polygon.
	 */
	getPointArray(): Vector3[];

	/**
	 * Set the polygon's points
	 * @param {Vector3[]} points The polygon's points.
	 */
	setPoints(points: Vector3[]): void;

	/**
	 * Triangulate this polygon. 
	 * The output data must be accessed through `getPointArray`.
	 * The output data contains points by group of three: each three-group
	 * defines one triangle.
	 */
	triangulate(): void;
}

/**
 * Method used to decorate a given object (publicAPI+model) with vtkPolygon characteristics.
 *
 * @param publicAPI object on which methods will be bounds (public)
 * @param model object on which data structure will be bounds (protected)
 * @param {IPolygonInitialValues} [initialValues] (default: {})
 */
export function extend(publicAPI: object, model: object, initialValues?: IPolygonInitialValues): void;

/**
 * Method used to create a new instance of vtkPolygon.
 * @param {IPolygonInitialValues} [initialValues] for pre-setting some of its content
 */
export function newInstance(initialValues?: IPolygonInitialValues): vtkPolygon;

/**
 * vtkPolygon represents a 2D n-sided polygon.
 * 
 * The polygons cannot have any internal holes, and cannot self-intersect.
 * Define the polygon with n-points ordered in the counter-clockwise direction.
 * Do not repeat the last point.
 */
export declare const vtkPolygon: {
	newInstance: typeof newInstance,
	extend: typeof extend;
};
export default vtkPolygon;

index.js

import macro from 'vtk.js/Sources/macros';
import * as vtkMath from 'vtk.js/Sources/Common/Core/Math';
import vtkLine from 'vtk.js/Sources/Common/DataModel/Line';
import vtkPlane from 'vtk.js/Sources/Common/DataModel/Plane';
import vtkPriorityQueue from 'vtk.js/Sources/Common/Core/PriorityQueue';
import { IntersectionState } from 'vtk.js/Sources/Common/DataModel/Line/Constants';

// ----------------------------------------------------------------------------
// vtkPolygon methods
// ----------------------------------------------------------------------------

const EPSILON = 1e-6;

function vtkPolygon(publicAPI, model) {
  // Set our classname
  model.classHierarchy.push('vtkPolygon');

  function computeNormal() {
    const v1 = [0, 0, 0];
    const v2 = [0, 0, 0];
    model.normal = [0, 0, 0];
    const anchor = [...model.firstPoint.point];

    let point = model.firstPoint;
    for (let i = 0; i < model.pointCount; i++) {
      vtkMath.subtract(point.point, anchor, v1);
      vtkMath.subtract(point.next.point, anchor, v2);

      const n = [0, 0, 0];
      vtkMath.cross(v1, v2, n);
      vtkMath.add(model.normal, n, model.normal);

      point = point.next;
    }

    return vtkMath.normalize(model.normal);
  }

  function computeMeasure(point) {
    const v1 = [0, 0, 0];
    const v2 = [0, 0, 0];
    const v3 = [0, 0, 0];
    const v4 = [0, 0, 0];

    vtkMath.subtract(point.point, point.previous.point, v1);
    vtkMath.subtract(point.next.point, point.point, v2);
    vtkMath.subtract(point.previous.point, point.next.point, v3);
    vtkMath.cross(v1, v2, v4);

    const area = vtkMath.dot(v4, model.normal);

    if (area <= 0) {
      return -1;
    }

    const perimeter = vtkMath.norm(v1) + vtkMath.norm(v2) + vtkMath.norm(v3);

    return (perimeter * perimeter) / area;
  }

  function canRemoveVertex(point) {
    if (model.pointCount <= 3) {
      return true;
    }

    const previous = point.previous;
    const next = point.next;

    const v = [0, 0, 0];
    vtkMath.subtract(next.point, previous.point, v);

    const sN = [0, 0, 0];
    vtkMath.cross(v, model.normal, sN);
    vtkMath.normalize(sN);
    if (vtkMath.norm(sN) === 0) {
      return false;
    }

    let val = vtkPlane.evaluate(sN, previous.point, next.next.point);
    // eslint-disable-next-line no-nested-ternary
    let currentSign = val > EPSILON ? 1 : val < -EPSILON ? -1 : 0;
    let oneNegative = currentSign < 0 ? 1 : 0;

    for (
      let vertex = next.next.next;
      vertex.id !== previous.id;
      vertex = vertex.next
    ) {
      const previousVertex = vertex.previous;
      val = vtkPlane.evaluate(sN, previous.point, vertex.point);
      // eslint-disable-next-line no-nested-ternary
      const sign = val > EPSILON ? 1 : val < -EPSILON ? -1 : 0;

      if (sign !== currentSign) {
        if (!oneNegative) {
          oneNegative = sign <= 0 ? 1 : 0;
        }

        if (
          vtkLine.intersection(
            previous.point,
            next.point,
            vertex.point,
            previousVertex.point,
            [0],
            [0]
          ) === IntersectionState.YES_INTERSECTION
        ) {
          return false;
        }
        currentSign = sign;
      }
    }

    return oneNegative === 1;
  }

  function removePoint(point, queue) {
    model.pointCount -= 1;

    const previous = point.previous;
    const next = point.next;

    model.tris = model.tris.concat(point.point);
    model.tris = model.tris.concat(next.point);
    model.tris = model.tris.concat(previous.point);

    previous.next = next;
    next.previous = previous;

    queue.deleteById(previous.id);
    queue.deleteById(next.id);

    const previousMeasure = computeMeasure(previous);
    if (previousMeasure > 0) {
      queue.push(previousMeasure, previous);
    }

    const nextMeasure = computeMeasure(next);
    if (nextMeasure > 0) {
      queue.push(nextMeasure, next);
    }

    if (point.id === model.firstPoint.id) {
      model.firstPoint = next;
    }
  }

  function earCutTriangulation() {
    computeNormal();

    const vertexQueue = vtkPriorityQueue.newInstance();
    let point = model.firstPoint;
    for (let i = 0; i < model.pointCount; i++) {
      const measure = computeMeasure(point);
      if (measure > 0) {
        vertexQueue.push(measure, point);
      }

      point = point.next;
    }

    while (model.pointCount > 2 && vertexQueue.length() > 0) {
      if (model.pointCount === vertexQueue.length()) {
        // convex
        const pointToRemove = vertexQueue.pop();
        removePoint(pointToRemove, vertexQueue);
      } else {
        // concave
        const pointToRemove = vertexQueue.pop();
        if (canRemoveVertex(pointToRemove)) {
          removePoint(pointToRemove, vertexQueue);
        }
      }
    }

    return model.pointCount <= 2;
  }

  publicAPI.triangulate = () => {
    if (!model.firstPoint) {
      return null;
    }

    return earCutTriangulation();
  };

  publicAPI.setPoints = (points) => {
    model.pointCount = points.length;

    model.firstPoint = {
      id: 0,
      point: points[0],
      next: null,
      previous: null,
    };

    let currentPoint = model.firstPoint;
    for (let i = 1; i < model.pointCount; i++) {
      currentPoint.next = {
        id: i,
        point: points[i],
        next: null,
        previous: currentPoint,
      };
      currentPoint = currentPoint.next;
    }

    model.firstPoint.previous = currentPoint;
    currentPoint.next = model.firstPoint;
  };

  publicAPI.getPointArray = () => model.tris;
}

// ----------------------------------------------------------------------------
// Object factory
// ----------------------------------------------------------------------------

const DEFAULT_VALUES = {
  firstPoint: null,
  pointCount: 0,
  tris: [],
};

// ----------------------------------------------------------------------------

export function extend(publicAPI, model, initialValues = {}) {
  Object.assign(model, DEFAULT_VALUES, initialValues);

  // Build VTK API
  macro.obj(publicAPI, model);
  vtkPolygon(publicAPI, model);
}

// ----------------------------------------------------------------------------

export const newInstance = macro.newInstance(extend, 'vtkPolygon');

// ----------------------------------------------------------------------------

export default { newInstance, extend };