import * as data from "@common/data/data.mjs";
import Scene from "@client/documents/scene.mjs";
import TokenDocument from "@client/documents/token.mjs";
import {Ray} from "@client/canvas/geometry/_module.mjs";
import {CLIPPER_SCALING_FACTOR, TOKEN_SHAPES} from "@common/constants.mjs";
import {PolygonTree} from "./polygon-tree.mjs";

/**
 * @import {DeepReadonly, Point, ClipperPoint} from "@client/_types.mjs";
 * @import {ClientShapeData} from "@common/data/data.mjs";
 * @import BaseGrid from "@common/grid/base.mjs";
 * @import GridlessGrid from "@common/grid/gridless.mjs";
 */

/* -------------------------------------------- */

/**
 * Mixin a BaseShapeData subclass.
 * @param {typeof data.BaseShapeData} ShapeData
 */
function ClientShapeDataMixin(ShapeData) {
  class ClientShapeData extends ShapeData {

    /**
     * The distance snapping precision.
     * @type {number}
     */
    static #DISTANCE_SNAPPING_PRECISION = 2;

    /* -------------------------------------------- */

    /**
     * The rotation snapping interval.
     * @type {number}
     */
    static #ROTATION_SNAPPING_INTERVAL = 5;

    /* -------------------------------------------- */

    /**
     * Convert a path to a clipper path.
     * @param {ClipperPoint[]|Point[]|number[]} path    A path
     * @returns {ClipperPoint[]}
     * @internal
     */
    static _toClipperPath(path) {
      let clipperPath;

      // The path is of type number[]
      if ( path.length && (typeof path[0] === "number") ) {
        clipperPath = [];
        for ( let i = 0; i < path.length; i += 2 ) {
          clipperPath.push({
            X: Math.round(path[i] * CLIPPER_SCALING_FACTOR),
            Y: Math.round(path[i + 1] * CLIPPER_SCALING_FACTOR)
          });
        }
      }

      // The path is of type Point[]
      else if ( path.length && ("x" in path[0]) ) {
        clipperPath = [];
        for ( const point of path ) {
          clipperPath.push({
            X: Math.round(point.x * CLIPPER_SCALING_FACTOR),
            Y: Math.round(point.y * CLIPPER_SCALING_FACTOR)
          });
        }
      }

      // The path is of type ClipperPoint[]
      else clipperPath = path;

      return clipperPath;
    }

    /* -------------------------------------------- */

    /**
     * The scene that this shape is placed in, if any.
     * @type {Scene|null}
     */
    get scene() {
      if ( this.#scene !== undefined ) return this.#scene;
      let scene = this.parent;
      while ( scene && !(scene instanceof Scene) ) scene = scene.parent;
      if ( scene ) scene._dependentShapes.add(this);
      return this.#scene = scene;
    }

    #scene;

    /* -------------------------------------------- */

    /**
     * The grid that this shape is placed in.
     * @type {BaseGrid}
     */
    get grid() {
      return this.scene?.grid ?? Scene.defaultGrid;
    }

    /* -------------------------------------------- */

    /**
     * The gridless version of the grid that this shape is placed in.
     * @type {GridlessGrid}
     */
    get gridlessGrid() {
      return this.scene?.gridlessGrid ?? Scene.defaultGridlessGrid;
    }

    /* -------------------------------------------- */

    /**
     * Is this shape empty?
     * @type {boolean}
     */
    get isEmpty() {
      return this.area === 0;
    }

    /* -------------------------------------------- */

    /**
     * The polygons of this shape.
     *
     * The value of this property must not be mutated.
     * @type {ReadonlyArray<PIXI.Polygon>}
     */
    get polygons() {
      return this.polygonTree.polygons;
    }

    /* -------------------------------------------- */

    /**
     * The polygon tree of this shape.
     *
     * The value of this property must not be mutated.
     * @type {PolygonTree}
     */
    get polygonTree() {
      return this.#polygonTree ??= PolygonTree.fromClipperPolyTree(this.clipperPolyTree);
    }

    #polygonTree;

    /* -------------------------------------------- */

    /**
     * The Clipper paths of this shape.
     * The winding numbers are 1 or 0.
     *
     * The value of this property must not be mutated.
     * @type {DeepReadonly<ClipperPoint[][]>}
     */
    get clipperPaths() {
      return this.polygonTree.clipperPaths;
    }

    /* -------------------------------------------- */

    /**
     * The Clipper polygon tree of this shape.
     *
     * The value of this property must not be mutated.
     * @type {ClipperLib.PolyTree}
     */
    get clipperPolyTree() {
      let clipperPolyTree = this.#clipperPolyTree;
      if ( !clipperPolyTree ) {
        const result = this._createClipperPolyTree();
        let clipperPath;

        if ( Array.isArray(result) ) clipperPath = this.constructor._toClipperPath(result);

        // The result is ClipperPoint[]
        if ( clipperPath ) {
          clipperPolyTree = new ClipperLib.PolyTree();
          if ( clipperPath.length ) {
            const clipperPolyNode = new ClipperLib.PolyNode();
            clipperPolyNode.m_polygon = clipperPath;
            clipperPolyTree.AddChild(clipperPolyNode);
            clipperPolyTree.m_AllPolys.push(clipperPolyNode);
          }
        }

        // The result is ClipperPolyTree
        else clipperPolyTree = result;

        this.#clipperPolyTree = clipperPolyTree;
      }
      return clipperPolyTree;
    }

    #clipperPolyTree;

    /* -------------------------------------------- */

    /**
     * The triangulation of this shape.
     *
     * The value of this property must not be mutated.
     * @type {Readonly<{vertices: Float32Array; indices: Uint16Array|Uint32Array}>}
     */
    get triangulation() {
      return this.polygonTree.triangulation;
    }

    /* -------------------------------------------- */

    /**
     * The bounds of this Region.
     *
     * The value of this property must not be mutated.
     * @type {PIXI.Rectangle}
     */
    get bounds() {
      return this.polygonTree.bounds;
    }

    /* -------------------------------------------- */

    /**
     * The origin of this shape.
     * @type {Readonly<Point>}
     */
    get origin() {
      return this.#origin ??= Object.freeze(this._createOrigin());
    }

    #origin;

    /* -------------------------------------------- */

    /**
     * The center point of this shape.
     * @type {Readonly<Point>}
     */
    get center() {
      return this.#center ??= Object.freeze(this._createCenter());
    }

    #center;

    /* -------------------------------------------- */

    /**
     * The area of this shape.
     * @type {number}
     */
    get area() {
      return this.#area ??= Object.freeze(this._calculateArea());
    }

    #area;

    /* -------------------------------------------- */

    /**
     * The measured segments of this shape.
     * Each segment consist of a ray, winding order, distance in grid units, and the angle in degrees if it has one.
     * The ray represents the measured segment. If the winding order is ...
     *  - 1, the segment is an edge in positive orientation.
     *  - -1, the segment is an edge in negative orientation.
     *  - 0, the segment is not an edge.
     *
     * The distance is the actual grid distance if the shape is grid-based.
     * Otherwise the distance is the distance in pixels divided by of the ratio of grid distance and grid size.
     * @type {DeepReadonly<{ray: Ray; winding: -1|0|1; distance: number; angle?: number}[]>}
     */
    get measuredSegments() {
      return this.#measuredSegments ??= foundry.utils.deepFreeze(this._createMeasuredSegments());
    }

    #measuredSegments;

    /* -------------------------------------------- */

    /**
     * The control handles of this shape.
     * Each handle has a position and a rotation in radians.
     * @type {DeepReadonly<{[name: string]: {position: Point; rotation: number; visible: boolean}}>}
     */
    get controlHandles() {
      return this.#controlHandles ??= foundry.utils.deepFreeze(this._createControlHandles());
    }

    #controlHandles;

    /* -------------------------------------------- */

    /** @inheritDoc */
    _updateCommit(copy, diff, options, state) {
      super._updateCommit(copy, diff, options, state);
      for ( const key in diff ) {
        if ( key === "hole" ) continue;
        if ( (key !== "gridBased") || !this.grid.isGridless ) {
          this._onShapeChange();
          break;
        }
      }
    }

    /* -------------------------------------------- */

    /** @inheritDoc */
    clone(data, context) {
      const clone = super.clone(data, context);
      if ( clone.parent === this.parent ) clone._index = this._index;
      if ( (clone.scene === this.scene) && foundry.utils.equals(clone._source, this._source) ) {
        clone.#polygonTree = this.#polygonTree;
        clone.#clipperPolyTree = this.#clipperPolyTree;
        clone.#origin = this.#origin;
        clone.#measuredSegments = this.#measuredSegments;
        clone.#controlHandles = this.#controlHandles;
      }
      return clone;
    }

    /* -------------------------------------------- */

    /**
     * Called when the shape was changed.
     * This function is not called when just the hole state is changed.
     * This function is not called if grid-based is changed and the grid is gridless.
     * @protected
     */
    _onShapeChange() {
      this.#polygonTree = undefined;
      this.#clipperPolyTree = undefined;
      this.#origin = undefined;
      this.#center = undefined;
      this.#measuredSegments = undefined;
      this.#controlHandles = undefined;
    }

    /* -------------------------------------------- */

    /**
     * Called when the grid this shape is placed in changes.
     * @param {object} changed    The changes to the grid.
     * @protected
     */
    _onGridChange(changed) {
      if ( ("size" in changed) || (this.gridBased && (("type" in changed)
        || (this.grid.isSquare && ("diagonals" in changed)))) ) this._onShapeChange();
      else if ( "distance" in changed ) this.#measuredSegments = undefined;
    }

    /* -------------------------------------------- */

    /**
     * Is this shape currently affected by the grid?
     * @returns {boolean}
     */
    get isAffectedByGrid() {
      return this.gridBased === true;
    }

    /* -------------------------------------------- */

    /**
     * Whether the shape is identical to itself after a rotation around its origin.
     * @returns {boolean}
     */
    get hasRotationalSymmetry() {
      return !this.schema.has("rotation");
    }

    /* -------------------------------------------- */

    /**
     * Create a ray.
     * @param {number} x             The x-coordinate of the origin of the ray.
     * @param {number} y             The y-coordinate of the origin of the ray.
     * @param {number} direction     The direction of the ray in degrees.
     * @param {number} length        The length of the ray in pixels.
     * @param {number} [alignment=0] The alignment to ray.
     * @returns {Ray}
     * @internal
     */
    _createRay(x, y, direction, length, alignment=0) {
      let ray;
      if ( this.gridBased && !this.grid.isGridless ) {
        const distancePixels = this.grid.size / this.grid.distance;
        const from = {x, y};
        const to = this.grid.getTranslatedPoint(from, direction, length / distancePixels);
        ray = new Ray(from, to);
      }
      else ray = Ray.fromAngle(x, y, Math.toRadians(direction), length);
      if ( alignment !== 0 ) {
        const dx = ray.dx * alignment;
        const dy = ray.dy * alignment;
        ray.A.x -= dx;
        ray.A.y -= dy;
        ray.B.x -= dx;
        ray.B.y -= dy;
      }
      return ray;
    }

    /* -------------------------------------------- */

    /**
     * Snap the given point.
     * @param {Point} point    The point that is to be snapped.
     * @returns {Point}        The snapped point.
     * @internal
     */
    _getSnappedPoint(point) {
      if ( this.grid.isGridless ) return {x: Math.round(point.x), y: Math.round(point.y)};
      const M = CONST.GRID_SNAPPING_MODES;
      return this.grid.getSnappedPoint(point, {mode: M.CENTER | M.VERTEX | M.EDGE_MIDPOINT, resolution: 1});
    }

    /* -------------------------------------------- */

    /**
     * Get the size for the given ray defined by a length and direction.
     * @param {number} length       The length of the ray in pixels.
     * @param {number} direction    The direction of the ray in radians.
     * @param {object} [options]                   Additional options.
     * @param {boolean} [options.snap=false]       Snap the size to with defined grid snapping precision?
     * @param {boolean} [options.round]            Round the size to integer?
     * @param {boolean} [options.allowZero=false]  Allow the size to be zero?
     * @returns {number}            The snapped size in pixels.
     * @internal
     */
    _calculateSize(length, direction, {snap=false, round=!snap, allowZero=false}={}) {
      let size = Math.max(length, 0);
      const distancePixels = this.grid.size / this.grid.distance;
      if ( this.gridBased && !this.grid.isGridless ) {
        const {distance} = this.grid.measurePath([{x: 0, y: 0},
          {x: Math.cos(direction) * size, y: Math.sin(direction) * size}]);
        size = distance * distancePixels;
      }
      if ( snap ) {
        const interval = this.grid.distance / ClientShapeData.#DISTANCE_SNAPPING_PRECISION;
        let distance = size / distancePixels;
        distance = distance.toNearest(interval);
        if ( !allowZero ) distance = Math.max(distance, interval);
        size = distance * distancePixels;
      }
      if ( !allowZero ) size = Math.max(size, 1);
      if ( round || size.almostEqual(Math.round(size)) ) size = Math.round(size);
      return size;
    }

    /* -------------------------------------------- */

    /**
     * Snap the given rotation.
     * @param {number} rotation    The rotation to be snapped in degrees.
     * @returns {number}           The snapped rotation in degrees.
     * @internal
     */
    _getSnappedRotation(rotation) {
      return rotation.toNearest(ClientShapeData.#ROTATION_SNAPPING_INTERVAL);
    }

    /* -------------------------------------------- */

    /**
     * Test whether given point is contained within this shape.
     * @param {Point} point    The point.
     * @returns {boolean}
     */
    testPoint(point) {
      return this.polygonTree.testPoint(point);
    }

    /* -------------------------------------------- */

    /**
     * Create the Clipper polygon tree of this shape.
     * This function may return a single positively-orientated and non-selfintersecting Clipper path instead of a tree,
     * which is automatically converted to a Clipper polygon tree.
     * This function is called only once. It is not called if the shape is empty.
     * @returns {ClipperLib.PolyTree|ClipperPoint[]|Point[]|number[]}
     * @protected
     * @abstract
     */
    _createClipperPolyTree() {
      throw new Error("A subclass of the ClientShapeData must implement the _createClipperPolyTree method.");
    }

    /* -------------------------------------------- */

    /**
     * Create the origin point of this shape.
     * @returns {Point}
     * @protected
     */
    _createOrigin() {
      return {x: this.x, y: this.y};
    }

    /* -------------------------------------------- */

    /**
     * Create the center point of this shape.
     * @returns {Point}
     * @protected
     */
    _createCenter() {
      return this.origin;
    }

    /* -------------------------------------------- */

    /**
     * Calculate the area of this shape.
     * @returns {number}
     * @protected
     */
    _calculateArea() {
      return this.polygonTree.area;
    }

    /* -------------------------------------------- */

    /**
     * Move the shape to the given origin.
     * @param {Point} origin                    The (unsnapped) origin.
     * @param {object} [options]                Additional options.
     * @param {boolean} [options.snap=false]    Snap the origin?
     */
    move(origin, {snap=false}={}) {
      const {x, y} = snap ? this._getSnappedPoint(origin) : origin;
      this.updateSource({x, y});
    }

    /* -------------------------------------------- */

    /**
     * Rotate the shape by the given angle in degrees around the origin (or pivot).
     * @param {number} angle           The angle in degrees.
     * @param {object} [options]       Additional options.
     * @param {Point} [options.pivot]  The pivot of rotation. Default: origin.
     */
    rotate(angle, {pivot}={}) {
      if ( angle % 360 === 0 ) return;
      if ( pivot ) {
        const grid = this.gridBased ? this.grid : this.gridlessGrid;
        const direction = Math.toDegrees(Math.atan2(this.origin.y - pivot.y, this.origin.x - pivot.x)) + angle;
        const distance = grid.measurePath([{x: pivot.x, y: pivot.y}, this.origin]).distance;
        const origin = grid.getTranslatedPoint({x: pivot.x, y: pivot.y}, direction, distance);
        this.move(origin);
      }
      this._rotate(angle);
    }

    /* -------------------------------------------- */

    /**
     * Rotate the shape by the given angle in degrees around the origin.
     * @param {number} angle    The angle in degrees.
     * @protected
     */
    _rotate(angle) {
      this.updateSource({rotation: this.rotation + angle});
    }

    /* -------------------------------------------- */

    /**
     * Draw the shape into the Graphics element.
     * @param {PIXI.Graphics} graphics   The Graphics element
     */
    drawShape(graphics) {
      this.polygonTree.drawShape(graphics);
    }

    /* -------------------------------------------- */

    /**
     * Draw reference lines of the shape into the Graphics element, if it has any.
     * @param {PIXI.Graphics} graphics   The Graphics element
     */
    drawReferenceLines(graphics) {}

    /* -------------------------------------------- */

    /**
     * Create a measured segment.
     * @param {number} x           The x-coordinate of the origin of the ray.
     * @param {number} y           The y-coordinate of the origin of the ray.
     * @param {number} direction   The direction of the ray in degrees.
     * @param {number} length      The length of the ray in pixels.
     * @param {number} alignment   The alignment of the ray.
     * @param {-1|0|1} winding     The winding order.
     * @param {number} [angle]     The angle in degrees.
     * @returns {{ray: Ray; winding: -1|0|1; distance: number; angle?: number}}
     * @internal
     */
    _createMeasuredSegment(x, y, direction, length, alignment, winding, angle) {
      const distancePixels = this.grid.size / this.grid.distance;
      const distance = length / distancePixels;
      const segment = {ray: this._createRay(x, y, direction, length, alignment), winding, distance};
      if ( angle !== undefined ) segment.angle = angle;
      return segment;
    }

    /* -------------------------------------------- */

    /**
     * Create the measured segments of this shape.
     * @returns {{ray: Ray; winding: -1|0|1; distance: number; angle?: number}[]}
     * @protected
     * @abstract
     */
    _createMeasuredSegments() {
      throw new Error("A subclass of the ClientShapeData must implement the _createMeasuredSegments method.");
    }

    /* -------------------------------------------- */

    /**
     * Get the control handles for this shape.
     * @returns {{[name: string]: {position: Point; rotation: number; visible: boolean}}}
     *   The position, rotation in radians, and visible state for each handle.
     * @abstract
     */
    _createControlHandles() {
      throw new Error("A subclass of the ClientShapeData must implement the _createControlHandles method.");
    }

    /* -------------------------------------------- */

    /**
     * Move the control handle to the destination position.
     * @param {string} name                       The handle name.
     * @param {Point} destination                 The destination of the handle.
     * @param {object} [options]                  Additional options.
     * @param {boolean} [options.snap=false]      Snapping?
     * @param {boolean} [options.unlinked=false]  Unlinked scaling?
     *
     */
    moveControlHandle(name, destination, options) {
      throw new Error("A subclass of the ClientShapeData must implement the moveControlHandle method.");
    }

    /* -------------------------------------------- */

    /**
     * Transform this shape by moving a scale handle.
     * @param {string} fieldName    The field name of the axis that is scaled.
     * @param {Point} origin        The origin.
     * @param {number} direction    The direction of the axis in degrees.
     * @param {number} alignment    The alignment of the axis.
     * @param {Point} destination   The handle destination.
     * @param {boolean} snap        Snap?
     * @param {boolean} [allowZero=false]    Allow zero size?
     * @param {number} [max]                 The maximum value.
     * @internal
     */
    _moveScaleHandle(fieldName, origin, direction, alignment, destination, snap, allowZero, max) {
      const a = Math.toRadians(this.rotation + direction);
      let size = Math.max((Math.cos(a) * (destination.x - origin.x)) + (Math.sin(a) * (destination.y - origin.y)), 0);
      size *= (1 / (1 - alignment));
      size = this._calculateSize(size, a, {snap, allowZero});
      if ( max !== undefined ) size = Math.min(size, max);
      this.updateSource({[fieldName]: size});
    }

    /* -------------------------------------------- */

    /**
     * Transform this shape by moving a rotation handle.
     * @param {number} direction    The direction of the rotation handle in degrees.
     * @param {Point} destination   The handle destination.
     * @param {boolean} snap        Snap?
     * @internal
     */
    _moveRotationHandle(direction, destination, snap) {
      let rotation = Math.toDegrees(Math.atan2(destination.y - this.origin.y, destination.x - this.origin.x))
        - direction;
      if ( snap ) rotation = this._getSnappedRotation(rotation);
      else rotation = rotation.toNearest(0.01);
      this.rotate(rotation - this.rotation);
    }

    /* -------------------------------------------- */

    /**
     * Transform this shape by moving the sweep handle.
     * @param {number} maxAngle     The maximum angle possible.
     * @param {Point} destination   The handle destination.
     * @param {boolean} snap        Snap?
     * @internal
     */
    _moveSweepHandle(maxAngle, destination, snap) {
      const a = Math.toRadians(-this.rotation);
      const cos = Math.cos(a);
      const sin = Math.sin(a);
      const dx = (cos * (destination.x - this.x)) - (sin * (destination.y - this.y));
      const dy = (sin * (destination.x - this.x)) + (cos * (destination.y - this.y));
      let angle;
      if ( dy <= 0 ) angle = dx >= 0 ? 0 : 360;
      else angle = Math.toDegrees(Math.atan2(dy, dx)) * 2;
      const interval = snap ? ClientShapeData.#ROTATION_SNAPPING_INTERVAL : 1;
      angle = Math.clamp(angle.toNearest(interval), interval, maxAngle);
      this.updateSource({angle});
    }

    /* -------------------------------------------- */

    /**
     * Handle the drag start event for the creation of this shape.
     * @param {PIXI.FederatedEvent} event    The pointer event.
     * @internal
     */
    _onDragStart(event) {
      const interaction = event.interactionData;
      let {origin} = interaction;
      let snap = !event.shiftKey;
      if ( canvas.forceSnapVertices ) {
        origin = this.grid.getSnappedPoint(origin, {mode: CONST.GRID_SNAPPING_MODES.VERTEX});
        snap = false;
      }
      this.move(origin, {snap});
      interaction.origin = this.origin;
    }

    /* -------------------------------------------- */

    /**
     * Handle the drag move event for the creation of this shape.
     * @param {PIXI.FederatedEvent} event    The pointer event.
     * @abstract
     * @internal
     */
    _onDragMove(event) {
      throw new Error("A subclass of the ClientShapeData must implement the _onDragMove method.");
    }

    /* -------------------------------------------- */
    /*  Sampling                                    */
    /* -------------------------------------------- */

    /**
     * Sample a point from the shape interior.
     * @param {Point} [out]    A point to write to.
     * @returns {Point}        The sampled point.
     * @throws {Error}         If the shape is empty.
     */
    sampleInterior(out) {
      if ( this.isEmpty ) throw new Error("Cannot sample an empty shape.");
      return this.polygonTree.sampleInterior(out);
    }

    /* -------------------------------------------- */

    /**
     * Sample a point from the shape boundary.
     * @param {Point} [out]    A point to write to.
     * @returns {Point}        The sampled point.
     * @throws {Error}         If the shape is empty.
     */
    sampleBoundary(out) {
      if ( this.isEmpty ) throw new Error("Cannot sample an empty shape.");
      return this.polygonTree.sampleBoundary(out);
    }
  }
  return ClientShapeData;
}

/* -------------------------------------------- */

/**
 * The data model for a rectangle shape.
 */
export class RectangleShapeData extends ClientShapeDataMixin(data.RectangleShapeData) {

  /** @type {{axisX: Ray; axisY: Ray}} */
  #rays;

  /* -------------------------------------------- */

  /**
   * Get the rays for both axes.
   * @returns {{axisX: Ray; axisY: Ray}}
   * @internal
   */
  _getRays() {
    if ( this.#rays ) return this.#rays;
    const {x, y, width, height, anchorX, anchorY, rotation} = this;
    return this.#rays = {
      axisX: this._createRay(x, y, rotation, width, anchorX),
      axisY: this._createRay(x, y, rotation + 90, height, anchorY)
    };
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    return (this.width <= 0) || (this.height <= 0);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  clone(data, context) {
    const clone = super.clone(data, context);
    if ( this.#rays && (clone.scene === this.scene) && foundry.utils.equals(clone._source, this._source) ) {
      clone.#rays = this.#rays;
    }
    return clone;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#rays = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const distancePixels = grid.size / grid.distance;
    return grid.getRectangle({x: this.x, y: this.y}, this.width / distancePixels,
      this.height / distancePixels, {x: this.anchorX, y: this.anchorY}, this.rotation);
  }

  /* -------------------------------------------- */

  /** @override */
  _createCenter() {
    const a = Math.toRadians(this.rotation);
    const cos = Math.cos(a);
    const sin = Math.sin(a);
    const dx = (0.5 - this.anchorX) * this.width;
    const dy = (0.5 - this.anchorY) * this.height;
    return {x: this.x + ((cos * dx) - (sin * dy)), y: this.y + ((sin * dx) + (cos * dy))};
  }

  /* -------------------------------------------- */

  /** @override */
  _calculateArea() {
    const {axisX, axisY} = this._getRays();
    return axisX.distance * axisY.distance;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleInterior(out) {
    const {axisX, axisY} = this._getRays();
    const x = axisX.A.x + (axisY.A.x - this.x);
    const y = axisX.A.y + (axisY.A.y - this.y);
    return sampleRectangleInterior(out, x, y, axisX, axisY);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleBoundary(out) {
    const {axisX, axisY} = this._getRays();
    const x = axisX.A.x + (axisY.A.x - this.x);
    const y = axisX.A.y + (axisY.A.y - this.y);
    return sampleRectangleBoundary(out, x, y, axisX, axisY);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  drawShape(graphics) {
    if ( this.rotation || (this.gridBased && !this.grid.isGridless) ) super.drawShape(graphics);
    else {
      const {x, y, width, height, anchorX, anchorY} = this;
      graphics.drawRect(x - (anchorX * width), y - (anchorY * height), width, height);
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    const {width, height, anchorX, anchorY} = this;
    const {axisX, axisY} = this._getRays();
    const ray1 = new Ray({x: axisX.A.x, y: axisX.A.y}, {x: axisX.B.x, y: axisX.B.y});
    const ray2 = new Ray({x: axisY.A.x, y: axisY.A.y}, {x: axisY.B.x, y: axisY.B.y});
    const dx1 = anchorX * axisX.dx;
    const dy1 = anchorX * axisX.dy;
    const dx2 = anchorY * axisY.dx;
    const dy2 = anchorY * axisY.dy;
    ray1.A.x -= dx2;
    ray1.A.y -= dy2;
    ray1.B.x -= dx2;
    ray1.B.y -= dy2;
    ray2.A.x -= dx1;
    ray2.A.y -= dy1;
    ray2.B.x -= dx1;
    ray2.B.y -= dy1;
    const distancePixels = this.grid.size / this.grid.distance;
    return [
      {ray: ray1, winding: 1, distance: width / distancePixels},
      {ray: ray2, winding: -1, distance: height / distancePixels}
    ];
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const {x, y, anchorX, anchorY} = this;
    const {axisX, axisY} = this._getRays();
    const s1 = anchorX <= 0.5 ? 1 - anchorX : -anchorX;
    const s2 = anchorY <= 0.5 ? 1 - anchorY : -anchorY;
    return {
      translate: {position: {x, y}, rotation: axisX.angle, visible: true},
      scale: {position: {x: x + (s1 * axisX.dx) + (s2 * axisY.dx), y: y + (s1 * axisX.dy) + (s2 * axisY.dy)},
        rotation: axisX.angle, visible: true},
      rotate: {position: (anchorX < 1) && (anchorY >= 0) && (anchorY <= 1) ? axisX.B : {x, y}, rotation: axisX.angle,
        visible: true}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false, unlinked=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "scale": {
        let {x, y, width, height, anchorX, anchorY, rotation} = this;
        const priorWidth = width;
        const priorHeight = height;
        const a = Math.toRadians(rotation);
        const cos = Math.cos(a);
        const sin = Math.sin(a);
        width = Math.max(((cos * (destination.x - x)) + (sin * (destination.y - y)))
          * (anchorX <= 0.5 ? 1 : -1), 0);
        height = Math.max(((cos * (destination.y - y)) - (sin * (destination.x - x)))
          * (anchorY <= 0.5 ? 1 : -1), 0);
        width /= (anchorX <= 0.5 ? 1 - anchorX : anchorX);
        height /= (anchorY <= 0.5 ? 1 - anchorY : anchorY);
        if ( unlinked ) {
          width = this._calculateSize(width, a, {snap});
          height = this._calculateSize(height, a + (Math.PI / 2), {snap});
        } else {
          const {axisX, axisY} = this._getRays();
          if ( width * axisY.distance >= height * axisX.distance ) {
            width = this._calculateSize(width, a, {snap});
            height = width / priorWidth * priorHeight;
            if ( height.almostEqual(Math.round(height)) ) height = Math.round(height);
          } else {
            height = this._calculateSize(height, a + (Math.PI / 2), {snap});
            width = height / priorHeight * priorWidth;
            if ( width.almostEqual(Math.round(width)) ) width = Math.round(width);
          }
        }
        this.updateSource({width, height});
        break;
      }
      case "rotate": this._moveRotationHandle(0, destination, snap); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {
    const {origin, destination} = event.interactionData;
    const snap = !event.shiftKey;
    const a1 = Math.toRadians(this.rotation);
    const a2 = a1 + (Math.PI / 2);

    // Calculate the dimensions based on the drag-origin and drag-destination and the rotation of the rectangle
    const cos = Math.cos(a1);
    const sin = Math.sin(a1);
    const dx = destination.x - origin.x;
    const dy = destination.y - origin.y;
    let width = (cos * dx) + (sin * dy);
    let height = (cos * dy) - (sin * dx);
    const invertedX = width < 0;
    const invertedY = height < 0;
    width = this._calculateSize(Math.abs(width), a1, {snap, allowZero: true});
    height = this._calculateSize(Math.abs(height), a2, {snap, allowZero: true});

    // Calculate the origin
    let {x, y} = origin;
    if ( (width !== 0) || (height !== 0) ) {

      // If either dimension is nonzero, make the other dimensions nonzero as well
      width ||= this._calculateSize(0, a1, {snap});
      height ||= this._calculateSize(0, a2, {snap});

      // Force to square
      if ( event.altKey ) width = height = Math.min(width, height);

      // Calculate the origin based on the anchor
      const ray1 = this._createRay(0, 0, this.rotation, width, 0);
      const ray2 = this._createRay(0, 0, this.rotation + 90, height, 0);
      const s1 = invertedX ? (this.anchorX - 1) : this.anchorX;
      const s2 = invertedY ? (this.anchorY - 1) : this.anchorY;
      x += ((s1 * ray1.dx) + (s2 * ray2.dx));
      y += ((s1 * ray1.dy) + (s2 * ray2.dy));
    }

    // Round origin coordinates to integers if almost integer
    if ( x.almostEqual(Math.round(x)) ) x = Math.round(x);
    if ( y.almostEqual(Math.round(y)) ) y = Math.round(y);

    this.updateSource({x, y, width, height});
  }
}

/* -------------------------------------------- */

/**
 * The data model for a circle shape.
 */
export class CircleShapeData extends ClientShapeDataMixin(data.CircleShapeData) {

  /** @override */
  get isEmpty() {
    return this.radius <= 0;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const distancePixels = grid.size / grid.distance;
    return grid.getCircle({x: this.x, y: this.y}, this.radius / distancePixels);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _calculateArea() {
    if ( !this.gridBased || this.grid.isGridless ) return Math.PI * (this.radius * this.radius);
    return super._calculateArea();
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleInterior(out) {
    if ( this.gridBased && !this.grid.isGridless ) return super.sampleInterior(out);
    if ( this.isEmpty ) throw new Error("Cannot sample an empty shape.");
    const point = out ?? {x: 0, y: 0};
    const angle = Math.random() * (Math.PI * 2);
    const radius = Math.sqrt(Math.random()) * this.radius;
    point.x = this.x + (Math.cos(angle) * radius);
    point.y = this.y + (Math.sin(angle) * radius);
    return point;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleBoundary(out) {
    if ( this.gridBased && !this.grid.isGridless ) return super.sampleBoundary(out);
    if ( this.isEmpty ) throw new Error("Cannot sample an empty shape.");
    const point = out ?? {x: 0, y: 0};
    const angle = Math.random() * (Math.PI * 2);
    point.x = this.x + (Math.cos(angle) * this.radius);
    point.y = this.y + (Math.sin(angle) * this.radius);
    return point;
  }

  /* -------------------------------------------- */

  /** @override */
  _rotate(angle) {}

  /* -------------------------------------------- */

  /** @inheritDoc */
  drawShape(graphics) {
    if ( this.gridBased && !this.grid.isGridless ) super.drawShape(graphics);
    else graphics.drawCircle(this.x, this.y, this.radius);
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    return [this._createMeasuredSegment(this.x, this.y, 0, this.radius, 0, 0)];
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const ray = this._createRay(this.x, this.y, 0, this.radius);
    return {
      translate: {position: ray.A, rotation: 0, visible: true},
      scale: {position: ray.B, rotation: 0, visible: true}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "scale": this._moveScaleHandle("radius", this.origin, 0, 0, destination, snap); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {
    const {origin, destination} = event.interactionData;
    const snap = !event.shiftKey;
    const dx = destination.x - origin.x;
    const dy = destination.y - origin.y;
    const radius = this._calculateSize(Math.hypot(dx, dy), Math.atan2(dy, dx), {snap, allowZero: true});
    this.updateSource({x: origin.x, y: origin.y, radius});
  }
}

/* -------------------------------------------- */

/**
 * The data model for an ellipse shape.
 */
export class EllipseShapeData extends ClientShapeDataMixin(data.EllipseShapeData) {

  /** @type {{axisX: Ray; axisY: Ray}} */
  #rays;

  /* -------------------------------------------- */

  /**
   * Get the rays for both axes.
   * @returns {{axisX: Ray; axisY: Ray}}
   * @internal
   */
  _getRays() {
    if ( this.#rays ) return this.#rays;
    const {x, y, radiusX, radiusY, rotation} = this;
    return this.#rays = {
      axisX: this._createRay(x, y, rotation, radiusX),
      axisY: this._createRay(x, y, rotation + 90, radiusY)
    };
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    return (this.radiusX <= 0) || (this.radiusY <= 0);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  clone(data, context) {
    const clone = super.clone(data, context);
    if ( this.#rays && (clone.scene === this.scene) && foundry.utils.equals(clone._source, this._source) ) {
      clone.#rays = this.#rays;
    }
    return clone;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#rays = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const distancePixels = grid.size / grid.distance;
    return grid.getEllipse({x: this.x, y: this.y}, this.radiusX / distancePixels,
      this.radiusY / distancePixels, this.rotation);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _calculateArea() {
    if ( !this.gridBased || this.grid.isGridless ) return Math.PI * (this.radiusX * this.radiusY);
    return super._calculateArea();
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleInterior(out) {
    if ( this.gridBased && !this.grid.isGridless ) return super.sampleInterior(out);
    if ( this.isEmpty ) throw new Error("Cannot sample an empty shape.");
    const {axisX, axisY} = this._getRays();
    const point = out ?? {x: 0, y: 0};
    const angle = Math.random() * (Math.PI * 2);
    const radius = Math.sqrt(Math.random());
    const s = Math.cos(angle) * radius;
    const t = Math.sin(angle) * radius;
    point.x = this.x + (axisX.dx * s) + (axisY.dx * t);
    point.y = this.y + (axisX.dy * s) + (axisY.dy * t);
    return point;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  drawShape(graphics) {
    if ( this.rotation || (this.gridBased && !this.grid.isGridless) ) super.drawShape(graphics);
    else graphics.drawEllipse(this.x, this.y, this.radiusX, this.radiusY);
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    const {axisX, axisY} = this._getRays();
    const distancePixels = this.grid.size / this.grid.distance;
    return [
      {ray: axisX, winding: 0, distance: this.radiusX / distancePixels},
      {ray: axisY, winding: 0, distance: this.radiusY / distancePixels}
    ];
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const {axisX, axisY} = this._getRays();
    return {
      translate: {position: axisX.A, rotation: axisX.angle, visible: true},
      scaleX: {position: axisX.B, rotation: axisX.angle, visible: true},
      scaleY: {position: axisY.B, rotation: axisY.angle, visible: true},
      rotate: {position: axisX.B, rotation: axisX.angle, visible: true}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "scaleX": this._moveScaleHandle("radiusX", this.origin, 0, 0, destination, snap); break;
      case "scaleY": this._moveScaleHandle("radiusY", this.origin, 90, 0, destination, snap); break;
      case "rotate": this._moveRotationHandle(0, destination, snap); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {
    const {origin, destination} = event.interactionData;
    const snap = !event.shiftKey;
    const a1 = Math.toRadians(this.rotation);
    const a2 = a1 + (Math.PI / 2);

    // Calculate the dimensions based on the drag-origin and drag-destination and the rotation of the ellipse
    const cos = Math.cos(a1);
    const sin = Math.sin(a1);
    const dx = destination.x - origin.x;
    const dy = destination.y - origin.y;
    let radiusX = this._calculateSize(Math.abs((cos * dx) + (sin * dy)), a1, {snap, allowZero: true});
    let radiusY = this._calculateSize(Math.abs((cos * dy) - (sin * dx)), a2, {snap, allowZero: true});

    if ( (radiusX !== 0) || (radiusY !== 0) ) {

      // If either dimension is nonzero, make the other dimensions nonzero as well
      radiusX ||= this._calculateSize(0, a1, {snap});
      radiusY ||= this._calculateSize(0, a2, {snap});

      // Force to circle
      if ( event.altKey ) radiusX = radiusY = Math.min(radiusX, radiusY);
    }

    this.updateSource({x: origin.x, y: origin.y, radiusX, radiusY});
  }
}

/* -------------------------------------------- */

/**
 * The data model for a cone shape.
 */
export class ConeShapeData extends ClientShapeDataMixin(data.ConeShapeData) {

  /** @type {{left: Ray; center: Ray; right: Ray}} */
  #rays;

  /* -------------------------------------------- */

  /**
   * Get the left, center, and right rays of this cone.
   * @returns {{left: Ray; center: Ray; right: Ray}}
   * @internal
   */
  _getRays() {
    if ( this.#rays ) return this.#rays;
    const {x, y, radius, angle, rotation, curvature} = this;
    const center = this._createRay(x, y, rotation, radius);

    // Flat curvature
    if ( curvature === "flat" ) {
      const halfAngle = Math.toRadians(angle) / 2;
      const length = center.distance / Math.cos(halfAngle);
      const left = Ray.fromAngle(x, y, center.angle - halfAngle, length);
      const right = Ray.fromAngle(x, y, center.angle + halfAngle, length);
      return this.#rays = {left, center, right};
    }

    // Semicircle curvature
    if ( (curvature === "semicircle") && (angle < 180) ) {
      const halfAngle = Math.toRadians(angle) / 2;
      const normalizedRight = Ray.fromAngle(x, y, center.angle + halfAngle, 1);
      const grid = this.gridBased ? this.grid : this.gridlessGrid;
      let intersectingAngle = center.angle + (0.5 * Math.PI);
      if ( !grid.isHexagonal ) intersectingAngle += (0.25 * Math.PI);
      else {
        const v = grid.getTranslatedPoint({x: 0, y: 0}, rotation, 1);
        const w = grid.getTranslatedPoint({x: 0, y: 0}, rotation + 90, 1);
        intersectingAngle += Math.atan(Math.hypot(v.x, v.y) / Math.hypot(w.x, w.y));
      }
      const intersectingLine = Ray.fromAngle(center.B.x, center.B.y, intersectingAngle, 1);
      const {t0: length} = foundry.utils.lineLineIntersection(normalizedRight.A, normalizedRight.B,
        intersectingLine.A, intersectingLine.B);
      const left = Ray.fromAngle(x, y, center.angle - halfAngle, length);
      const right = Ray.fromAngle(x, y, center.angle + halfAngle, length);
      return this.#rays = {left, center, right};
    }

    // Round curvature
    return this.#rays = {
      left: this._createRay(x, y, rotation - (angle / 2), radius),
      center,
      right: this._createRay(x, y, rotation + (angle / 2), radius)
    };
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    return (this.radius <= 0) || (this.angle <= 0);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  clone(data, context) {
    const clone = super.clone(data, context);
    if ( this.#rays && (clone.scene === this.scene) && foundry.utils.equals(clone._source, this._source) ) {
      clone.#rays = this.#rays;
    }
    return clone;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#rays = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    if ( (this.radius <= 0) || (this.angle <= 0) ) return new ClipperLib.PolyTree();

    // Flat curvature
    if ( this.curvature === "flat" ) {
      const {left, center, right} = this._getRays();
      return [center.A, left.B, right.B];
    }

    const grid = this.gridBased ? this.grid : this.gridlessGrid;

    // Semicircle curvature
    if ( (this.curvature === "semicircle") && (this.angle < 180) ) {
      const {left, center, right} = this._getRays();
      const intersection = foundry.utils.lineLineIntersection(center.A, center.B, left.B, right.B);
      const distance = grid.measurePath([intersection, center.B]).distance;
      const points = grid.getCone(intersection, distance, this.rotation, 180);
      points[0].x = this.x;
      points[0].y = this.y;
      return points;
    }

    // Round curvature
    const distancePixels = grid.size / grid.distance;
    return grid.getCone({x: this.x, y: this.y}, this.radius / distancePixels, this.rotation, this.angle);
  }

  /* -------------------------------------------- */

  /** @override */
  _createCenter() {
    if ( this.angle === 360 ) return this.origin;
    return foundry.utils.polygonCentroid(this.polygons[0].points);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _calculateArea() {
    if ( (this.curvature === "round") && (!this.gridBased || this.grid.isGridless) ) {
      return Math.PI * (this.radius * this.radius) * (this.angle / 360);
    }
    return super._calculateArea();
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    const distancePixels = this.grid.size / this.grid.distance;
    return [{ray: this._getRays().center, winding: 0, distance: this.radius / distancePixels, angle: this.angle}];
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const {center, right} = this._getRays();
    return {
      translate: {position: center.A, rotation: center.angle, visible: true},
      scale: {position: center.B, rotation: center.angle, visible: true},
      sweep: {position: right.project(0.5), rotation: right.angle, visible: true},
      rotate: {position: center.B, rotation: center.angle, visible: true}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "scale": this._moveScaleHandle("radius", this.origin, 0, 0, destination, snap); break;
      case "rotate": this._moveRotationHandle(0, destination, snap); break;
      case "sweep": {
        const maxAngle = this.curvature === "flat" ? 90 : (this.curvature === "semicircle" ? 180 : 360);
        this._moveSweepHandle(maxAngle, destination, snap);
        break;
      }
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {
    const {origin, destination} = event.interactionData;
    const snap = !event.shiftKey;
    const dx = destination.x - origin.x;
    const dy = destination.y - origin.y;
    let rotation = Math.toDegrees(Math.atan2(dy, dx));
    if ( snap ) rotation = this._getSnappedRotation(rotation);
    else rotation = rotation.toNearest(0.01);
    const radius = this._calculateSize(Math.hypot(dx, dy), Math.toRadians(rotation), {snap, allowZero: true});
    this.updateSource({x: origin.x, y: origin.y, radius, rotation});
  }
}

/* -------------------------------------------- */

/**
 * The data model for a ring shape.
 */
export class RingShapeData extends ClientShapeDataMixin(data.RingShapeData) {

  /**
   * The cached circle polygon for this ring.
   * @type {Point[]}
   */
  #circlePolygon;

  /**
   * The cached Euclidean point-sampling data for this ring.
   * @type {{
   *   innerRadius: number;
   *   outerRadius: number;
   *   innerRadiusSquared: number;
   *   outerRadiusSquared: number;
   *   totalRadius: number;
   * }}
   */
  #euclideanSamplingData;

  /* -------------------------------------------- */

  /**
   * Get the circle polygon of this ring.
   * @returns {Point[]}
   */
  #getCirclePolygon() {
    if ( this.#circlePolygon ) return this.#circlePolygon;
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const distancePixels = this.grid.size / grid.distance;
    return this.#circlePolygon = grid.getCircle({x: this.x, y: this.y}, this.radius / distancePixels);
  }

  /* -------------------------------------------- */

  /**
   * Get the cached Euclidean point-sampling data.
   * @returns {{
   *   innerRadius: number;
   *   outerRadius: number;
   *   innerRadiusSquared: number;
   *   outerRadiusSquared: number;
   *   totalRadius: number;
   * }}
   */
  #getEuclideanSamplingData() {
    if ( this.#euclideanSamplingData ) return this.#euclideanSamplingData;
    const innerRadius = Math.max(this.radius - this.innerWidth, 0);
    const outerRadius = this.radius + this.outerWidth;
    return this.#euclideanSamplingData = {
      innerRadius,
      outerRadius,
      innerRadiusSquared: innerRadius * innerRadius,
      outerRadiusSquared: outerRadius * outerRadius,
      totalRadius: innerRadius + outerRadius
    };
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    const innerRadius = Math.max(this.radius - this.innerWidth, 0);
    const outerRadius = this.radius + this.outerWidth;
    return outerRadius <= innerRadius;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  clone(data, context) {
    const clone = super.clone(data, context);
    if ( (this.#circlePolygon || this.#euclideanSamplingData) && (clone.scene === this.scene)
      && foundry.utils.equals(clone._source, this._source) ) {
      clone.#circlePolygon = this.#circlePolygon;
      clone.#euclideanSamplingData = this.#euclideanSamplingData;
    }
    return clone;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#circlePolygon = undefined;
    this.#euclideanSamplingData = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const distancePixels = grid.size / grid.distance;
    const [innerCircle, outerCircle] = grid.getRing({x: this.x, y: this.y}, this.radius / distancePixels,
      this.innerWidth / distancePixels, this.outerWidth / distancePixels);
    const clipperPolyTree = new ClipperLib.PolyTree();
    if ( outerCircle.length !== 0 ) {
      const clipperOuterPolyNode = new ClipperLib.PolyNode();
      const clipperOuterPath = clipperOuterPolyNode.Contour();
      for ( const point of outerCircle ) {
        clipperOuterPath.push({
          X: Math.round(point.x * CLIPPER_SCALING_FACTOR),
          Y: Math.round(point.y * CLIPPER_SCALING_FACTOR)
        });
      }
      clipperPolyTree.AddChild(clipperOuterPolyNode);
      clipperPolyTree.m_AllPolys.push(clipperOuterPolyNode);
      if ( innerCircle.length !== 0 ) {
        const clipperInnerPolyNode = new ClipperLib.PolyNode();
        const clipperInnerPath = clipperInnerPolyNode.Contour();
        for ( const point of innerCircle ) {
          clipperInnerPath.push({
            X: Math.round(point.x * CLIPPER_SCALING_FACTOR),
            Y: Math.round(point.y * CLIPPER_SCALING_FACTOR)
          });
        }
        clipperInnerPath.reverse();
        clipperOuterPolyNode.AddChild(clipperInnerPolyNode);
        clipperPolyTree.m_AllPolys.push(clipperInnerPolyNode);
      }
    }
    return clipperPolyTree;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _calculateArea() {
    if ( !this.gridBased || this.grid.isGridless ) {
      const innerRadius = Math.max(this.radius - this.innerWidth, 0);
      const outerRadius = this.radius + this.outerWidth;
      return Math.PI * ((outerRadius * outerRadius) - (innerRadius * innerRadius));
    }
    return super._calculateArea();
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleInterior(out) {
    if ( this.gridBased && !this.grid.isGridless ) return super.sampleInterior(out);
    const {innerRadiusSquared, outerRadiusSquared} = this.#getEuclideanSamplingData();
    if ( outerRadiusSquared <= innerRadiusSquared ) throw new Error("Cannot sample an empty shape.");
    const point = out ?? {x: 0, y: 0};
    const angle = Math.random() * (Math.PI * 2);
    const radius = Math.sqrt(innerRadiusSquared + (Math.random() * (outerRadiusSquared - innerRadiusSquared)));
    point.x = this.x + (Math.cos(angle) * radius);
    point.y = this.y + (Math.sin(angle) * radius);
    return point;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleBoundary(out) {
    if ( this.gridBased && !this.grid.isGridless ) return super.sampleBoundary(out);
    const {innerRadius, outerRadius, totalRadius} = this.#getEuclideanSamplingData();
    if ( this.isEmpty ) throw new Error("Cannot sample an empty shape.");
    const point = out ?? {x: 0, y: 0};
    const angle = Math.random() * (Math.PI * 2);
    const radius = ((Math.random() * totalRadius) < outerRadius) ? outerRadius : innerRadius;
    point.x = this.x + (Math.cos(angle) * radius);
    point.y = this.y + (Math.sin(angle) * radius);
    return point;
  }

  /* -------------------------------------------- */

  /** @override */
  _rotate(angle) {}

  /* -------------------------------------------- */

  /** @inheritDoc */
  drawShape(graphics) {
    if ( this.gridBased && !this.grid.isGridless ) {
      super.drawShape(graphics);
      return;
    }
    const innerRadius = this.radius - this.innerWidth;
    const outerRadius = this.radius + this.outerWidth;
    graphics.drawCircle(this.x, this.y, outerRadius);
    if ( innerRadius > 0 ) {
      graphics.beginHole();
      graphics.drawCircle(this.x, this.y, innerRadius);
      graphics.endHole();
    }
  }

  /* -------------------------------------------- */

  /** @override */
  drawReferenceLines(graphics) {
    if ( (this.radius === 0) || (this.innerWidth === 0) || (this.outerWidth === 0) ) return;
    if ( this.gridBased && !this.grid.isGridless ) graphics.drawPolygon(this.#getCirclePolygon());
    else graphics.drawCircle(this.x, this.y, this.radius);
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    const distancePixels = this.grid.size / this.grid.distance;
    const {B: {x: x0, y: y0}} = this._createRay(this.x, this.y, 90, this.radius);
    const segments = [
      this._createMeasuredSegment(this.x, this.y, 0, this.radius, 0, 0),
      {ray: this._createRay(x0, y0, 90, this.outerWidth), winding: 0, distance: this.outerWidth / distancePixels}
    ];
    if ( this.innerWidth <= this.radius ) {
      segments.push({ray: this._createRay(x0, y0, 270, this.innerWidth), winding: 0,
        distance: this.innerWidth / distancePixels});
    }
    return segments;
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const ray1 = this._createRay(this.x, this.y, 0, this.radius);
    const {B: {x: x0, y: y0}} = this._createRay(this.x, this.y, 90, this.radius);
    const ray2 = this._createRay(x0, y0, 270, this.innerWidth);
    const ray3 = this._createRay(x0, y0, 90, this.outerWidth);
    return {
      translate: {position: ray1.A, rotation: 0, visible: true},
      scale: {position: ray1.B, rotation: ray1.angle, visible: true},
      inset: {position: ray2.B, rotation: ray3.angle, visible: true},
      offset: {position: ray3.B, rotation: ray3.angle, visible: true}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "scale": this._moveScaleHandle("radius", this.origin, 0, 0, destination, snap); break;
      case "inset": this._moveScaleHandle("innerWidth", this._createRay(this.x, this.y, 90, this.radius).B, 270, 0, destination, snap, this.outerWidth > 0, this.radius); break;
      case "offset": this._moveScaleHandle("outerWidth", this._createRay(this.x, this.y, 90, this.radius).B, 90, 0, destination, snap, this.innerWidth > 0); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {
    const {origin, destination} = event.interactionData;
    const snap = !event.shiftKey;
    const dx = destination.x - origin.x;
    const dy = destination.y - origin.y;
    const radius = this._calculateSize(Math.hypot(dx, dy), Math.atan2(dy, dx), {snap, allowZero: true});
    this.updateSource({x: origin.x, y: origin.y, radius});
  }
}

/* -------------------------------------------- */

/**
 * The data model for a line shape.
 */
export class LineShapeData extends ClientShapeDataMixin(data.LineShapeData) {

  /** @type {{axisX: Ray; axisY: Ray}} */
  #rays;

  /* -------------------------------------------- */

  /**
   * Get the rays for both axes.
   * @returns {{axisX: Ray; axisY: Ray}}
   * @internal
   */
  _getRays() {
    if ( this.#rays ) return this.#rays;
    const {x, y, length, width, rotation} = this;
    return this.#rays = {
      axisX: this._createRay(x, y, rotation, length),
      axisY: this._createRay(x, y, rotation + 90, width, 0.5)
    };
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    return (this.length <= 0) || (this.width <= 0);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  clone(data, context) {
    const clone = super.clone(data, context);
    if ( this.#rays && (clone.scene === this.scene)
      && foundry.utils.equals(clone._source, this._source) ) {
      clone.#rays = this.#rays;
    }
    return clone;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#rays = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const distancePixels = grid.size / grid.distance;
    return grid.getLine({x: this.x, y: this.y}, this.length / distancePixels,
      this.width / distancePixels, this.rotation);
  }

  /* -------------------------------------------- */

  /** @override */
  _createCenter() {
    return this._getRays().axisX.project(0.5);
  }

  /* -------------------------------------------- */

  /** @override */
  _calculateArea() {
    const {axisX, axisY} = this._getRays();
    return axisX.distance * axisY.distance;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleInterior(out) {
    const {axisX, axisY} = this._getRays();
    return sampleRectangleInterior(out, axisY.A.x, axisY.A.y, axisX, axisY);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleBoundary(out) {
    const {axisX, axisY} = this._getRays();
    return sampleRectangleBoundary(out, axisY.A.x, axisY.A.y, axisX, axisY);
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    const distancePixels = this.grid.size / this.grid.distance;
    const {axisX, axisY} = this._getRays();
    return [
      {ray: axisX, winding: 0, distance: this.length / distancePixels},
      {ray: axisY, winding: -1, distance: this.width / distancePixels}
    ];
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const {axisX, axisY} = this._getRays();
    return {
      translate: {position: axisX.A, rotation: axisX.angle, visible: true},
      scaleX: {position: axisX.B, rotation: axisX.angle, visible: true},
      scaleY: {position: {x: axisY.B.x + (axisX.dx / 2), y: axisY.B.y + (axisX.dy / 2)}, rotation: axisY.angle,
        visible: true},
      rotate: {position: axisX.B, rotation: axisX.angle, visible: true}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "scaleX": this._moveScaleHandle("length", this.origin, 0, 0, destination, snap); break;
      case "scaleY": this._moveScaleHandle("width", this.origin, 90, 0.5, destination, snap); break;
      case "rotate": this._moveRotationHandle(0, destination, snap); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {
    const {origin, destination} = event.interactionData;
    const snap = !event.shiftKey;
    const dx = destination.x - origin.x;
    const dy = destination.y - origin.y;
    let rotation = Math.toDegrees(Math.atan2(dy, dx));
    if ( snap ) rotation = this._getSnappedRotation(rotation);
    else rotation = rotation.toNearest(0.01);
    const length = this._calculateSize(Math.hypot(dx, dy), Math.toRadians(rotation), {snap, allowZero: true});
    this.updateSource({x: origin.x, y: origin.y, length, rotation});
  }
}

/* -------------------------------------------- */

/**
 * The data model for an emanation shape.
 */
export class EmanationShapeData extends ClientShapeDataMixin(data.EmanationShapeData) {

  /** @type {Ray} */
  #ray;

  /* -------------------------------------------- */

  /**
   * Get the ray.
   * @returns {Ray}
   */
  #getRay() {
    if ( this.#ray ) return this.#ray;
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const base = this.base.type === "token" ? this.base._getTokenShape() : this.base;
    let x;
    let y;
    let direction = base.rotation;
    switch ( base.type ) {
      case "rectangle":
      case "ellipse":
      case "line":
        ({x, y} = base._getRays().axisX.B);
        break;
      case "circle":
        ({x, y} = base._createRay(base.x, base.y, base.rotation, base.radius).B);
        break;
      case "cone":
        ({x, y} = base._getRays().center.B);
        break;
      case "polygon": {
        // Try to pick the most pleasing location
        const {left, right} = base.bounds;
        const epsilon = 1 / CLIPPER_SCALING_FACTOR;
        const points = base.polygons[0].points;
        for ( let i = 0; i < points.length; i += 2 ) {
          const x0 = points[i];
          if ( (x0 > left + epsilon) && (x0 < right - epsilon) ) continue;
          const i1 = (i + 2) % points.length;
          let y0;
          if ( points[i1] !== x0 ) y0 = points[i + 1];
          else {
            y0 = (points[i + 1] + points[i1 + 1]) / 2;
            i += 2;
          }
          const dy = y - this.origin.y;
          const dy0 = y0 - this.origin.y;
          if ( (x === undefined) || (Math.abs(dy0) < Math.abs(dy) - epsilon)
            || (Math.abs(dy0).almostEqual(Math.abs(dy), 2 * epsilon)
            && (x0 > this.origin.x) && ((x < this.origin) || (Math.sign(dy0) < Math.sign(dy)))) ) {
            [x, y] = [x0, y0];
          }
        }
        direction = x >= this.origin.x ? 0 : 180;
        break;
      }
      default: throw new Error("Invalid base shape type");
    }
    const distancePixels = grid.size / grid.distance;
    const A = {x, y};
    const B = grid.getTranslatedPoint(A, direction, this.radius / distancePixels);
    return this.#ray = new Ray(A, B);
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    return this.base.isEmpty;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#ray = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  get isAffectedByGrid() {
    return this.gridBased || this.base.isAffectedByGrid;
  }

  /* -------------------------------------------- */

  /** @override */
  get hasRotationalSymmetry() {
    return this.base.hasRotationalSymmetry;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    if ( this.base.isEmpty ) return new ClipperLib.PolyTree();
    if ( this.radius <= 0 ) return this.base.hole ? new ClipperLib.PolyTree() : this.base.clipperPolyTree;
    const grid = this.gridBased ? this.grid : this.gridlessGrid;
    const base = this.base.type === "token" ? this.base._getTokenShape() : this.base;
    const baseGrid = base.gridBased ? base.grid : base.gridlessGrid;

    // Circle
    if ( (base.type === "circle") && (baseGrid.isGridless === grid.isGridless)
      && (!grid.isSquare || ((grid.diagonals !== CONST.GRID_DIAGONALS.ALTERNATING_1)
      && (grid.diagonals !== CONST.GRID_DIAGONALS.ALTERNATING_2))) ) {
      const distancePixels = grid.size / grid.distance;
      if ( base.hole ) {
        const ring = new RingShapeData({x: base.x, y: base.y, radius: base.radius, innerWidth: 0,
          outerWidth: this.radius, gridBased: this.gridBased}, {parent: this.parent});
        return ring.clipperPolyTree;
      }
      return grid.getCircle({x: base.x, y: base.y}, (base.radius + this.radius) / distancePixels);
    }

    let minkowskiSum;

    // Euclidean ellipse
    if ( (base.type === "ellipse") && baseGrid.isGridless && grid.isGridless ) {
      const {x, y, rotation} = base;
      const r1 = base.radiusX;
      const r2 = base.radiusY;
      const r3 = this.radius;
      const maxR = Math.max(r1, r2) + r3;
      const n = Math.max(Math.ceil(Math.PI / Math.acos(Math.max(maxR - 0.25, 0) / maxR)), 4);
      const points = new Array(n);
      const angle = Math.toRadians(rotation);
      const cos = Math.cos(angle);
      const sin = Math.sin(angle);
      for ( let i = 0, j = 0; i < n; i++ ) {
        const a = 2 * Math.PI * (i / n);
        const c = Math.cos(a);
        const s = Math.sin(a);
        const nx = c * r2;
        const ny = s * r1;
        const nd = Math.hypot(nx, ny);
        const dx = (c * r1) + (nx / nd * r3);
        const dy = (s * r2) + (ny / nd * r3);
        points[j++] = x + ((cos * dx) - (sin * dy));
        points[j++] = y + ((sin * dx) + (cos * dy));
      }
      minkowskiSum = points;
    }

    // Rounded rectangle / line
    else if ( (base.type === "rectangle") || (base.type === "line") ) {
      const distancePixels = grid.size / grid.distance;
      const range = this.radius / distancePixels;
      const [x0, y0, x1, y1, x2, y2, x3, y3] = base.polygons[0].points;
      const rotation = base.rotation;
      minkowskiSum = [
        ...grid.getCone({x: x0, y: y0}, range, rotation + 225, 90).slice(1),
        ...grid.getCone({x: x1, y: y1}, range, rotation + 315, 90).slice(1),
        ...grid.getCone({x: x2, y: y2}, range, rotation + 45, 90).slice(1),
        ...grid.getCone({x: x3, y: y3}, range, rotation + 135, 90).slice(1)
      ];
    }

    // Any other shape type
    else {
      const tokenPath = base.clipperPaths[0];
      const distancePixels = grid.size / grid.distance;
      const range = this.radius / distancePixels;

      // Compute the path of the emanation circle
      const emanationPath = [];
      for ( const {x, y} of grid.getCircle({x: 0, y: 0}, range) ) {
        emanationPath.push({
          X: Math.round(x * CLIPPER_SCALING_FACTOR),
          Y: Math.round(y * CLIPPER_SCALING_FACTOR)
        });
      }

      // Compute the Minkowski sum of the token's shape and the emanation circle
      const intermediateSolution = ClipperLib.Clipper.MinkowskiSum(emanationPath, tokenPath, true);

      // The intermediate solution is broken, we need to fix it
      const solution = new ClipperLib.PolyTree();
      const clipper = new ClipperLib.Clipper();
      clipper.StrictlySimple = true;
      clipper.AddPaths(intermediateSolution, ClipperLib.PolyType.ptSubject, true);
      clipper.Execute(ClipperLib.ClipType.ctUnion, solution, ClipperLib.PolyFillType.pftEvenOdd,
        ClipperLib.PolyFillType.pftEvenOdd);
      minkowskiSum = solution.Childs()[0].Contour();
    }

    // Subtract base shape if hole
    if ( !base.hole ) return minkowskiSum;
    const solution = new ClipperLib.PolyTree();
    const clipper = new ClipperLib.Clipper();
    clipper.AddPath(this.constructor._toClipperPath(minkowskiSum), ClipperLib.PolyType.ptSubject, true);
    clipper.AddPaths(base.clipperPaths, ClipperLib.PolyType.ptClip, true);
    clipper.Execute(ClipperLib.ClipType.ctDifference, solution, ClipperLib.PolyFillType.pftEvenOdd,
      ClipperLib.PolyFillType.pftEvenOdd);
    return solution;
  }

  /* -------------------------------------------- */

  /** @override */
  _createOrigin() {
    return this.base.origin;
  }

  /* -------------------------------------------- */

  /** @override */
  move(origin, options) {
    const base = this.base.clone();
    base.move(origin, options);
    this.updateSource({base: base.toObject()});
  }

  /* -------------------------------------------- */

  /** @override */
  _rotate(angle) {
    const base = this.base.clone();
    base.rotate(angle);
    this.updateSource({base: base.toObject()});
  }

  /* -------------------------------------------- */

  /** @override */
  drawReferenceLines(graphics) {
    this.base.drawReferenceLines(graphics);
    if ( (this.radius > 0) && !this.base.hole ) this.base.drawShape(graphics);
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    if ( this.radius <= 0 ) return [];
    const distancePixels = this.grid.size / this.grid.distance;
    const range = this.radius / distancePixels;
    return [...this.base.measuredSegments, {ray: this.#getRay(), winding: 0, distance: range}];
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const ray = this.#getRay();
    return {...this.base.controlHandles, offset: {position: ray.B, rotation: ray.angle, visible: true}};
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, options={}) {
    if ( name === "offset" ) {
      const {snap=false} = options;
      const x0 = this.#getRay().A.x;
      const radius = this._calculateSize(Math.max(Math.sign(x0 - this.origin.x) * (destination.x - x0), 0), 0,
        {snap, allowZero: !this.base.hole});
      this.updateSource({radius});
      return;
    }
    const base = this.base.clone();
    base.moveControlHandle(name, destination, options);
    this.updateSource({base: base.toObject()});
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {

    // This implementation is not exact but good enough
    const {destination} = event.interactionData;
    const snap = !event.shiftKey;
    let intersection;
    let radius = 0;
    if ( !this.base.testPoint(destination) ) {
      const points = this.base.polygons[0].points;
      const x0 = points.at(-2);
      const y0 = points.at(-1);
      let p0 = {x: x0, y: y0};
      for ( let i = 0; i < points.length; i += 2 ) {
        const x1 = points[i];
        const y1 = points[i + 1];
        const p1 = {x: x1, y: y1};
        intersection = foundry.utils.lineSegmentIntersection(this.origin, destination, p0, p1);
        if ( intersection ) break;
        p0 = p1;
      }
      if ( intersection ) {
        const dx = destination.x - intersection.x;
        const dy = destination.y - intersection.y;
        const length = Math.hypot(dx, dy);
        const direction = Math.atan2(dy, dx);
        radius = this._calculateSize(length, direction, {snap, allowZero: true});
      }
    }
    this.updateSource({radius});
  }
}

/* -------------------------------------------- */

/**
 * The data model for a polygon shape.
 */
export class PolygonShapeData extends ClientShapeDataMixin(data.PolygonShapeData) {

  /**
   * A shared point instance.
   * @type {PIXI.Point}
   */
  static #SHARED_POINT = new PIXI.Point();

  /* -------------------------------------------- */

  /** @override */
  get hasRotationalSymmetry() {
    return !this.controlHandles.rotate.visible;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    const polygon = new PIXI.Polygon(this.points);
    if ( !polygon.isPositive ) polygon.reverseOrientation();
    return polygon.points;
  }

  /* -------------------------------------------- */

  /** @override */
  _createOrigin() {
    if ( this._source.origin ) return {...this._source.origin};
    return foundry.utils.polygonCentroid(this.points);
  }

  /* -------------------------------------------- */

  /** @override */
  _getSnappedPoint(point) {
    if ( this.grid.isGridless ) return {x: Math.round(point.x), y: Math.round(point.y)};
    const M = CONST.GRID_SNAPPING_MODES;
    return this.grid.getSnappedPoint(point, {
      mode: M.CENTER | M.VERTEX | M.CORNER | M.SIDE_MIDPOINT,
      resolution: this.grid.size >= 128 ? 8 : (this.grid.size >= 64 ? 4 : 2)
    });
  }

  /* -------------------------------------------- */

  /** @override */
  _calculateSize(length, direction, {snap=false, round=!snap, allowZero=false}={}) {
    let size = Math.max(length, 0);
    if ( snap ) {
      let interval;
      if ( this.grid.isGridless ) interval = 1;
      else {
        let precision = this.grid.size >= 128 ? 16 : (this.grid.size >= 64 ? 8 : 4);
        if ( this.grid.isSquare ) {
          const c = Math.abs(Math.cos(direction));
          const s = Math.abs(Math.sin(direction));
          precision *= Math.max(c, s);
        } else {
          if ( this.grid.columns ) direction += (Math.PI / 6);
          const c0 = Math.abs(Math.cos(direction));
          const c1 = Math.abs(Math.cos(direction - (Math.PI / 3)));
          const c2 = Math.abs(Math.cos(direction + (Math.PI / 3)));
          precision *= Math.max(c0, c1, c2);
        }
        interval = this.grid.size / precision;
      }
      size = size.toNearest(interval);
      if ( !allowZero ) size = Math.max(size, interval);
    }
    if ( !allowZero ) size = Math.max(size, 1);
    if ( round || size.almostEqual(Math.round(size)) ) size = Math.round(size);
    return size;
  }

  /* -------------------------------------------- */

  /** @override */
  move(origin, {snap=false}={}) {
    if ( snap ) origin = this._getSnappedPoint(origin);
    const dx = origin.x - this.origin.x;
    const dy = origin.y - this.origin.y;
    const points = this.points.slice();
    for ( let i = 0; i < points.length; i += 2 ) {
      points[i] += dx;
      points[i + 1] += dy;
    }
    const data = {points};
    if ( this._source.origin ) data.origin = {x: origin.x, y: origin.y};
    this.updateSource(data);
  }

  /* -------------------------------------------- */

  /** @override */
  _rotate(angle) {
    const points = this.points.slice();
    const matrix = PIXI.Matrix.TEMP_MATRIX.identity()
      .translate(-this.origin.x, -this.origin.y)
      .rotate(Math.toRadians(angle))
      .translate(this.origin.x, this.origin.y);
    for ( let i = 0; i < points.length; i += 2 ) {
      const point = PolygonShapeData.#SHARED_POINT.set(points[i], points[i + 1]);
      matrix.apply(point, point);
      points[i] = point.x;
      points[i + 1] = point.y;
    }
    this.updateSource({points});
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    return [];
  }

  /* -------------------------------------------- */

  /**
   * Get the target point for scaling and rotation.
   * @returns {Point|null}
   */
  #getTarget() {
    const {x: x0, y: y0} = this.origin;
    for ( let i = 0; i < this.points.length; i += 2 ) {
      const x1 = this.points[i];
      const y1 = this.points[i + 1];
      if ( (x1 !== x0) || (y1 !== y0) ) return {x: x1, y: y1};
    }
    return null;
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const target = this.#getTarget();
    const ray = new Ray(this.origin, target ?? this.origin);
    return {
      translate: {position: ray.A, rotation: ray.angle, visible: true},
      scale: {position: ray.B, rotation: ray.angle, visible: !!target},
      rotate: {position: ray.B, rotation: ray.angle, visible: !!target}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "scale": {
        const points = this.points.slice();
        const {x: x0, y: y0} = this.origin;
        const {x: x1, y: y1} = this.controlHandles.scale.position;
        let dx = x1 - x0;
        const dy = y1 - y0;
        if ( (dx === 0) && (dy === 0) ) dx = 1;
        const d = Math.hypot(dx, dy);
        const a = Math.atan2(dy, dx);
        let size = (((destination.x - x0) * dx) + ((destination.y - y0) * dy)) / d;
        size = this._calculateSize(size, a, {snap});
        const scale = size / d;
        const matrix = PIXI.Matrix.TEMP_MATRIX.identity()
          .translate(-x0, -y0)
          .scale(scale, scale)
          .translate(x0, y0);
        for ( let i = 0; i < points.length; i += 2 ) {
          const point = PolygonShapeData.#SHARED_POINT.set(points[i], points[i + 1]);
          matrix.apply(point, point);
          points[i] = point.x;
          points[i + 1] = point.y;
        }
        this.updateSource({points});
        break;
      }
      case "rotate": this._moveRotationHandle(Math.toDegrees(this.controlHandles.rotate.rotation), destination, snap); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragStart(event) {
    const interaction = event.interactionData;
    let {origin} = interaction;
    let snap = !event.shiftKey;
    if ( interaction.freehand ) {
      interaction.freehandSampleRate ??= 100;
      interaction.freehandDrawTime = Date.now();
      snap = false;
    } else if ( canvas.forceSnapVertices ) {
      origin = this.grid.getSnappedPoint(origin, {mode: CONST.GRID_SNAPPING_MODES.VERTEX});
      snap = false;
    }
    this.move(origin, {snap});
    interaction.origin = this.origin;
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {
    const interaction = event.interactionData;
    let {destination} = interaction;
    const points = this.points.slice();
    if ( interaction.freehand ) {
      const now = Date.now();
      if ( (now - interaction.freehandDrawTime) >= interaction.freehandSampleRate ) {
        interaction.drawTime = now;
        if ( !(destination.x.almostEqual(points.at(-4)) && destination.y.almostEqual(points.at(-3))) ) {
          points.splice(-2, 0, destination.x, destination.y);
        }
      }
    } else if ( canvas.forceSnapVertices ) {
      destination = this.grid.getSnappedPoint(destination, {mode: CONST.GRID_SNAPPING_MODES.VERTEX});
    } else {
      const snap = !event.shiftKey;
      if ( snap ) destination = this._getSnappedPoint(destination);
    }
    points[points.length - 2] = destination.x;
    points[points.length - 1] = destination.y;
    this.updateSource({points});
  }
}

/* -------------------------------------------- */

/**
 * The data model for a token shape.
 */
export class TokenShapeData extends ClientShapeDataMixin(data.TokenShapeData) {

  /** @type {TokenDocument} */
  #token;

  /* -------------------------------------------- */

  /** @type {CircleShapeData|EllipseShapeData|PolygonShapeData} */
  #tokenShape;

  /* -------------------------------------------- */

  /**
   * Get the token.
   * @returns {TokenDocument}
   */
  #getToken() {
    if ( this.#token ) return this.#token;
    const scene = this.scene ?? new Scene.implementation({name: "Default Scene"});
    const {x, y, width, height, shape} = this;
    return this.#token = new TokenDocument.implementation({x, y, width, height, shape}, {parent: scene});
  }

  /* -------------------------------------------- */

  /**
   * Get the token shape.
   * @type {CircleShapeData|EllipseShapeData|PolygonShapeData}
   * @internal
   */
  _getTokenShape() {
    if ( this.#tokenShape ) return this.#tokenShape;
    const token = this.#getToken();
    if ( token.parent.grid.isGridless ) {
      const {width, height} = token.getSize();
      const shape = token.shape;
      if ( (shape === TOKEN_SHAPES.ELLIPSE_1) || (shape === TOKEN_SHAPES.ELLIPSE_2) ) {
        if ( width === height ) {
          const radius = width / 2;
          this.#tokenShape = new CircleShapeData({x: token.x + radius, y: token.y + radius, radius, hole: this.hole},
            {parent: token.parent});
        } else {
          const radiusX = width / 2;
          const radiusY = height / 2;
          this.#tokenShape = new EllipseShapeData({x: token.x + radiusX, y: token.y + radiusY, radiusX, radiusY,
            hole: this.hole}, {parent: token.parent});
        }
      } else {
        const halfWidth = width / 2;
        const halfHeight = height / 2;
        this.#tokenShape = new RectangleShapeData({x: token.x + halfWidth, y: token.y + halfHeight, width, height,
          anchorX: 0.5, anchorY: 0.5, hole: this.hole}, {parent: token.parent});
      }
    } else if ( token.parent.grid.isSquare ) {
      const {width, height} = token.getSize();
      const halfWidth = width / 2;
      const halfHeight = height / 2;
      this.#tokenShape = new RectangleShapeData({x: token.x + halfWidth, y: token.y + halfHeight, width, height,
        anchorX: 0.5, anchorY: 0.5, hole: this.hole}, {parent: token.parent});
    } else {
      const points = [];
      for ( const {x, y} of token.getGridSpacePolygon() ) {
        points.push(token.x + x, token.y + y);
      }
      this.#tokenShape = new PolygonShapeData({points, hole: this.hole}, {parent: token.parent});
    }
    return this.#tokenShape;
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    return false;
  }

  /* -------------------------------------------- */

  /** @override */
  get polygonTree() {
    return this._getTokenShape().polygonTree;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleInterior(out) {
    return this._getTokenShape().sampleInterior(out);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  sampleBoundary(out) {
    return this._getTokenShape().sampleBoundary(out);
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#token = undefined;
    this.#tokenShape = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  get isAffectedByGrid() {
    return true;
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    return this._getTokenShape().clipperPolyTree;
  }

  /* -------------------------------------------- */

  /** @override */
  _createOrigin() {
    const {x, y} = this.#getToken().getCenterPoint();
    return {x, y};
  }

  /* -------------------------------------------- */

  /** @override */
  move(origin, {snap=false}={}) {
    const token = this.#getToken();
    const pivot = token.getCenterPoint({x: 0, y: 0});
    const position = {x: origin.x - pivot.x, y: origin.y - pivot.y};
    const {x, y} = snap ? token.getSnappedPosition(position) : position;
    this.updateSource({x, y});
  }

  /* -------------------------------------------- */

  /** @override */
  _rotate(angle) {}

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    return [];
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    return {translate: {position: this.origin, rotation: 0, visible: true}};
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {}
}

/* -------------------------------------------- */

/**
 * The data model for a shape that is the union of grid spaces.
 */
export class GridShapeData extends ClientShapeDataMixin(data.GridShapeData) {

  /** @type {Set<string>} */
  #offsetKeys;

  /* -------------------------------------------- */

  /**
   * Get the offset keys.
   * @returns {Set<string>}
   */
  #getOffsetKeys() {
    if ( !this.#offsetKeys ) {
      this.#offsetKeys = new Set();
      for ( const {i, j} of this.offsets ) this.#offsetKeys.add(`${i}.${j}`);
    }
    return this.#offsetKeys;
  }

  /* -------------------------------------------- */

  /** @override */
  get isEmpty() {
    return !this.offsets.length || this.grid.isGridless;
  }

  /* -------------------------------------------- */

  /** @override */
  get isAffectedByGrid() {
    return true;
  }

  /* -------------------------------------------- */

  /** @override */
  get hasRotationalSymmetry() {
    return !this.controlHandles.rotate.visible;
  }

  /* -------------------------------------------- */

  /** @inheritDoc */
  _onShapeChange() {
    super._onShapeChange();
    this.#offsetKeys = undefined;
  }

  /* -------------------------------------------- */

  /** @override */
  testPoint(point) {
    const {i, j} = this.grid.getOffset(point);
    return this.#getOffsetKeys().has(`${i}.${j}`);
  }

  /* -------------------------------------------- */

  /** @override */
  _createClipperPolyTree() {
    if ( this.isEmpty ) return new ClipperLib.PolyTree();
    if ( this.offsets.length === 1 ) return this.grid.getVertices(this.offsets[0]);

    // Clipper handles collinear edges so badly we have to scale the grid space shapes slightly (1 Clipper pixel)
    // to eliminate them. If we didn't do this, the performance would be abysmal.
    const scale = 1 + (2 / (CLIPPER_SCALING_FACTOR * Math.max(this.grid.sizeX, this.grid.sizeY)));
    const vertices = this.grid.getShape();
    for ( const vertex of vertices ) {
      vertex.x *= scale;
      vertex.y *= scale;
    }
    const clipper = new ClipperLib.Clipper();
    for ( const offset of this.offsets ) {
      const center = this.grid.getCenterPoint(offset);
      const path = [];
      for ( const vertex of vertices ) {
        path.push({
          X: Math.round((center.x + vertex.x) * CLIPPER_SCALING_FACTOR),
          Y: Math.round((center.y + vertex.y) * CLIPPER_SCALING_FACTOR)
        });
      }
      clipper.AddPath(path, ClipperLib.PolyType.ptSubject, true);
    }
    const solution = new ClipperLib.PolyTree();
    clipper.Execute(ClipperLib.ClipType.ctUnion, solution, ClipperLib.PolyFillType.pftPositive,
      ClipperLib.PolyFillType.pftEvenOdd);
    return solution;
  }

  /* -------------------------------------------- */

  /** @override */
  _createOrigin() {
    if ( this._source.origin ) return {...this._source.origin};
    if ( this.isEmpty ) return {x: 0, y: 0};
    return this.grid.getCenterPoint(this.offsets[0]);
  }

  /* -------------------------------------------- */

  /** @override */
  move(origin, {snap=false}={}) {
    const from = this.grid.getOffset(this.origin);
    const to = this.grid.getOffset(origin);
    if ( snap ) origin = this.grid.getCenterPoint(to);
    const offsets = [];
    if ( !this.grid.isHexagonal ) {
      const di = to.i - from.i;
      const dj = to.j - from.j;
      for ( const offset of this.offsets ) offsets.push({i: offset.i + di, j: offset.j + dj});
    } else {
      const a = this.grid.getCube(from);
      const b = this.grid.getCube(to);
      const dq = b.q - a.q;
      const dr = b.r - a.r;
      const ds = b.s - a.s;
      for ( const offset of this.offsets ) {
        const cube = this.grid.getCube(offset);
        cube.q += dq;
        cube.r += dr;
        cube.s += ds;
        offsets.push(this.grid.getOffset(cube));
      }
    }
    const data = {offsets};
    if ( this._source.origin ) data.origin = {x: origin.x, y: origin.y};
    this.updateSource(data);
  }

  /* -------------------------------------------- */

  /**
   * @override
   * @see {@link https://www.redblobgames.com/grids/hexagons/implementation.html#rotation}
   */
  _rotate(angle) {
    if ( this.grid.isEmpty ) return;
    const offsets = [];
    if ( this.grid.isSquare ) {
      const origin = this.grid.getOffset(this.origin);
      angle = Math.toRadians(angle.toNearest(90));
      const cos = Math.round(Math.cos(angle));
      const sin = Math.round(Math.sin(angle));
      for ( const offset of this.offsets ) {
        const di = offset.i - origin.i;
        const dj = offset.j - origin.j;
        offsets.push({
          i: (sin * dj) + (cos * di) + origin.i,
          j: (cos * dj) - (sin * di) + origin.j
        });
      }
    } else {
      const origin = this.grid.getCube(this.grid.getOffset(this.origin));
      const n = Math.normalizeDegrees(angle.toNearest(60)) / 60;
      for ( const offset of this.offsets ) {
        const cube = this.grid.getCube(offset);
        cube.q -= origin.q;
        cube.r -= origin.r;
        cube.s -= origin.s;
        for ( let i = 0; i < n; i++ ) [cube.q, cube.r, cube.s] = [-cube.r, -cube.s, -cube.q];
        cube.q += origin.q;
        cube.r += origin.r;
        cube.s += origin.s;
        offsets.push(this.grid.getOffset(cube));
      }
    }
    this.updateSource({offsets});
  }

  /* -------------------------------------------- */

  /** @override */
  _createMeasuredSegments() {
    return [];
  }

  /* -------------------------------------------- */

  /**
   * Get the rotation of the shape, if any.
   * @returns {number|void}
   */
  #getDirection() {
    const origin = this.grid.getOffset(this.origin);
    for ( const offset of this.offsets ) {
      if ( (offset.i !== origin.i) || (offset.j !== origin.j) ) {
        return new Ray(this.grid.getCenterPoint(origin), this.grid.getCenterPoint(offset)).angle;
      }
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _createControlHandles() {
    const direction = this.#getDirection();
    return {
      translate: {position: this.origin, rotation: direction ?? 0, visible: true},
      rotate: {position: this.origin, rotation: direction ?? 0, visible: direction !== undefined}
    };
  }

  /* -------------------------------------------- */

  /** @override */
  moveControlHandle(name, destination, {snap=false}={}) {
    switch ( name ) {
      case "translate": this.move(destination, {snap}); break;
      case "rotate": this._moveRotationHandle(Math.toDegrees(this.controlHandles.rotate.rotation), destination, snap); break;
      default: throw new Error("Invalid handle");
    }
  }

  /* -------------------------------------------- */

  /** @override */
  _onDragMove(event) {}
}

/* -------------------------------------------- */

/**
 * Sample a point from a rectangle interior.
 * @param {Point} [out]  A point to write to.
 * @param {number} x     The x-coordinate of the rectangle corner.
 * @param {number} y     The y-coordinate of the rectangle corner.
 * @param {Ray} axisX    The rectangle width axis.
 * @param {Ray} axisY    The rectangle height axis.
 * @returns {Point}
 * @throws {Error} If the rectangle is empty.
 */
function sampleRectangleInterior(out, x, y, axisX, axisY) {
  const width = axisX.distance;
  const height = axisY.distance;
  if ( (width <= 0) || (height <= 0) ) throw new Error("Cannot sample an empty shape.");
  const point = out ?? {x: 0, y: 0};
  const s = Math.random();
  const t = Math.random();
  point.x = x + (axisX.dx * s) + (axisY.dx * t);
  point.y = y + (axisX.dy * s) + (axisY.dy * t);
  return point;
}

/* -------------------------------------------- */

/**
 * Sample a point from a rectangle boundary.
 * @param {Point} [out]  A point to write to.
 * @param {number} x     The x-coordinate of the rectangle corner.
 * @param {number} y     The y-coordinate of the rectangle corner.
 * @param {Ray} axisX    The rectangle width axis.
 * @param {Ray} axisY    The rectangle height axis.
 * @returns {Point}
 * @throws {Error} If the rectangle is empty.
 */
function sampleRectangleBoundary(out, x, y, axisX, axisY) {
  const width = axisX.distance;
  const height = axisY.distance;
  if ( (width <= 0) || (height <= 0) ) throw new Error("Cannot sample an empty shape.");
  const point = out ?? {x: 0, y: 0};
  let d = Math.random() * (2 * (width + height));
  if ( d < width ) {
    const t = d / width;
    point.x = x + (axisX.dx * t);
    point.y = y + (axisX.dy * t);
    return point;
  }

  d -= width;
  if ( d < height ) {
    const t = d / height;
    point.x = x + axisX.dx + (axisY.dx * t);
    point.y = y + axisX.dy + (axisY.dy * t);
    return point;
  }

  d -= height;
  if ( d < width ) {
    const t = d / width;
    point.x = x + axisX.dx + axisY.dx - (axisX.dx * t);
    point.y = y + axisX.dy + axisY.dy - (axisX.dy * t);
    return point;
  }

  d -= width;
  const t = d / height;
  point.x = x + axisY.dx - (axisY.dx * t);
  point.y = y + axisY.dy - (axisY.dy * t);
  return point;
}
