{"version":3,"file":"index.d.ts","sources":["../src/interfaces.ts","../src/model/Rectangle.ts","../src/model/Area.ts","../src/model/Line.ts","../src/PointPath.ts","../src/BubbleSets.ts","../src/padding.ts","../src/model/Circle.ts","../src/potentialAreas.ts","../src/routing.ts"],"sourcesContent":["export declare type IPoint = { x: number; y: number };\n\nexport interface ICenterPoint {\n  cx: number;\n  cy: number;\n}\n\nexport interface IRectangle extends IPoint {\n  width: number;\n  height: number;\n}\n\nexport interface IRectangle2 extends IRectangle {\n  x2: number;\n  y2: number;\n}\n\nexport interface ILine {\n  x1: number;\n  y1: number;\n  x2: number;\n  y2: number;\n}\n\nexport interface ICircle extends ICenterPoint {\n  radius: number;\n}\n\nexport function rect(x: number, y: number, width: number, height: number): IRectangle {\n  return { x, y, width, height };\n}\n\nexport function circle(cx: number, cy: number, radius: number): ICircle {\n  return { cx, cy, radius };\n}\n\nexport function line(x1: number, y1: number, x2: number, y2: number): ILine {\n  return { x1, y1, x2, y2 };\n}\n\nexport function point(x: number, y: number) {\n  return { x, y };\n}\n","import type { IPoint, IRectangle, IRectangle2, ICircle } from '../interfaces';\nimport { ptsDistanceSq } from '../utils';\nimport { outcode, OutCode } from '../Intersection';\n\nexport class Rectangle implements IRectangle2, ICircle {\n  constructor(\n    public x: number,\n    public y: number,\n    public width: number,\n    public height: number\n  ) {}\n\n  get x2() {\n    return this.x + this.width;\n  }\n\n  get y2() {\n    return this.y + this.height;\n  }\n\n  get cx() {\n    return this.x + this.width / 2;\n  }\n\n  get cy() {\n    return this.y + this.height / 2;\n  }\n\n  get radius() {\n    return Math.max(this.width, this.height) / 2;\n  }\n\n  static from(r: IRectangle) {\n    return new Rectangle(r.x, r.y, r.width, r.height);\n  }\n\n  equals(that: IRectangle) {\n    return this.x === that.x && this.y === that.y && this.width === that.width && this.height === that.height;\n  }\n\n  clone() {\n    return new Rectangle(this.x, this.y, this.width, this.height);\n  }\n\n  add(that: IRectangle) {\n    const x = Math.min(this.x, that.x);\n    const y = Math.min(this.y, that.y);\n    const x2 = Math.max(this.x2, that.x + that.width);\n    const y2 = Math.max(this.y2, that.y + that.height);\n    this.x = x;\n    this.y = y;\n    this.width = x2 - x;\n    this.height = y2 - y;\n  }\n\n  addPoint(p: IPoint) {\n    const x = Math.min(this.x, p.x);\n    const y = Math.min(this.y, p.y);\n    const x2 = Math.max(this.x2, p.x);\n    const y2 = Math.max(this.y2, p.y);\n    this.x = x;\n    this.y = y;\n    this.width = x2 - x;\n    this.height = y2 - y;\n  }\n\n  toString() {\n    return `Rectangle[x=${this.x}, y=${this.y}, w=${this.width}, h=${this.height}]`;\n  }\n\n  draw(ctx: CanvasRenderingContext2D) {\n    ctx.rect(this.x, this.y, this.width, this.height);\n  }\n\n  containsPt(px: number, py: number) {\n    return px >= this.x && px <= this.x2 && py >= this.y && py <= this.y2;\n  }\n\n  get area() {\n    return this.width * this.height;\n  }\n\n  intersects(that: IRectangle) {\n    if (this.area <= 0 || that.width <= 0 || that.height <= 0) {\n      return false;\n    }\n    return that.x + that.width > this.x && that.y + that.height > this.y && that.x < this.x2 && that.y < this.y2;\n  }\n\n  distSquare(tempX: number, tempY: number) {\n    // test current point to see if it is inside rectangle\n    if (this.containsPt(tempX, tempY)) {\n      return 0;\n    }\n    // which edge of rectangle is closest\n    const code = outcode(this, tempX, tempY);\n    // top\n    if (code.has(OutCode.TOP)) {\n      // and left\n      if (code.has(OutCode.LEFT)) {\n        // linear distance from upper left corner\n        return ptsDistanceSq(tempX, tempY, this.x, this.y);\n      }\n      if (code.has(OutCode.RIGHT)) {\n        // and right\n        // linear distance from upper right corner\n        return ptsDistanceSq(tempX, tempY, this.x2, this.y);\n      }\n      // distance from top line segment\n      return (this.y - tempY) * (this.y - tempY);\n    }\n    // bottom\n    if (code.has(OutCode.BOTTOM)) {\n      // and left\n      if (code.has(OutCode.LEFT)) {\n        // linear distance from lower left corner\n        return ptsDistanceSq(tempX, tempY, this.x, this.y2);\n      }\n      // and right\n      if (code.has(OutCode.RIGHT)) {\n        // linear distance from lower right corner\n        return ptsDistanceSq(tempX, tempY, this.x2, this.y2);\n      }\n      // distance from bottom line segment\n      return (tempY - this.y2) * (tempY - this.y2);\n    }\n    // left only\n    if (code.has(OutCode.LEFT)) {\n      // linear distance from left edge\n      return (this.x - tempX) * (this.x - tempX);\n    }\n    // right only\n    if (code.has(OutCode.RIGHT)) {\n      // linear distance from right edge\n      return (tempX - this.x2) * (tempX - this.x2);\n    }\n    return 0;\n  }\n}\n\nexport function boundingBox(path: ReadonlyArray<IPoint>) {\n  if (path.length === 0) {\n    return null;\n  }\n  const first = path[0];\n  const bb = new Rectangle(first.x, first.y, 0, 0);\n  for (const point of path) {\n    bb.addPoint(point);\n  }\n  return bb;\n}\n","import type { IRectangle, IPoint } from '../interfaces';\nimport { Rectangle } from './Rectangle';\n\nexport class Area {\n  private readonly area: Float32Array;\n\n  constructor(\n    public readonly pixelGroup: number,\n    public readonly i = 0,\n    public readonly j = 0,\n    public readonly pixelX = 0,\n    public readonly pixelY = 0,\n    public readonly width: number = 10,\n    public readonly height: number = 10,\n    pixels: Float32Array = new Float32Array(Math.max(0, width * height)).fill(0)\n  ) {\n    this.area = pixels;\n  }\n\n  createSub(rect: IRectangle, pixelPos: IPoint) {\n    return new Area(this.pixelGroup, rect.x, rect.y, pixelPos.x, pixelPos.y, rect.width, rect.height);\n  }\n\n  static fromPixelRegion(pixelRect: IRectangle, pixelGroup: number) {\n    return new Area(\n      pixelGroup,\n      0,\n      0,\n      pixelRect.x,\n      pixelRect.y,\n      Math.ceil(pixelRect.width / pixelGroup),\n      Math.ceil(pixelRect.height / pixelGroup)\n    );\n  }\n\n  copy(sub: Area, pixelPoint: IPoint) {\n    return new Area(\n      this.pixelGroup,\n      this.scaleX(pixelPoint.x),\n      this.scaleY(pixelPoint.y),\n      pixelPoint.x,\n      pixelPoint.y,\n      sub.width,\n      sub.height,\n      sub.area\n    );\n  }\n\n  boundX(pos: number) {\n    if (pos < this.i) {\n      return this.i;\n    }\n    if (pos >= this.width) {\n      return this.width - 1;\n    }\n    return pos;\n  }\n\n  boundY(pos: number) {\n    if (pos < this.j) {\n      return this.j;\n    }\n    if (pos >= this.height) {\n      return this.height - 1;\n    }\n    return pos;\n  }\n\n  scaleX(pixel: number) {\n    return this.boundX(Math.floor((pixel - this.pixelX) / this.pixelGroup));\n  }\n\n  scaleY(pixel: number) {\n    return this.boundY(Math.floor((pixel - this.pixelY) / this.pixelGroup));\n  }\n\n  scale(pixelRect: IRectangle) {\n    const x = this.scaleX(pixelRect.x);\n    const y = this.scaleY(pixelRect.y);\n    const x2 = this.boundX(Math.ceil((pixelRect.x + pixelRect.width - this.pixelX) / this.pixelGroup));\n    const y2 = this.boundY(Math.ceil((pixelRect.y + pixelRect.height - this.pixelY) / this.pixelGroup));\n    const width = x2 - x;\n    const height = y2 - y;\n    return new Rectangle(x, y, width, height);\n  }\n\n  invertScaleX(v: number) {\n    return Math.round(v * this.pixelGroup + this.pixelX);\n  }\n\n  invertScaleY(v: number) {\n    return Math.round(v * this.pixelGroup + this.pixelY);\n  }\n\n  addPadding(rect: Rectangle, pixelPadding: number) {\n    const padding = Math.ceil(pixelPadding / this.pixelGroup);\n    const x = this.boundX(rect.x - padding);\n    const y = this.boundY(rect.y - padding);\n    const x2 = this.boundX(rect.x2 + padding);\n    const y2 = this.boundY(rect.y2 + padding);\n    const width = x2 - x;\n    const height = y2 - y;\n    return new Rectangle(x, y, width, height);\n  }\n\n  get(i: number, j: number) {\n    if (i < 0 || j < 0 || i >= this.width || j >= this.height) {\n      return Number.NaN;\n    }\n    return this.area[i + j * this.width];\n  }\n\n  inc(i: number, j: number, v: number) {\n    if (i < 0 || j < 0 || i >= this.width || j >= this.height) {\n      return;\n    }\n    this.area[i + j * this.width] += v;\n  }\n\n  set(i: number, j: number, v: number) {\n    if (i < 0 || j < 0 || i >= this.width || j >= this.height) {\n      return;\n    }\n    this.area[i + j * this.width] = v;\n  }\n\n  incArea(sub: Area, factor: number) {\n    if (sub.width <= 0 || sub.height <= 0 || factor === 0) {\n      return;\n    }\n    // assume it is within the bounds\n    const w = this.width;\n    const aw = sub.width;\n    const i1 = Math.max(0, sub.i);\n    const j1 = Math.max(0, sub.j);\n    const i2 = Math.min(sub.i + sub.width, w);\n    const j2 = Math.min(sub.j + sub.height, this.height);\n\n    if (j2 <= 0 || i2 <= 0 || i1 >= w || j2 >= this.height) {\n      return;\n    }\n\n    for (let j = j1; j < j2; j++) {\n      const subRow = (j - sub.j) * aw;\n      const row = j * w;\n      for (let i = i1; i < i2; i++) {\n        const v = sub.area[i - sub.i + subRow];\n        if (v === 0) {\n          continue;\n        }\n        this.area[i + row] += factor * v;\n      }\n    }\n  }\n\n  fill(value: number) {\n    this.area.fill(value);\n  }\n\n  fillArea(rect: IRectangle, value: number) {\n    const offset = rect.x + rect.y * this.width;\n    for (let j = 0; j < rect.height; j++) {\n      const pos = offset + j * this.width;\n      this.area.fill(value, pos, pos + rect.width);\n    }\n  }\n\n  fillHorizontalLine(i: number, j: number, width: number, value: number) {\n    const offset = i + j * this.width;\n    this.area.fill(value, offset, offset + width);\n  }\n\n  fillVerticalLine(i: number, j: number, height: number, value: number) {\n    const offset = i + j * this.width;\n    for (let k = 0; k < height; k++) {\n      this.area[offset + k * this.width] = value;\n    }\n  }\n\n  clear() {\n    this.area.fill(0);\n  }\n\n  toString() {\n    let r = '';\n    for (let j = 0; j < this.height; j++) {\n      const row = j * this.width;\n      for (let i = 0; i < this.width; i++) {\n        const v = this.area[row + i];\n        r += v.toFixed(1).padStart(6);\n        r += ' ';\n      }\n      r += '\\n';\n    }\n    return r;\n  }\n\n  draw(ctx: CanvasRenderingContext2D, offset = true) {\n    if (this.width <= 0 || this.height <= 0) {\n      return;\n    }\n    ctx.save();\n    if (offset) {\n      ctx.translate(this.pixelX, this.pixelY);\n    }\n    const min = this.area.reduce((acc, v) => Math.min(acc, v), Number.POSITIVE_INFINITY);\n    const max = this.area.reduce((acc, v) => Math.max(acc, v), Number.NEGATIVE_INFINITY);\n\n    const scale = (v: number) => (v - min) / (max - min);\n    ctx.scale(this.pixelGroup, this.pixelGroup);\n    for (let i = 0; i < this.width; i++) {\n      for (let j = 0; j < this.height; j++) {\n        const v = this.area[i + j * this.width];\n        ctx.fillStyle = `rgba(0, 0, 0, ${scale(v)})`;\n        ctx.fillRect(i, j, 1, 1);\n      }\n    }\n    ctx.restore();\n  }\n\n  drawThreshold(ctx: CanvasRenderingContext2D, threshold: number, offset = true) {\n    if (this.width <= 0 || this.height <= 0) {\n      return;\n    }\n    ctx.save();\n    if (offset) {\n      ctx.translate(this.pixelX, this.pixelY);\n    }\n    ctx.scale(this.pixelGroup, this.pixelGroup);\n    for (let i = 0; i < this.width; i++) {\n      for (let j = 0; j < this.height; j++) {\n        const v = this.area[i + j * this.width];\n        ctx.fillStyle = v > threshold ? 'black' : 'white';\n        ctx.fillRect(i, j, 1, 1);\n      }\n    }\n    ctx.restore();\n  }\n}\n","import { linePtSegDistSq } from '../utils';\nimport type { ILine, IRectangle2 } from '../interfaces';\n\nexport function lineBoundingBox(line: ILine): IRectangle2 {\n  const minX = Math.min(line.x1, line.x2);\n  const maxX = Math.max(line.x1, line.x2);\n  const minY = Math.min(line.y1, line.y2);\n  const maxY = Math.max(line.y1, line.y2);\n\n  return {\n    x: minX,\n    y: minY,\n    x2: maxX,\n    y2: maxY,\n    width: maxX - minX,\n    height: maxY - minY,\n  };\n}\n\nexport class Line {\n  constructor(\n    public x1: number,\n    public y1: number,\n    public x2: number,\n    public y2: number\n  ) {}\n\n  equals(that: ILine) {\n    return this.x1 === that.x1 && this.y1 === that.y1 && this.x2 === that.x2 && this.y2 === that.y2;\n  }\n\n  draw(ctx: CanvasRenderingContext2D) {\n    ctx.moveTo(this.x1, this.y1);\n    ctx.lineTo(this.x2, this.y2);\n  }\n\n  toString() {\n    return `Line(from=(${this.x1},${this.y1}),to=(${this.x2},${this.y2}))`;\n  }\n\n  static from(l: { x1: number; y1: number; x2: number; y2: number }) {\n    return new Line(l.x1, l.y1, l.x2, l.y2);\n  }\n\n  // whether an infinite line to positive x from the point p will cut through the line\n  cuts(px: number, py: number) {\n    if (this.y1 === this.y2) {\n      return false;\n    }\n    if ((py < this.y1 && py <= this.y2) || (py > this.y1 && py >= this.y2)) {\n      return false;\n    }\n    if (px > this.x1 && px >= this.x2) {\n      return false;\n    }\n    if (px < this.x1 && px <= this.x2) {\n      return true;\n    }\n    const cross = this.x1 + ((py - this.y1) * (this.x2 - this.x1)) / (this.y2 - this.y1);\n    return px <= cross;\n  }\n\n  distSquare(x: number, y: number) {\n    return linePtSegDistSq(this.x1, this.y1, this.x2, this.y2, x, y);\n  }\n\n  ptClose(x: number, y: number, r: number) {\n    // check whether the point is outside the bounding rectangle with padding r\n    if (this.x1 < this.x2) {\n      if (x < this.x1 - r || x > this.x2 + r) {\n        return false;\n      }\n    } else {\n      if (x < this.x2 - r || x > this.x1 + r) {\n        return false;\n      }\n    }\n    if (this.y1 < this.y2) {\n      if (y < this.y1 - r || y > this.y2 + r) {\n        return false;\n      }\n    } else {\n      if (y < this.y2 - r || y > this.y1 + r) {\n        return false;\n      }\n    }\n    return true;\n  }\n}\n","import { shapeSimplifier, bSplineShapeGenerator, samplePath } from './simplifiers';\nimport { Line, boundingBox } from './model';\nimport type { IPoint, ICenterPoint } from './interfaces';\nimport { round } from './utils';\n\nexport class PointPath {\n  readonly points: ReadonlyArray<IPoint>;\n\n  readonly closed: boolean;\n\n  constructor(points: ReadonlyArray<IPoint> = [], closed = true) {\n    this.points = points;\n    this.closed = closed;\n  }\n\n  get(index: number): IPoint {\n    const i = index;\n    const l = this.points.length;\n    if (index < 0) {\n      return this.closed ? this.get(index + l) : this.points[0];\n    } else if (index >= l) {\n      return this.closed ? this.get(index - l) : this.points[l - 1];\n    }\n    return this.points[i];\n  }\n\n  get length() {\n    return this.points.length;\n  }\n\n  toString(roundToDigits: number | ((v: number) => number) = Infinity) {\n    const points = this.points;\n    if (points.length === 0) {\n      return '';\n    }\n    const rounder = typeof roundToDigits === 'function' ? roundToDigits : round(roundToDigits);\n    let r = 'M';\n    for (const p of points) {\n      r += `${rounder(p.x)},${rounder(p.y)} L`;\n    }\n    r = r.slice(0, -1);\n    if (this.closed) {\n      r += ' Z';\n    }\n    return r;\n  }\n\n  draw(ctx: CanvasRenderingContext2D) {\n    const points = this.points;\n    if (points.length === 0) {\n      return;\n    }\n    ctx.beginPath();\n\n    ctx.moveTo(points[0].x, points[0].y);\n\n    for (const p of points) {\n      ctx.lineTo(p.x, p.y);\n    }\n\n    if (this.closed) {\n      ctx.closePath();\n    }\n  }\n\n  sample(skip?: number) {\n    return samplePath(skip)(this);\n  }\n\n  simplify(tolerance?: number) {\n    return shapeSimplifier(tolerance)(this);\n  }\n\n  bSplines(granularity?: number) {\n    return bSplineShapeGenerator(granularity)(this);\n  }\n\n  apply(transformer: (path: PointPath) => PointPath) {\n    return transformer(this);\n  }\n\n  containsElements(members: ReadonlyArray<ICenterPoint>) {\n    const bb = boundingBox(this.points);\n    if (!bb) {\n      return false;\n    }\n    return members.every((member) => {\n      return bb.containsPt(member.cx, member.cy) && this.withinArea(member.cx, member.cy);\n    });\n  }\n\n  withinArea(px: number, py: number) {\n    if (this.length === 0) {\n      return false;\n    }\n    let crossings = 0;\n    const first = this.points[0]!;\n    const line = new Line(first.x, first.y, first.x, first.y);\n\n    for (let i = 1; i < this.points.length; i++) {\n      const cur = this.points[i];\n      line.x1 = line.x2;\n      line.y1 = line.y2;\n      line.x2 = cur.x;\n      line.y2 = cur.y;\n\n      if (line.cuts(px, py)) {\n        crossings++;\n      }\n    }\n    // close to start\n    line.x1 = line.x2;\n    line.y1 = line.y2;\n    line.x2 = first.x;\n    line.y2 = first.y;\n\n    if (line.cuts(px, py)) {\n      crossings++;\n    }\n\n    return crossings % 2 === 1;\n  }\n}\n","import type { ICircle, ILine, IRectangle } from './interfaces';\nimport { createGenericInfluenceArea, createLineInfluenceArea, createRectangleInfluenceArea } from './potentialAreas';\nimport { calculateVirtualEdges } from './routing';\nimport { Circle } from './model';\nimport { Area } from './model/Area';\nimport { Line, lineBoundingBox } from './model/Line';\nimport { marchingSquares } from './MarchingSquares';\nimport { Rectangle } from './model/Rectangle';\nimport { addPadding } from './padding';\nimport { PointPath } from './PointPath';\n\nexport interface IPotentialOptions {\n  /**\n   * the resolution of the algorithm in square pixels\n   * @default 4\n   */\n  pixelGroup?: number;\n  /**\n   * the amount of space to move the virtual edge when wrapping around obstacles\n   * @default 10\n   */\n  morphBuffer?: number;\n}\n\nexport interface IRoutingOptions {\n  virtualEdges?: boolean;\n  /**\n   *  number of times to run the algorithm to refine the path finding in difficult areas\n   * @default 100\n   */\n  maxRoutingIterations?: number;\n  /**\n   * the amount of space to move the virtual edge when wrapping around obstacles\n   * @default 10\n   */\n  morphBuffer?: number;\n}\nexport interface IOutlineOptions {\n  /**\n   * number of times to refine the boundary\n   * @default 20\n   */\n  maxMarchingIterations?: number;\n  /**\n   * the distance from edges at which energy is 1 (full influence)\n   * @default 10\n   */\n  edgeR0?: number;\n  /**\n   * the distance from edges at which energy is 0 (no influence)\n   * @default 20\n   */\n  edgeR1?: number;\n  /**\n   * the distance from nodes which energy is 1 (full influence)\n   * @default 15\n   */\n  nodeR0?: number;\n  /**\n   * the distance from nodes at which energy is 0 (no influence)\n   * @default 50\n   */\n  nodeR1?: number;\n\n  threshold?: number;\n  memberInfluenceFactor?: number;\n  edgeInfluenceFactor?: number;\n  nonMemberInfluenceFactor?: number;\n}\n\nexport interface IBubbleSetOptions extends IRoutingOptions, IOutlineOptions, IPotentialOptions {}\n\nexport const defaultOptions: Readonly<Required<IBubbleSetOptions>> = {\n  // override these defaults to change the spacing and bubble precision; affects performance and appearance\n  maxRoutingIterations: 100, // number of times to run the algorithm to refine the path finding in difficult areas\n  maxMarchingIterations: 20, // number of times to refine the boundary\n  pixelGroup: 4, // the resolution of the algorithm in square pixels\n  edgeR0: 10, // the distance from edges at which energy is 1 (full influence)\n  edgeR1: 20, // the distance from edges at which energy is 0 (no influence)\n  nodeR0: 15, // the distance from nodes which energy is 1 (full influence)\n  nodeR1: 50, // the distance from nodes at which energy is 0 (no influence)\n  morphBuffer: 10, // the amount of space to move the virtual edge when wrapping around obstacles\n\n  threshold: 1,\n  memberInfluenceFactor: 1,\n  edgeInfluenceFactor: 1,\n  nonMemberInfluenceFactor: -0.8,\n\n  virtualEdges: true,\n};\n\nfunction isCircle(v: IRectangle | ICircle): v is ICircle {\n  return v != null && typeof (v as ICircle).radius === 'number';\n}\n\nfunction isEqual(a: IRectangle | ICircle, b: IRectangle | ICircle) {\n  if (isCircle(a) !== isCircle(b)) {\n    return false;\n  }\n  if (isCircle(a)) {\n    const bc = b as ICircle;\n    return a.cx === bc.cx && a.cy === bc.cy && a.radius === bc.radius;\n  }\n  const br = b as IRectangle;\n  return a.x === br.x && a.y === br.y && a.width === br.width && a.height === br.height;\n}\n\nenum EDirty {\n  MEMBERS,\n  NON_MEMBERS,\n  EDGES,\n}\n\ninterface IMember {\n  readonly raw: IRectangle | ICircle;\n  obj: Rectangle | Circle;\n  area: Area | null;\n}\n\ninterface IEdge {\n  readonly raw: ILine;\n  obj: Line;\n  area: Area | null;\n}\n\nexport class BubbleSets {\n  private readonly dirty = new Set<EDirty>();\n\n  private readonly o: Required<IBubbleSetOptions>;\n\n  private readonly members: IMember[] = [];\n\n  private readonly nonMembers: IMember[] = [];\n\n  private virtualEdges: IEdge[] = [];\n\n  private readonly edges: IEdge[] = [];\n\n  private activeRegion = new Rectangle(0, 0, 0, 0);\n\n  private potentialArea = new Area(1, 0, 0, 0, 0, 0, 0);\n\n  constructor(options: IBubbleSetOptions = {}) {\n    this.o = Object.assign({}, defaultOptions, options);\n  }\n\n  pushMember(...members: ReadonlyArray<IRectangle | ICircle>) {\n    if (members.length === 0) {\n      return;\n    }\n    this.dirty.add(EDirty.MEMBERS);\n    for (const v of members) {\n      this.members.push({\n        raw: v,\n        obj: isCircle(v) ? Circle.from(v) : Rectangle.from(v),\n        area: null,\n      });\n    }\n  }\n\n  removeMember(member: IRectangle | ICircle) {\n    const index = this.members.findIndex((d) => isEqual(d.raw, member));\n    if (index < 0) {\n      return false;\n    }\n    this.members.splice(index, 1);\n    this.dirty.add(EDirty.MEMBERS);\n    return true;\n  }\n\n  removeNonMember(nonMember: IRectangle | ICircle) {\n    const index = this.nonMembers.findIndex((d) => isEqual(d.raw, nonMember));\n    if (index < 0) {\n      return false;\n    }\n    this.nonMembers.splice(index, 1);\n    this.dirty.add(EDirty.NON_MEMBERS);\n    return true;\n  }\n\n  removeEdge(edge: ILine) {\n    const index = this.edges.findIndex((d) => d.obj.equals(edge));\n    if (index < 0) {\n      return false;\n    }\n    this.edges.splice(index, 1);\n    this.dirty.add(EDirty.NON_MEMBERS);\n    return true;\n  }\n\n  pushNonMember(...nonMembers: ReadonlyArray<IRectangle | ICircle>) {\n    if (nonMembers.length === 0) {\n      return;\n    }\n    this.dirty.add(EDirty.NON_MEMBERS);\n    for (const v of nonMembers) {\n      this.nonMembers.push({\n        raw: v,\n        obj: isCircle(v) ? Circle.from(v) : Rectangle.from(v),\n        area: null,\n      });\n    }\n  }\n\n  pushEdge(...edges: ReadonlyArray<ILine>) {\n    if (edges.length === 0) {\n      return;\n    }\n    this.dirty.add(EDirty.EDGES);\n    for (const v of edges) {\n      this.edges.push({\n        raw: v,\n        obj: Line.from(v),\n        area: null,\n      });\n    }\n  }\n\n  private update() {\n    const dirtyMembers = this.dirty.has(EDirty.MEMBERS);\n    const dirtyNonMembers = this.dirty.has(EDirty.NON_MEMBERS);\n    let dirtyEdges = this.dirty.has(EDirty.EDGES);\n    this.dirty.clear();\n\n    const memberObjs = this.members.map((d) => d.obj);\n    if (this.o.virtualEdges && (dirtyMembers || dirtyNonMembers)) {\n      // update virtual edges\n      const nonMembersAsRects = this.nonMembers.map((d) => d.obj);\n      const virtualEdges = calculateVirtualEdges(\n        memberObjs,\n        nonMembersAsRects,\n        this.o.maxRoutingIterations,\n        this.o.morphBuffer\n      );\n\n      const old = new Map<string, Area | null>(this.virtualEdges.map((e) => [e.obj.toString(), e.area]));\n      // reuse edge areas if possible\n      this.virtualEdges = virtualEdges.map((e) => ({\n        raw: e,\n        obj: e,\n        area: old.get(e.toString()) ?? null,\n      }));\n      dirtyEdges = true;\n    }\n\n    let activeRegionDirty = false;\n    if (dirtyMembers || dirtyEdges) {\n      // update the active region\n      const edgesObj = this.virtualEdges.concat(this.edges).map((e) => e.obj);\n      const bb = unionBoundingBox(memberObjs, edgesObj);\n      const padding = Math.max(this.o.edgeR1, this.o.nodeR1) + this.o.morphBuffer;\n      const activeRegion = Rectangle.from(addPadding(bb, padding));\n      if (!activeRegion.equals(this.activeRegion)) {\n        activeRegionDirty = true;\n        this.activeRegion = activeRegion;\n      }\n    }\n\n    if (activeRegionDirty) {\n      const potentialWidth = Math.ceil(this.activeRegion.width / this.o.pixelGroup);\n      const potentialHeight = Math.ceil(this.activeRegion.height / this.o.pixelGroup);\n\n      if (this.activeRegion.x !== this.potentialArea.pixelX || this.activeRegion.y !== this.potentialArea.pixelY) {\n        // full recreate\n        this.potentialArea = Area.fromPixelRegion(this.activeRegion, this.o.pixelGroup);\n        this.members.forEach((m) => (m.area = null));\n        this.nonMembers.forEach((m) => (m.area = null));\n        this.edges.forEach((m) => (m.area = null));\n        this.virtualEdges.forEach((m) => (m.area = null));\n      } else if (potentialWidth !== this.potentialArea.width || potentialHeight !== this.potentialArea.height) {\n        // recreate but we can keep the existing areas\n        this.potentialArea = Area.fromPixelRegion(this.activeRegion, this.o.pixelGroup);\n      }\n    }\n\n    // update\n    const existing = new Map<string, Area>();\n    const addCache = (m: IMember) => {\n      if (m.area) {\n        const key = `${m.obj.width}x${m.obj.height}x${m.obj instanceof Rectangle ? 'R' : 'C'}`;\n        existing.set(key, m.area);\n      }\n    };\n    const createOrAddCache = (m: IMember) => {\n      if (m.area) {\n        return;\n      }\n      const key = `${m.obj.width}x${m.obj.height}x${m.obj instanceof Rectangle ? 'R' : 'C'}`;\n      if (existing.has(key)) {\n        const r = existing.get(key)!;\n        m.area = this.potentialArea.copy(r, { x: m.obj.x - this.o.nodeR1, y: m.obj.y - this.o.nodeR1 });\n        return;\n      }\n      const r =\n        m.obj instanceof Rectangle\n          ? createRectangleInfluenceArea(m.obj, this.potentialArea, this.o.nodeR1)\n          : createGenericInfluenceArea(m.obj, this.potentialArea, this.o.nodeR1);\n      m.area = r;\n      existing.set(key, r);\n    };\n    this.members.forEach(addCache);\n    this.nonMembers.forEach(addCache);\n\n    this.members.forEach(createOrAddCache);\n    this.nonMembers.forEach((m) => {\n      if (!this.activeRegion.intersects(m.obj)) {\n        m.area = null;\n      } else {\n        createOrAddCache(m);\n      }\n    });\n\n    this.edges.forEach((edge) => {\n      if (!edge.area) {\n        edge.area = createLineInfluenceArea(edge.obj, this.potentialArea, this.o.edgeR1);\n      }\n    });\n    this.virtualEdges.forEach((edge) => {\n      if (!edge.area) {\n        edge.area = createLineInfluenceArea(edge.obj, this.potentialArea, this.o.edgeR1);\n      }\n    });\n  }\n\n  drawMembers(ctx: CanvasRenderingContext2D) {\n    for (const member of this.members) {\n      member.obj.draw(ctx);\n    }\n  }\n\n  drawNonMembers(ctx: CanvasRenderingContext2D) {\n    for (const member of this.nonMembers) {\n      member.obj.draw(ctx);\n    }\n  }\n\n  drawEdges(ctx: CanvasRenderingContext2D) {\n    for (const edge of this.edges) {\n      edge.obj.draw(ctx);\n    }\n  }\n\n  drawPotentialArea(ctx: CanvasRenderingContext2D, offset = true) {\n    this.potentialArea.draw(ctx, offset);\n  }\n\n  compute() {\n    if (this.members.length === 0) {\n      return new PointPath([]);\n    }\n\n    if (this.dirty.size > 0) {\n      this.update();\n    }\n\n    const { o, potentialArea } = this;\n\n    const members = this.members.map((m) => m.area!);\n    const edges = this.virtualEdges.concat(this.edges).map((d) => d.area!);\n    const nonMembers = this.nonMembers.filter((d) => d.area != null).map((d) => d.area!);\n    const memberObjs = this.members.map((m) => m.obj);\n\n    return calculatePotentialOutline(\n      potentialArea,\n      members,\n      edges,\n      nonMembers,\n      (p) => p.containsElements(memberObjs),\n      o\n    );\n  }\n}\n\nexport function calculatePotentialOutline(\n  potentialArea: Area,\n  members: ReadonlyArray<Area>,\n  edges: ReadonlyArray<Area>,\n  nonMembers: ReadonlyArray<Area>,\n  validPath: (path: PointPath) => boolean,\n  options: IOutlineOptions = {}\n) {\n  const o = Object.assign({}, defaultOptions, options);\n  let threshold = o.threshold;\n  let memberInfluenceFactor = o.memberInfluenceFactor;\n  let edgeInfluenceFactor = o.edgeInfluenceFactor;\n  let nonMemberInfluenceFactor = o.nonMemberInfluenceFactor;\n\n  // using inverse a for numerical stability\n  const nodeInfA = (o.nodeR0 - o.nodeR1) * (o.nodeR0 - o.nodeR1);\n  const edgeInfA = (o.edgeR0 - o.edgeR1) * (o.edgeR0 - o.edgeR1);\n\n  // try to march, check if surface contains all items\n  for (let iterations = 0; iterations < o.maxMarchingIterations; iterations++) {\n    potentialArea.clear();\n\n    // add all positive energy (included items) first, as negative energy\n    // (morphing) requires all positives to be already set\n    if (memberInfluenceFactor !== 0) {\n      const f = memberInfluenceFactor / nodeInfA;\n      for (const item of members) {\n        // add node energy\n        potentialArea.incArea(item, f);\n      }\n    }\n\n    if (edgeInfluenceFactor !== 0) {\n      // add the influence of all the virtual edges\n      const f = edgeInfluenceFactor / edgeInfA;\n      for (const area of edges) {\n        potentialArea.incArea(area, f);\n      }\n    }\n\n    // calculate negative energy contribution for all other visible items within bounds\n    if (nonMemberInfluenceFactor !== 0) {\n      const f = nonMemberInfluenceFactor / nodeInfA;\n      for (const area of nonMembers) {\n        // add node energy\n        potentialArea.incArea(area, f);\n      }\n    }\n\n    // compute contour\n    const contour = marchingSquares(potentialArea, threshold);\n    if (contour && validPath(contour)) {\n      // found a valid path\n      return contour;\n    }\n\n    // prepare for next iteration\n\n    // reduce negative influences first; this will allow the surface to\n    // pass without making it fatter all around (which raising the threshold does)\n    threshold *= 0.95;\n    if (iterations <= o.maxMarchingIterations * 0.5) {\n      memberInfluenceFactor *= 1.2;\n      edgeInfluenceFactor *= 1.2;\n    } else if (nonMemberInfluenceFactor !== 0 && nonMembers.length > 0) {\n      // after half the iterations, start increasing positive energy and lowering the threshold\n      nonMemberInfluenceFactor *= 0.8;\n    } else {\n      break;\n    }\n  }\n  // cannot find a solution\n  return new PointPath([]);\n}\n\nexport function unionBoundingBox(memberItems: IRectangle[], edgeItems: Line[]) {\n  if (memberItems.length === 0) {\n    return new Rectangle(0, 0, 0, 0);\n  }\n  const activeRegion = Rectangle.from(memberItems[0]);\n  for (const m of memberItems) {\n    activeRegion.add(m);\n  }\n  for (const l of edgeItems) {\n    activeRegion.add(lineBoundingBox(l));\n  }\n  return activeRegion;\n}\n\nexport function createOutline(\n  members: ReadonlyArray<IRectangle | ICircle>,\n  nonMembers: ReadonlyArray<IRectangle> = [],\n  edges: ReadonlyArray<ILine> = [],\n  options: IOutlineOptions = {}\n) {\n  if (members.length === 0) {\n    return new PointPath([]);\n  }\n  const bb = new BubbleSets(options);\n  bb.pushMember(...members);\n  bb.pushNonMember(...nonMembers);\n  bb.pushEdge(...edges);\n  return bb.compute();\n}\n","import type { IRectangle } from './interfaces';\n\nexport function addPadding(rect: IRectangle, padding: number): IRectangle;\nexport function addPadding(rect: ReadonlyArray<IRectangle>, padding: number): ReadonlyArray<IRectangle>;\nexport function addPadding(\n  rect: IRectangle | ReadonlyArray<IRectangle>,\n  padding: number\n): IRectangle | ReadonlyArray<IRectangle> {\n  const map = (r: IRectangle) => ({\n    x: r.x - padding,\n    y: r.y - padding,\n    width: r.width + 2 * padding,\n    height: r.height + 2 * padding,\n  });\n  if (Array.isArray(rect)) {\n    return rect.map(map);\n  }\n  return map(rect as IRectangle);\n}\n","import type { ICircle, IRectangle2 } from '../interfaces';\nimport { ptsDistanceSq } from '../utils';\n\nexport class Circle implements IRectangle2, ICircle {\n  constructor(\n    public cx: number,\n    public cy: number,\n    public radius: number\n  ) {}\n\n  get x() {\n    return this.cx - this.radius;\n  }\n\n  get x2() {\n    return this.cx + this.radius;\n  }\n\n  get width() {\n    return this.radius * 2;\n  }\n\n  get y() {\n    return this.cy - this.radius;\n  }\n\n  get y2() {\n    return this.cy + this.radius;\n  }\n\n  get height() {\n    return this.radius * 2;\n  }\n\n  static from(r: ICircle) {\n    return new Circle(r.cx, r.cy, r.radius);\n  }\n\n  containsPt(x: number, y: number) {\n    return ptsDistanceSq(this.cx, this.cy, x, y) < this.radius * this.radius;\n  }\n\n  distSquare(tempX: number, tempY: number) {\n    const dist = ptsDistanceSq(this.cx, this.cy, tempX, tempY);\n    if (dist < this.radius * this.radius) {\n      // inside\n      return 0;\n    }\n    const offset = Math.sqrt(dist) - this.radius;\n    return offset * offset;\n  }\n\n  draw(ctx: CanvasRenderingContext2D) {\n    ctx.ellipse(this.cx, this.cy, this.radius, this.radius, 0, 0, Math.PI * 2);\n  }\n}\n","import { lineBoundingBox } from './model';\nimport type { Area } from './model/Area';\nimport { addPadding } from './padding';\nimport type { IRectangle, ILine } from './interfaces';\nimport { linePtSegDistSq } from './utils';\n\nexport function createLineInfluenceArea(line: ILine, potentialArea: Area, padding: number) {\n  return createGenericInfluenceArea(\n    Object.assign(lineBoundingBox(line), {\n      distSquare: (x: number, y: number) => linePtSegDistSq(line.x1, line.y1, line.x2, line.y2, x, y),\n    }),\n    potentialArea,\n    padding\n  );\n}\n\nexport function createGenericInfluenceArea(\n  shape: IRectangle & { distSquare(x: number, y: number): number },\n  potentialArea: Area,\n  padding: number\n) {\n  const lr = addPadding(shape, padding);\n  const scaled = potentialArea.scale(lr);\n  const area = potentialArea.createSub(scaled, lr);\n  sample(area, potentialArea, padding, (x, y) => shape.distSquare(x, y));\n  return area;\n}\n\nfunction sample(area: Area, potentialArea: Area, padding: number, distanceFunction: (x: number, y: number) => number) {\n  const padding2 = padding * padding;\n\n  // find the affected subregion of potentialArea\n  // for every point in active subregion of potentialArea, calculate\n  // distance to nearest point on rectangle and add influence\n\n  for (let y = 0; y < area.height; y++) {\n    for (let x = 0; x < area.width; x++) {\n      // convert back to screen coordinates\n      const tempX = potentialArea.invertScaleX(area.i + x);\n      const tempY = potentialArea.invertScaleY(area.j + y);\n      const distanceSq = distanceFunction(tempX, tempY);\n      if (distanceSq === 0) {\n        area.set(x, y, padding2);\n        continue;\n      }\n      // only influence if less than r1\n      if (distanceSq < padding2) {\n        const dr = padding - Math.sqrt(distanceSq);\n        area.set(x, y, dr * dr);\n      }\n    }\n  }\n  return area;\n}\n\nexport function createRectangleInfluenceArea(\n  rect: IRectangle & { distSquare(x: number, y: number): number },\n  potentialArea: Area,\n  padding: number\n) {\n  const scaled = potentialArea.scale(rect);\n  const padded = potentialArea.addPadding(scaled, padding);\n  const area = potentialArea.createSub(padded, { x: rect.x - padding, y: rect.y - padding });\n  const paddingLeft = scaled.x - padded.x;\n  const paddingTop = scaled.y - padded.y;\n  const paddingRight = padded.x2 - scaled.x2;\n  const paddingBottom = padded.y2 - scaled.y2;\n  const innerWidth = padded.width - paddingLeft - paddingRight;\n  const innerHeight = padded.height - paddingTop - paddingBottom;\n\n  // outside rect ... depends on distance\n  // cttc\n  // lffr\n  // lffr\n  // cbbc\n  const padding2 = padding * padding;\n  // within the rect ... full ri2\n  area.fillArea(\n    {\n      x: paddingLeft,\n      y: paddingTop,\n      width: innerWidth + 1,\n      height: innerHeight + 1,\n    },\n    padding2\n  );\n\n  const straightDistances: number[] = [0];\n  const maxPadding = Math.max(paddingTop, paddingLeft, paddingRight, paddingBottom);\n  {\n    const tempX = potentialArea.invertScaleX(scaled.x + scaled.width / 2);\n    for (let i = 1; i < maxPadding; i++) {\n      const tempY = potentialArea.invertScaleY(scaled.y - i);\n      const distanceSq = rect.distSquare(tempX, tempY);\n      // only influence if less than r1\n      if (distanceSq < padding2) {\n        const dr = padding - Math.sqrt(distanceSq);\n        straightDistances.push(dr * dr);\n      } else {\n        break;\n      }\n    }\n  }\n  const cornerDistances: number[][] = [];\n  const maxHorizontalPadding = Math.max(paddingLeft, paddingRight);\n  const maxVerticalPadding = Math.max(paddingTop, paddingRight);\n  for (let i = 1; i < maxHorizontalPadding; i++) {\n    const tempX = potentialArea.invertScaleX(scaled.x - i);\n    const row: number[] = [];\n    for (let j = 1; j < maxVerticalPadding; j++) {\n      const tempY = potentialArea.invertScaleY(scaled.y - j);\n      const distanceSq = rect.distSquare(tempX, tempY);\n      // only influence if less than r1\n      if (distanceSq < padding2) {\n        const dr = padding - Math.sqrt(distanceSq);\n        row.push(dr * dr);\n      } else {\n        row.push(0);\n      }\n    }\n    cornerDistances.push(row);\n  }\n\n  //top\n  for (let y = 1; y < Math.min(paddingTop, straightDistances.length); y++) {\n    const value = straightDistances[y];\n    area.fillHorizontalLine(paddingLeft, paddingTop - y, innerWidth + 1, value);\n  }\n  //bottom\n  for (let y = 1; y < Math.min(paddingBottom, straightDistances.length); y++) {\n    const value = straightDistances[y];\n    area.fillHorizontalLine(paddingLeft, paddingTop + innerHeight + y, innerWidth + 1, value);\n  }\n  //left\n  for (let x = 1; x < Math.min(paddingLeft, straightDistances.length); x++) {\n    const value = straightDistances[x];\n    area.fillVerticalLine(paddingLeft - x, paddingTop, innerHeight + 1, value);\n  }\n  //right\n  for (let x = 1; x < Math.min(paddingBottom, straightDistances.length); x++) {\n    const value = straightDistances[x];\n    area.fillVerticalLine(paddingLeft + innerWidth + x, paddingTop, innerHeight + 1, value);\n  }\n  //top/bottom left\n  for (let i = 1; i < paddingLeft; i++) {\n    const row = cornerDistances[i - 1];\n    const ii = paddingLeft - i;\n    for (let j = 1; j < paddingTop; j++) {\n      area.set(ii, paddingTop - j, row[j - 1]);\n    }\n    for (let j = 1; j < paddingBottom; j++) {\n      area.set(ii, paddingTop + innerHeight + j, row[j - 1]);\n    }\n  }\n  //top/bottom right\n  for (let i = 1; i < paddingRight; i++) {\n    const row = cornerDistances[i - 1];\n    const ii = paddingLeft + innerWidth + i;\n    for (let j = 1; j < paddingTop; j++) {\n      area.set(ii, paddingTop - j, row[j - 1]);\n    }\n    for (let j = 1; j < paddingBottom; j++) {\n      area.set(ii, paddingTop + innerHeight + j, row[j - 1]);\n    }\n  }\n\n  // const other = sample(padded, potentialArea, padding, (x, y) => rect.rectDistSq(x, y));\n  // console.log(other.toString());\n  // console.log(area.toString());\n  return area;\n}\n","import {\n  EState,\n  fractionToLineCenter,\n  Intersection,\n  testIntersection,\n  hasFractionToLineCenter,\n  intersectsLine,\n} from './Intersection';\nimport { Line } from './model/Line';\nimport { doublePointsEqual, ptsDistanceSq } from './utils';\nimport { type IPoint, point, type ICircle, type IRectangle2 } from './interfaces';\n\nexport function calculateVirtualEdges(\n  items: ReadonlyArray<ICircle>,\n  nonMembers: ReadonlyArray<IRectangle2 & { containsPt(x: number, y: number): boolean }>,\n  maxRoutingIterations: number,\n  morphBuffer: number\n) {\n  if (items.length === 0) {\n    return [];\n  }\n  const sorted = sortByDistanceToCentroid(items);\n\n  return sorted\n    .map((d, i) => {\n      const visited = sorted.slice(0, i);\n      return connectItem(nonMembers, d, visited, maxRoutingIterations, morphBuffer);\n    })\n    .flat();\n}\n\nfunction connectItem(\n  nonMembers: ReadonlyArray<IRectangle2 & { containsPt(x: number, y: number): boolean }>,\n  item: ICircle,\n  visited: ReadonlyArray<ICircle>,\n  maxRoutingIterations: number,\n  morphBuffer: number\n) {\n  const itemCenter = point(item.cx, item.cy);\n\n  // discover the nearest neighbor with minimal interference items\n  const closestNeighbor = calculateClosestNeighbor(itemCenter, visited, nonMembers);\n  if (closestNeighbor == null) {\n    return [];\n  }\n  // if there is a visited closest neighbor, add straight line between\n  // them to the positive energy to ensure connected clusters\n  const directLine = new Line(itemCenter.x, itemCenter.y, closestNeighbor.cx, closestNeighbor.cy);\n\n  // route the edge around intersecting nodes not in set\n  const scannedLines = computeRoute(directLine, nonMembers, maxRoutingIterations, morphBuffer);\n\n  return mergeLines(scannedLines, nonMembers);\n}\n\nfunction computeRoute(\n  directLine: Line,\n  nonMembers: ReadonlyArray<IRectangle2 & { containsPt(x: number, y: number): boolean }>,\n  maxRoutingIterations: number,\n  morphBuffer: number\n) {\n  // route the edge around intersecting nodes not in set\n  const scannedLines: Line[] = [];\n  const linesToCheck: Line[] = [];\n  linesToCheck.push(directLine);\n\n  let hasIntersection = true;\n\n  for (let iterations = 0; iterations < maxRoutingIterations && hasIntersection; iterations++) {\n    hasIntersection = false;\n    while (!hasIntersection && linesToCheck.length > 0) {\n      const line = linesToCheck.pop()!;\n      // resolve intersections in order along edge\n      const closestItem = getCenterItem(nonMembers, line);\n      const intersections = closestItem ? testIntersection(line, closestItem) : null;\n\n      // 2 intersections = line passes through item\n      if (!closestItem || !intersections || intersections.count !== 2) {\n        // no intersection found, mark this line as completed\n        if (!hasIntersection) {\n          scannedLines.push(line);\n        }\n        continue;\n      }\n\n      let tempMorphBuffer = morphBuffer;\n      let movePoint = rerouteLine(closestItem, tempMorphBuffer, intersections, true);\n      // test the movePoint already exists\n      let foundFirst = pointExists(movePoint, linesToCheck) || pointExists(movePoint, scannedLines);\n      let pointInside = isPointInRectangles(movePoint, nonMembers);\n      // prefer first corner, even if buffer becomes very small\n      while (!foundFirst && pointInside && tempMorphBuffer >= 1) {\n        // try a smaller buffer\n        tempMorphBuffer /= 1.5;\n        movePoint = rerouteLine(closestItem, tempMorphBuffer, intersections, true);\n        foundFirst = pointExists(movePoint, linesToCheck) || pointExists(movePoint, scannedLines);\n        pointInside = isPointInRectangles(movePoint, nonMembers);\n      }\n\n      if (movePoint && !foundFirst && !pointInside) {\n        // add 2 rerouted lines to check\n        linesToCheck.push(new Line(line.x1, line.y1, movePoint.x, movePoint.y));\n        linesToCheck.push(new Line(movePoint.x, movePoint.y, line.x2, line.y2));\n        // indicate intersection found\n        hasIntersection = true;\n      }\n\n      if (hasIntersection) {\n        continue;\n      }\n\n      // if we didn't find a valid point around the\n      // first corner, try the second\n      tempMorphBuffer = morphBuffer;\n      movePoint = rerouteLine(closestItem, tempMorphBuffer, intersections, false);\n      let foundSecond = pointExists(movePoint, linesToCheck) || pointExists(movePoint, scannedLines);\n      pointInside = isPointInRectangles(movePoint, nonMembers);\n      // if both corners have been used, stop; otherwise gradually reduce buffer and try second corner\n      while (!foundSecond && pointInside && tempMorphBuffer >= 1) {\n        // try a smaller buffer\n        tempMorphBuffer /= 1.5;\n        movePoint = rerouteLine(closestItem, tempMorphBuffer, intersections, false);\n        foundSecond = pointExists(movePoint, linesToCheck) || pointExists(movePoint, scannedLines);\n        pointInside = isPointInRectangles(movePoint, nonMembers);\n      }\n\n      if (movePoint && !foundSecond) {\n        // add 2 rerouted lines to check\n        linesToCheck.push(new Line(line.x1, line.y1, movePoint.x, movePoint.y));\n        linesToCheck.push(new Line(movePoint.x, movePoint.y, line.x2, line.y2));\n        // indicate intersection found\n        hasIntersection = true;\n      }\n      // no intersection found, mark this line as completed\n      if (!hasIntersection) {\n        scannedLines.push(line);\n      }\n    }\n  }\n  // finalize any that were not rerouted (due to running out of\n  // iterations) or if we aren't morphing\n  while (linesToCheck.length > 0) {\n    scannedLines.push(linesToCheck.pop()!);\n  }\n\n  return scannedLines;\n}\n\nfunction mergeLines(scannedLines: Line[], nonMembers: ReadonlyArray<IRectangle2>) {\n  const finalRoute: Line[] = [];\n  // try to merge consecutive lines if possible\n  while (scannedLines.length > 0) {\n    const line1 = scannedLines.pop()!;\n    if (scannedLines.length === 0) {\n      finalRoute.push(line1);\n      break;\n    }\n    const line2 = scannedLines.pop()!;\n    const mergeLine = new Line(line1.x1, line1.y1, line2.x2, line2.y2);\n    // resolve intersections in order along edge\n    const closestItem = getCenterItem(nonMembers, mergeLine);\n    // merge most recent line and previous line\n    if (!closestItem) {\n      scannedLines.push(mergeLine);\n    } else {\n      finalRoute.push(line1);\n      scannedLines.push(line2);\n    }\n  }\n  return finalRoute;\n}\n\nfunction calculateClosestNeighbor(\n  itemCenter: IPoint,\n  visited: ReadonlyArray<ICircle>,\n  nonMembers: ReadonlyArray<IRectangle2>\n) {\n  let minLengthSq = Number.POSITIVE_INFINITY;\n  return visited.reduce(\n    (closestNeighbor, neighborItem) => {\n      const distanceSq = ptsDistanceSq(itemCenter.x, itemCenter.y, neighborItem.cx, neighborItem.cy);\n      if (distanceSq > minLengthSq) {\n        // the interference can only increase the distance so if already bigger, return\n        return closestNeighbor;\n      }\n\n      const directLine = new Line(itemCenter.x, itemCenter.y, neighborItem.cx, neighborItem.cy);\n      // augment distance by number of interfering items\n      const numberInterferenceItems = itemsCuttingLine(nonMembers, directLine);\n\n      // TODO is there a better function to consider interference in nearest-neighbor checking? This is hacky\n      if (distanceSq * (numberInterferenceItems + 1) * (numberInterferenceItems + 1) < minLengthSq) {\n        closestNeighbor = neighborItem;\n        minLengthSq = distanceSq * (numberInterferenceItems + 1) * (numberInterferenceItems + 1);\n      }\n      return closestNeighbor;\n    },\n    null as ICircle | null\n  );\n}\n\nfunction sortByDistanceToCentroid<T extends ICircle>(items: ReadonlyArray<T>) {\n  if (items.length < 2) {\n    return items;\n  }\n  let totalX = 0;\n  let totalY = 0;\n  items.forEach((item) => {\n    totalX += item.cx;\n    totalY += item.cy;\n  });\n  totalX /= items.length;\n  totalY /= items.length;\n  return items\n    .map((item) => {\n      const diffX = totalX - item.cx;\n      const diffY = totalY - item.cy;\n      const dist = diffX * diffX + diffY * diffY;\n      return [item, dist] as [T, number];\n    })\n    .sort((a, b) => a[1] - b[1])\n    .map((d) => d[0]);\n}\n\nfunction isPointInRectangles(p: IPoint, rects: ReadonlyArray<{ containsPt(x: number, y: number): boolean }>) {\n  return rects.some((r) => r.containsPt(p.x, p.y));\n}\n\nfunction pointExists(pointToCheck: IPoint, lines: ReadonlyArray<Line>) {\n  return lines.some((checkEndPointsLine) => {\n    if (doublePointsEqual(checkEndPointsLine.x1, checkEndPointsLine.y1, pointToCheck.x, pointToCheck.y, 1e-3)) {\n      return true;\n    }\n    if (doublePointsEqual(checkEndPointsLine.x2, checkEndPointsLine.y2, pointToCheck.x, pointToCheck.y, 1e-3)) {\n      return true;\n    }\n    return false;\n  });\n}\n\nfunction getCenterItem(items: ReadonlyArray<IRectangle2>, testLine: Line) {\n  let minDistance = Number.POSITIVE_INFINITY;\n  let closestItem: IRectangle2 | null = null;\n\n  for (const item of items) {\n    if (!intersectsLine(item, testLine)) {\n      continue;\n    }\n    const distance = fractionToLineCenter(item, testLine);\n    // find closest intersection\n    if (distance >= 0 && distance < minDistance) {\n      closestItem = item;\n      minDistance = distance;\n    }\n  }\n  return closestItem;\n}\n\nfunction itemsCuttingLine(items: ReadonlyArray<IRectangle2>, testLine: Line) {\n  return items.reduce((count, item) => {\n    if (intersectsLine(item, testLine) && hasFractionToLineCenter(item, testLine)) {\n      return count + 1;\n    }\n    return count;\n  }, 0);\n}\n\nfunction rerouteLine(\n  item: IRectangle2,\n  rerouteBuffer: number,\n  intersections: { top: Intersection; left: Intersection; right: Intersection; bottom: Intersection },\n  wrapNormal: boolean\n) {\n  const topIntersect = intersections.top;\n  const leftIntersect = intersections.left;\n  const bottomIntersect = intersections.bottom;\n  const rightIntersect = intersections.right;\n\n  // wrap around the most efficient way\n  if (wrapNormal) {\n    // left side\n    if (leftIntersect.state === EState.POINT) {\n      if (topIntersect.state === EState.POINT)\n        // triangle, must go around top left\n        return point(item.x - rerouteBuffer, item.y - rerouteBuffer);\n      if (bottomIntersect.state === EState.POINT)\n        // triangle, must go around bottom left\n        return point(item.x - rerouteBuffer, item.y2 + rerouteBuffer);\n      // else through left to right, calculate areas\n      const totalArea = item.width * item.height;\n      // top area\n      const topArea = item.width * ((leftIntersect.y - item.y + (rightIntersect.y - item.y)) * 0.5);\n      if (topArea < totalArea * 0.5) {\n        // go around top (the side which would make a greater movement)\n        if (leftIntersect.y > rightIntersect.y)\n          // top left\n          return point(item.x - rerouteBuffer, item.y - rerouteBuffer);\n        // top right\n        return point(item.x2 + rerouteBuffer, item.y - rerouteBuffer);\n      }\n      // go around bottom\n      if (leftIntersect.y < rightIntersect.y)\n        // bottom left\n        return point(item.x - rerouteBuffer, item.y2 + rerouteBuffer);\n      // bottom right\n      return point(item.x2 + rerouteBuffer, item.y2 + rerouteBuffer);\n    }\n    // right side\n    if (rightIntersect.state === EState.POINT) {\n      if (topIntersect.state === EState.POINT)\n        // triangle, must go around top right\n        return point(item.x2 + rerouteBuffer, item.y - rerouteBuffer);\n      if (bottomIntersect.state === EState.POINT)\n        // triangle, must go around bottom right\n        return point(item.x2 + rerouteBuffer, item.y2 + rerouteBuffer);\n    }\n    // else through top to bottom, calculate areas\n    const totalArea = item.height * item.width;\n    const leftArea = item.height * ((topIntersect.x - item.x + (bottomIntersect.x - item.x)) * 0.5);\n    if (leftArea < totalArea * 0.5) {\n      // go around left\n      if (topIntersect.x > bottomIntersect.x)\n        // top left\n        return point(item.x - rerouteBuffer, item.y - rerouteBuffer);\n      // bottom left\n      return point(item.x - rerouteBuffer, item.y2 + rerouteBuffer);\n    }\n    // go around right\n    if (topIntersect.x < bottomIntersect.x)\n      // top right\n      return point(item.x2 + rerouteBuffer, item.y - rerouteBuffer);\n    // bottom right\n    return point(item.x2 + rerouteBuffer, item.y2 + rerouteBuffer);\n  }\n  // wrap around opposite (usually because the first move caused a problem)\n  if (leftIntersect.state === EState.POINT) {\n    if (topIntersect.state === EState.POINT)\n      // triangle, must go around bottom right\n      return point(item.x2 + rerouteBuffer, item.y2 + rerouteBuffer);\n    if (bottomIntersect.state === EState.POINT)\n      // triangle, must go around top right\n      return point(item.x2 + rerouteBuffer, item.y - rerouteBuffer);\n    // else through left to right, calculate areas\n    const totalArea = item.height * item.width;\n    const topArea = item.width * ((leftIntersect.y - item.y + (rightIntersect.y - item.y)) * 0.5);\n    if (topArea < totalArea * 0.5) {\n      // go around bottom (the side which would make a lesser movement)\n      if (leftIntersect.y > rightIntersect.y)\n        // bottom right\n        return point(item.x2 + rerouteBuffer, item.y2 + rerouteBuffer);\n      // bottom left\n      return point(item.x - rerouteBuffer, item.y2 + rerouteBuffer);\n    }\n    // go around top\n    if (leftIntersect.y < rightIntersect.y)\n      // top right\n      return point(item.x2 + rerouteBuffer, item.y - rerouteBuffer);\n    // top left\n    return point(item.x - rerouteBuffer, item.y - rerouteBuffer);\n  }\n  if (rightIntersect.state === EState.POINT) {\n    if (topIntersect.state === EState.POINT)\n      // triangle, must go around bottom left\n      return point(item.x - rerouteBuffer, item.y2 + rerouteBuffer);\n    if (bottomIntersect.state === EState.POINT)\n      // triangle, must go around top left\n      return point(item.x - rerouteBuffer, item.y - rerouteBuffer);\n  }\n  // else through top to bottom, calculate areas\n  const totalArea = item.height * item.width;\n  const leftArea = item.height * ((topIntersect.x - item.x + (bottomIntersect.x - item.x)) * 0.5);\n  if (leftArea < totalArea * 0.5) {\n    // go around right\n    if (topIntersect.x > bottomIntersect.x)\n      // bottom right\n      return point(item.x2 + rerouteBuffer, item.y2 + rerouteBuffer);\n    // top right\n    return point(item.x2 + rerouteBuffer, item.y - rerouteBuffer);\n  }\n  // go around left\n  if (topIntersect.x < bottomIntersect.x)\n    // bottom left\n    return point(item.x - rerouteBuffer, item.y2 + rerouteBuffer);\n  // top left\n  return point(item.x - rerouteBuffer, item.y - rerouteBuffer);\n}\n"],"names":[],"mappings":";;;;;;;AAAO;AACP;AACA;AACA;AACO;AACP;AACA;AACA;AACO;AACP;AACA;AACA;AACO;AACP;AACA;AACA;AACO;AACP;AACA;AACA;AACA;AACA;AACO;AACP;AACA;AACO;AACA;AACA;AACA;AACP;AACA;AACA;;AC9BO;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACO;;ACtBA;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;;AClCO;AACA;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;;ACnBO;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;;ACVO;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACO;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACO;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACO;AACP;AACO;AACA;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACO;AACA;AACA;;ACxFA;AACA;;ACDA;AACP;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;AACA;;ACdO;AACA;AACP;AACA;AACO;AACP;AACA;;ACNO;AACP;AACA;;;"}