{"version":3,"file":"overlap.js","sourceRoot":"","sources":["../../../../src/geometry/label/layout/overlap.ts"],"names":[],"mappings":"AAAA,OAAO,EAAE,IAAI,EAAE,MAAM,YAAY,CAAC;AAIlC,IAAM,SAAS,GAAG,GAAG,CAAC;AAetB;;;GAGG;AACH;IAOE,gBAAY,GAAmB;QAAnB,oBAAA,EAAA,QAAmB;QAFvB,WAAM,GAAW,EAAE,CAAC;QAGlB,IAAA,KAAuB,GAAG,KAAlB,EAAR,IAAI,mBAAG,CAAC,KAAA,EAAE,KAAa,GAAG,KAAR,EAAR,IAAI,mBAAG,CAAC,KAAA,CAAS;QACnC,IAAI,CAAC,IAAI,GAAG,IAAI,CAAC;QACjB,IAAI,CAAC,IAAI,GAAG,IAAI,CAAC;IACnB,CAAC;IAEM,uBAAM,GAAb,UAAc,IAAU;QACtB,IAAI,MAAM,GAAG,IAAI,CAAC;QAClB,IAAM,MAAM,GAAG,IAAI,CAAC,MAAM,CAAC;QAC3B,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,KAAK,IAAI,CAAC,GAAG,IAAI,EAAE,CAAC,IAAI,IAAI,EAAE,CAAC,IAAI,CAAC,EAAE;YACpC,IAAI,CAAC,MAAM,CAAC,CAAC,CAAC,EAAE;gBACd,MAAM,CAAC,CAAC,CAAC,GAAG,EAAE,CAAC;gBACf,SAAS;aACV;YACD,IAAI,CAAC,KAAK,IAAI,IAAI,CAAC,KAAK,IAAI,EAAE;gBAC5B,KAAK,IAAI,CAAC,GAAG,IAAI,EAAE,CAAC,IAAI,IAAI,EAAE,CAAC,EAAE,EAAE;oBACjC,IAAI,MAAM,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,EAAE;wBAChB,MAAM,GAAG,KAAK,CAAC;wBACf,MAAM;qBACP;iBACF;aACF;iBAAM;gBACL,IAAI,MAAM,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,IAAI,MAAM,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,EAAE;oBACtC,MAAM,GAAG,KAAK,CAAC;oBACf,MAAM;iBACP;aACF;SACF;QACD,OAAO,MAAM,CAAC;IAChB,CAAC;IAEM,wBAAO,GAAd,UAAe,IAAU;QACvB,IAAM,MAAM,GAAG,IAAI,CAAC,MAAM,CAAC;QAC3B,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,IAAM,IAAI,GAAG,IAAI,CAAC,KAAK,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC;QACnC,eAAe;QACf,KAAK,IAAI,CAAC,GAAG,IAAI,EAAE,CAAC,IAAI,IAAI,EAAE,CAAC,IAAI,CAAC,EAAE;YACpC,IAAI,CAAC,MAAM,CAAC,CAAC,CAAC,EAAE;gBACd,MAAM,CAAC,CAAC,CAAC,GAAG,EAAE,CAAC;aAChB;SACF;QACD,KAAK,IAAI,CAAC,GAAG,IAAI,EAAE,CAAC,IAAI,IAAI,EAAE,CAAC,IAAI,IAAI,CAAC,IAAI,EAAE;YAC5C,KAAK,IAAI,CAAC,GAAG,IAAI,EAAE,CAAC,IAAI,IAAI,EAAE,CAAC,IAAI,IAAI,CAAC,IAAI,EAAE;gBAC5C,MAAM,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,IAAI,CAAC;aACrB;YACD,MAAM,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,IAAI,CAAC;SACxB;QAED,kBAAkB;QAClB,IAAI,IAAI,CAAC,IAAI,KAAK,CAAC,EAAE;YACnB,KAAK,IAAI,CAAC,GAAG,IAAI,EAAE,CAAC,IAAI,IAAI,EAAE,CAAC,IAAI,CAAC,EAAE;gBACpC,MAAM,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,GAAG,IAAI,CAAC;gBACvB,MAAM,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,GAAG,IAAI,CAAC;aACxB;SACF;QAED,kBAAkB;QAClB,IAAI,IAAI,CAAC,IAAI,KAAK,CAAC,EAAE;YACnB,KAAK,IAAI,CAAC,GAAG,IAAI,EAAE,CAAC,IAAI,IAAI,EAAE,CAAC,IAAI,CAAC,EAAE;gBACpC,MAAM,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,IAAI,CAAC;gBACvB,MAAM,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,IAAI,CAAC;aACxB;SACF;IACH,CAAC;IAEM,wBAAO,GAAd;QACE,IAAI,CAAC,MAAM,GAAG,EAAE,CAAC;IACnB,CAAC;IACH,aAAC;AAAD,CAAC,AAjFD,IAiFC;AAED,SAAS,UAAU,CAAC,KAAa,EAAE,MAAc,EAAE,QAA4B;IAA5B,yBAAA,EAAA,oBAA4B;IAC7E,IAAM,EAAE,GAAG,CAAC,CAAC,CAAC;IACR,IAAA,KAAW,KAAK,CAAC,IAAI,EAAE,EAArB,CAAC,OAAA,EAAE,CAAC,OAAiB,CAAC;IAC9B,IAAM,IAAI,GAAG,KAAK,CAAC,aAAa,EAAE,CAAC;IACnC,IAAM,QAAQ,GAAG,IAAI,CAAC,IAAI,CAAC,IAAI,CAAC,KAAK,GAAG,IAAI,CAAC,KAAK,GAAG,IAAI,CAAC,MAAM,GAAG,IAAI,CAAC,MAAM,CAAC,CAAC;IAChF,IAAI,IAAI,CAAC;IACT,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC;IACZ,IAAI,EAAE,GAAG,CAAC,CAAC;IACX,IAAI,EAAE,GAAG,CAAC,CAAC;IACX,IAAM,CAAC,GAAG,UAAC,KAAa;QACtB,IAAM,EAAE,GAAG,KAAK,GAAG,GAAG,CAAC;QACvB,OAAO,CAAC,EAAE,GAAG,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE,GAAG,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,CAAC;IAChD,CAAC,CAAC;IAEF,IAAI,MAAM,CAAC,MAAM,CAAC,IAAI,CAAC,EAAE;QACvB,MAAM,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC;QACrB,OAAO,IAAI,CAAC;KACb;IACD,IAAI,OAAO,GAAG,KAAK,CAAC;IACpB,IAAI,KAAK,GAAG,CAAC,CAAC;IACd,IAAM,aAAa,GAAG,EAAE,CAAC;IACzB,OAAO,IAAI,CAAC,GAAG,CAAC,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,CAAC,GAAG,QAAQ,IAAI,KAAK,GAAG,QAAQ,EAAE;QAC1E,IAAI,GAAG,CAAC,CAAC,CAAC,CAAC,IAAI,EAAE,CAAC,CAAC,CAAC;QACpB,EAAE,GAAG,CAAC,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC;QACf,EAAE,GAAG,CAAC,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC;QACf,IAAI,CAAC,CAAC,EAAE,IAAI,CAAC,EAAE,CAAC,IAAI,aAAa,CAAC,UAAG,EAAE,cAAI,EAAE,CAAE,CAAC,EAAE;YAChD,SAAS;SACV;QACD,KAAK,CAAC,IAAI,CAAC,EAAE,CAAC,EAAE,CAAC,GAAG,EAAE,EAAE,CAAC,EAAE,CAAC,GAAG,EAAE,EAAE,CAAC,CAAC;QACrC,IAAI,EAAE,GAAG,EAAE,GAAG,CAAC,EAAE;YACf,KAAK,CAAC,IAAI,CAAC,WAAW,EAAE,OAAO,CAAC,CAAC;SAClC;QACD,KAAK,EAAE,CAAC;QACR,IAAI,MAAM,CAAC,MAAM,CAAC,KAAK,CAAC,aAAa,EAAE,CAAC,EAAE;YACxC,MAAM,CAAC,OAAO,CAAC,KAAK,CAAC,aAAa,EAAE,CAAC,CAAC;YACtC,OAAO,GAAG,IAAI,CAAC;YACf,aAAa,CAAC,UAAG,EAAE,cAAI,EAAE,CAAE,CAAC,GAAG,IAAI,CAAC;YACpC,MAAM;SACP;KACF;IACD,OAAO,OAAO,CAAC;AACjB,CAAC;AAED;;;;;;;;;GASG;AACH,SAAS,mBAAmB,CAAC,KAAa,EAAE,CAAS,EAAE,CAAS,EAAE,KAAa;IACvE,IAAA,KAAoB,KAAK,CAAC,aAAa,EAAE,EAAvC,KAAK,WAAA,EAAE,MAAM,YAA0B,CAAC;IAChD,IAAM,KAAK,GAAG;QACZ,CAAC,GAAA;QACD,CAAC,GAAA;QACD,SAAS,EAAE,QAAQ;KACpB,CAAC;IACF,QAAQ,KAAK,EAAE;QACb,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,MAAM,GAAG,CAAC,CAAC;YACtB,KAAK,CAAC,CAAC,IAAI,CAAC,CAAC;YACb,KAAK,CAAC,SAAS,GAAG,MAAM,CAAC;YACzB,MAAM;QACR,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,MAAM,GAAG,CAAC,CAAC;YACtB,KAAK,CAAC,CAAC,IAAI,CAAC,CAAC;YACb,KAAK,CAAC,SAAS,GAAG,OAAO,CAAC;YAC1B,MAAM;QACR,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,MAAM,GAAG,CAAC,CAAC;YACtB,KAAK,CAAC,CAAC,IAAI,CAAC,CAAC;YACb,KAAK,CAAC,SAAS,GAAG,OAAO,CAAC;YAC1B,MAAM;QACR,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,MAAM,GAAG,CAAC,CAAC;YACtB,KAAK,CAAC,CAAC,IAAI,CAAC,CAAC;YACb,KAAK,CAAC,SAAS,GAAG,MAAM,CAAC;YACzB,MAAM;QACR,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,MAAM,GAAG,CAAC,GAAG,CAAC,CAAC;YAC1B,MAAM;QACR,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,MAAM,GAAG,CAAC,GAAG,CAAC,CAAC;YAC1B,MAAM;QACR,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,KAAK,GAAG,CAAC,CAAC;YACrB,KAAK,CAAC,SAAS,GAAG,MAAM,CAAC;YACzB,MAAM;QACR,KAAK,CAAC;YACJ,KAAK,CAAC,CAAC,IAAI,KAAK,GAAG,CAAC,CAAC;YACrB,KAAK,CAAC,SAAS,GAAG,OAAO,CAAC;YAC1B,MAAM;QACR;YACE,MAAM;KACT;IACD,KAAK,CAAC,IAAI,CAAC,KAAK,CAAC,CAAC;IAClB,OAAO,KAAK,CAAC,aAAa,EAAE,CAAC;AAC/B,CAAC;AAED;;;;;GAKG;AACH,MAAM,UAAU,YAAY,CAAC,KAAkB,EAAE,MAAgB,EAAE,MAA2B,EAAE,MAAY;IAC1G,IAAM,MAAM,GAAG,IAAI,MAAM,EAAE,CAAC;IAC5B,IAAI,CAAC,MAAM,EAAE,UAAC,KAAa;QACzB,IAAM,UAAU,GAAG,KAAK,CAAC,IAAI,CAAC,UAAC,KAAK,IAAK,OAAA,KAAK,CAAC,GAAG,CAAC,MAAM,CAAC,KAAK,MAAM,EAA5B,CAA4B,CAAW,CAAC;QACjF,IAAI,CAAC,UAAU,CAAC,UAAU,EAAE,MAAM,CAAC,EAAE;YACnC,KAAK,CAAC,MAAM,CAAC,IAAI,CAAC,CAAC;SACpB;IACH,CAAC,CAAC,CAAC;IACH,MAAM,CAAC,OAAO,EAAE,CAAC;AACnB,CAAC;AAED;;;;GAIG;AACH,MAAM,UAAU,OAAO,CAAC,KAAkB,EAAE,MAAgB,EAAE,MAA2B,EAAE,MAAY;IACrG,IAAM,MAAM,GAAG,IAAI,MAAM,EAAE,CAAC;IAC5B,IAAI,CAAC,MAAM,EAAE,UAAC,KAAa;QACzB,IAAM,UAAU,GAAG,KAAK,CAAC,IAAI,CAAC,UAAC,KAAK,IAAK,OAAA,KAAK,CAAC,GAAG,CAAC,MAAM,CAAC,KAAK,MAAM,EAA5B,CAA4B,CAAW,CAAC;QAC3E,IAAA,KAAW,UAAU,CAAC,IAAI,EAAE,EAA1B,CAAC,OAAA,EAAE,CAAC,OAAsB,CAAC;QACnC,IAAI,OAAO,GAAG,KAAK,CAAC;QACpB,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,IAAI,CAAC,EAAE,CAAC,EAAE,EAAE;YAC3B,IAAM,IAAI,GAAG,mBAAmB,CAAC,UAAU,EAAE,CAAC,EAAE,CAAC,EAAE,CAAC,CAAC,CAAC;YACtD,IAAI,MAAM,CAAC,MAAM,CAAC,IAAI,CAAC,EAAE;gBACvB,MAAM,CAAC,OAAO,CAAC,IAAI,CAAC,CAAC;gBACrB,OAAO,GAAG,IAAI,CAAC;gBACf,MAAM;aACP;SACF;QACD,IAAI,CAAC,OAAO,EAAE;YACZ,KAAK,CAAC,MAAM,CAAC,IAAI,CAAC,CAAC;SACpB;IACH,CAAC,CAAC,CAAC;IAEH,MAAM,CAAC,OAAO,EAAE,CAAC;AACnB,CAAC","sourcesContent":["import { each } from '@antv/util';\nimport { BBox, IGroup, IShape } from '../../../dependents';\nimport { LabelItem } from '../interface';\n\nconst MAX_TIMES = 100;\n\n/** @ignore */\ninterface Bitmap {\n  [key: number]: {\n    [key: number]: boolean;\n  };\n}\n\n/** @ignore */\ninterface GreedyCfg {\n  readonly xGap?: number;\n  readonly yGap?: number;\n}\n\n/**\n * @ignore\n * Greedy 贪婪算法\n */\nclass Greedy {\n  public readonly xGap: number;\n  /** optimizing for text overlapping detection: use a min text height as gap */\n  public readonly yGap: number;\n\n  private bitmap: Bitmap = {};\n\n  constructor(cfg: GreedyCfg = {}) {\n    const { xGap = 1, yGap = 8 } = cfg;\n    this.xGap = xGap;\n    this.yGap = yGap;\n  }\n\n  public hasGap(bbox: BBox): boolean {\n    let hasGap = true;\n    const bitmap = this.bitmap;\n    const minX = Math.round(bbox.minX);\n    const maxX = Math.round(bbox.maxX);\n    const minY = Math.round(bbox.minY);\n    const maxY = Math.round(bbox.maxY);\n    for (let i = minX; i <= maxX; i += 1) {\n      if (!bitmap[i]) {\n        bitmap[i] = {};\n        continue;\n      }\n      if (i === minX || i === maxX) {\n        for (let j = minY; j <= maxY; j++) {\n          if (bitmap[i][j]) {\n            hasGap = false;\n            break;\n          }\n        }\n      } else {\n        if (bitmap[i][minY] || bitmap[i][maxY]) {\n          hasGap = false;\n          break;\n        }\n      }\n    }\n    return hasGap;\n  }\n\n  public fillGap(bbox: BBox): void {\n    const bitmap = this.bitmap;\n    const minX = Math.round(bbox.minX);\n    const maxX = Math.round(bbox.maxX);\n    const minY = Math.round(bbox.minY);\n    const maxY = Math.round(bbox.maxY);\n    // filling grid\n    for (let i = minX; i <= maxX; i += 1) {\n      if (!bitmap[i]) {\n        bitmap[i] = {};\n      }\n    }\n    for (let i = minX; i <= maxX; i += this.xGap) {\n      for (let j = minY; j <= maxY; j += this.yGap) {\n        bitmap[i][j] = true;\n      }\n      bitmap[i][maxY] = true;\n    }\n\n    // filling y edges\n    if (this.yGap !== 1) {\n      for (let i = minY; i <= maxY; i += 1) {\n        bitmap[minX][i] = true;\n        bitmap[maxX][i] = true;\n      }\n    }\n\n    // filling x edges\n    if (this.xGap !== 1) {\n      for (let i = minX; i <= maxX; i += 1) {\n        bitmap[i][minY] = true;\n        bitmap[i][maxY] = true;\n      }\n    }\n  }\n\n  public destroy(): void {\n    this.bitmap = {};\n  }\n}\n\nfunction spiralFill(label: IShape, greedy: Greedy, maxTimes: number = MAX_TIMES) {\n  const dt = -1;\n  const { x, y } = label.attr();\n  const bbox = label.getCanvasBBox();\n  const maxDelta = Math.sqrt(bbox.width * bbox.width + bbox.height * bbox.height);\n  let dxdy;\n  let t = -dt;\n  let dx = 0;\n  let dy = 0;\n  const f = (param: number) => {\n    const nt = param * 0.1;\n    return [nt * Math.cos(nt), nt * Math.sin(nt)];\n  };\n\n  if (greedy.hasGap(bbox)) {\n    greedy.fillGap(bbox);\n    return true;\n  }\n  let canFill = false;\n  let times = 0;\n  const accessedCache = {};\n  while (Math.min(Math.abs(dx), Math.abs(dy)) < maxDelta && times < maxTimes) {\n    dxdy = f((t += dt));\n    dx = ~~dxdy[0];\n    dy = ~~dxdy[1];\n    if ((!dx && !dy) || accessedCache[`${dx}-${dy}`]) {\n      continue;\n    }\n    label.attr({ x: x + dx, y: y + dy });\n    if (dx + dy < 0) {\n      label.attr('textAlign', 'right');\n    }\n    times++;\n    if (greedy.hasGap(label.getCanvasBBox())) {\n      greedy.fillGap(label.getCanvasBBox());\n      canFill = true;\n      accessedCache[`${dx}-${dy}`] = true;\n      break;\n    }\n  }\n  return canFill;\n}\n\n/*\n *  根据如下规则尝试放置label\n *                5\n *        ------------------\n *        |    1   |   0   |\n *    8   —————————4————————   7\n *        |    2   |   3   |\n *        ——————————————————\n *                 6\n */\nfunction adjustLabelPosition(label: IShape, x: number, y: number, index: number) {\n  const { width, height } = label.getCanvasBBox();\n  const attrs = {\n    x,\n    y,\n    textAlign: 'center',\n  };\n  switch (index) {\n    case 0:\n      attrs.y -= height + 1;\n      attrs.x += 1;\n      attrs.textAlign = 'left';\n      break;\n    case 1:\n      attrs.y -= height + 1;\n      attrs.x -= 1;\n      attrs.textAlign = 'right';\n      break;\n    case 2:\n      attrs.y += height + 1;\n      attrs.x -= 1;\n      attrs.textAlign = 'right';\n      break;\n    case 3:\n      attrs.y += height + 1;\n      attrs.x += 1;\n      attrs.textAlign = 'left';\n      break;\n    case 5:\n      attrs.y -= height * 2 + 2;\n      break;\n    case 6:\n      attrs.y += height * 2 + 2;\n      break;\n    case 7:\n      attrs.x += width + 1;\n      attrs.textAlign = 'left';\n      break;\n    case 8:\n      attrs.x -= width + 1;\n      attrs.textAlign = 'right';\n      break;\n    default:\n      break;\n  }\n  label.attr(attrs);\n  return label.getCanvasBBox();\n}\n\n/**\n * @ignore\n * label 防遮挡布局：在不改变 label 位置的情况下对相互重叠的 label 进行调整。\n * 不同于 'overlap' 类型的布局，该布局不会对 label 的位置进行偏移调整。\n * @param labels 参与布局调整的 label 数组集合\n */\nexport function fixedOverlap(items: LabelItem[], labels: IGroup[], shapes: IShape[] | IGroup[], region: BBox) {\n  const greedy = new Greedy();\n  each(labels, (label: IGroup) => {\n    const labelShape = label.find((shape) => shape.get('type') === 'text') as IShape;\n    if (!spiralFill(labelShape, greedy)) {\n      label.remove(true);\n    }\n  });\n  greedy.destroy();\n}\n\n/**\n * @ignore\n * label 防遮挡布局：为了防止 label 之间相互覆盖同时保证尽可能多 的 label 展示，通过尝试将 label 向**四周偏移**来剔除放不下的 label\n * @param labels 参与布局调整的 label 数组集合\n */\nexport function overlap(items: LabelItem[], labels: IGroup[], shapes: IShape[] | IGroup[], region: BBox) {\n  const greedy = new Greedy();\n  each(labels, (label: IGroup) => {\n    const labelShape = label.find((shape) => shape.get('type') === 'text') as IShape;\n    const { x, y } = labelShape.attr();\n    let canFill = false;\n    for (let i = 0; i <= 8; i++) {\n      const bbox = adjustLabelPosition(labelShape, x, y, i);\n      if (greedy.hasGap(bbox)) {\n        greedy.fillGap(bbox);\n        canFill = true;\n        break;\n      }\n    }\n    if (!canFill) {\n      label.remove(true);\n    }\n  });\n\n  greedy.destroy();\n}\n"]}