{"version":3,"sources":["../src/util.ts","../src/Hull.ts","../src/ImageTrace.ts","../src/createConvexHull.ts"],"names":["nf","x","precision","k10","vec2Arr","y","arr2Vec","Hull","_Hull","color","sampledPoints","pathSimplification","curveFittingTolerance","width","height","arrayPoints","pt","concaveHull","concaveman","points","tolerance","simplify","simplifiedHullPoints","segments","edgeTypes","isClosedFreeShape","nextStartIndex","i","start","end","startSides","endSides","doShareSide","side","isEdgeOnBorder","pathSegEdgeArrangement","currInd","nextInd","type","edgeInds","ptInd","curveRunPoints","leftTangent","b","rightTangent","value","fitted","c1","c2","fit","sides","maxX","maxY","a","data","firstCurve","ImageTrace","imageData","palette","options","pathSimplificationTolerance","minHullDistance","pixelGridStepSize","debugPointRadius","seen","c","key","hull","backgroundColor","svg","r","g","fontSize","segment","mid","fileName","svgText","blob","url","maskPoints","pointCloud","clouds","threshold","thresholdSq","cellSize","grid","p","cx","cy","visited","cloud","queue","qi","idx","gx","gy","bucket","nbIdx","q","dx","dy","stride","index","cross2","o","pointsEqual","createConvexHullPoints","sorted","unique","point","lower","upper"],"mappings":"8lBAAO,SAASA,CAAAA,CAAGC,CAAAA,CAAWC,CAAAA,CAAY,CAAA,CAAW,CACpD,IAAMC,CAAAA,CAAM,EAAA,EAAMD,CAAAA,CAClB,OAAA,CAAQ,IAAA,CAAK,KAAA,CAAMD,CAAAA,CAAIE,CAAG,CAAA,CAAIA,CAAAA,EAAK,QAAA,EACpC,KCKMC,CAAAA,CAAU,CAAC,CAAE,CAAA,CAAAH,CAAAA,CAAG,CAAA,CAAAI,CAAE,CAAA,GAAY,CAACJ,CAAAA,CAAGI,CAAC,CAAA,CACnCC,CAAAA,CAAU,CAAC,CAACL,CAAAA,CAAGI,CAAC,CAAA,IAAiB,CAAE,CAAA,CAAAJ,CAAAA,CAAG,CAAA,CAAAI,CAAE,CAAA,CAAA,CACjCE,CAAAA,CAAN,MAAMC,CAAK,CAQjB,WAAA,CACQC,CAAAA,CACSC,CAAAA,CACAC,CAAAA,CACAC,CAAAA,CACAC,EACAC,CAAAA,CACf,CANM,IAAA,CAAA,KAAA,CAAAL,CAAAA,CACS,IAAA,CAAA,aAAA,CAAAC,CAAAA,CACA,IAAA,CAAA,kBAAA,CAAAC,CAAAA,CACA,IAAA,CAAA,qBAAA,CAAAC,CAAAA,CACA,IAAA,CAAA,KAAA,CAAAC,CAAAA,CACA,IAAA,CAAA,MAAA,CAAAC,CAAAA,CAEhB,IAAA,CAAK,KAAA,CAAQL,EACb,IAAA,CAAK,KAAA,CAAQI,CAAAA,CACb,IAAA,CAAK,MAAA,CAASC,CAAAA,CACd,IAAA,CAAK,qBAAA,CAAwBF,CAAAA,CAK7B,IAAMG,CAAAA,CAAcL,CAAAA,CAAc,GAAA,CAAIM,CAAAA,EAAM,CAACA,CAAAA,CAAG,EAAGA,CAAAA,CAAG,CAAC,CAAC,CAAA,CAClDC,CAAAA,CAAcC,kBAAAA,CAAWH,CAAAA,CAAaP,CAAAA,CAAK,SAAA,CAAW,CAAC,CAAA,CAAE,GAAA,CAC9D,CAAC,CAACP,CAAAA,CAAGI,CAAC,KAAO,CACZ,CAAA,CAAAJ,CAAAA,CACA,CAAA,CAAAI,CACD,CAAA,CACD,CAAA,CAEA,IAAA,CAAK,UAAA,CAAa,IAAA,CAAK,YAAA,CAAaY,CAAAA,CAAaN,CAAkB,CAAA,CAInE,IAAA,CAAK,OAAA,CAAU,KAAK,UAAA,CAAW,MAAA,EAAU,CAAA,CAErC,IAAA,CAAK,OAAA,GACR,IAAA,CAAK,YAAA,CAAe,IAAA,CAAK,kBAAA,CAAmB,IAAA,CAAK,UAAU,CAAA,EAE7D,CAxCA,OAAO,SAAA,CAAY,CAAA,CAEV,UAAA,CACA,YAAA,CAEA,OAAA,CAwCT,YAAA,CAAaQ,CAAAA,CAAgBC,CAAAA,CAA2B,CACvD,OAAOC,kBAAAA,CAASF,CAAAA,CAAQC,CAAAA,CAAW,IAAI,CACxC,CAEA,kBAAA,CAAmBE,CAAAA,CAA6C,CAC/D,IAAMC,CAAAA,CAA0B,EAAC,CAE3B,CAAA,CAAID,CAAAA,CAAqB,MAAA,CAEzBE,CAAAA,CAA+B,IAAI,KAAA,CAAM,CAAC,CAAA,CAC5CC,CAAAA,CAAoB,IAAA,CACpBC,CAAAA,CAAiB,EAAA,CACrB,QAASC,CAAAA,CAAI,CAAA,CAAGA,CAAAA,CAAI,CAAA,CAAGA,CAAAA,EAAAA,CAAK,CAC3B,IAAIC,CAAAA,CAAQN,CAAAA,CAAqBK,CAAC,CAAA,CAC9BE,CAAAA,CAAMP,CAAAA,CAAAA,CAAsBK,CAAAA,CAAI,CAAA,EAAK,CAAC,EACpCG,CAAAA,CAAa,IAAA,CAAK,gBAAA,CAAiBF,CAAK,CAAA,CACxCG,CAAAA,CAAW,IAAA,CAAK,gBAAA,CAAiBF,CAAG,CAAA,CACpCG,CAAAA,CAAcF,CAAAA,CAAW,IAAA,CAAKG,CAAAA,EACnCF,CAAAA,CAAS,QAAA,CAASE,CAAI,CACvB,CAAA,CAEIH,CAAAA,CAAW,MAAA,CAAS,CAAA,GACvBR,CAAAA,CAAqBK,CAAC,CAAA,CAAIC,CAAAA,CAAQ,IAAA,CAAK,SAAA,CACtCA,CAAAA,CACAE,CACD,CAAA,CAAA,CACGC,CAAAA,CAAS,MAAA,CAAS,IACrBT,CAAAA,CAAAA,CAAsBK,CAAAA,CAAI,CAAA,EAAK,CAAC,CAAA,CAAIE,CAAAA,CAAM,IAAA,CAAK,SAAA,CAC9CA,CAAAA,CACAE,CACD,CAAA,CAAA,CAGD,IAAMG,CAAAA,CACLJ,CAAAA,CAAW,MAAA,CAAS,CAAA,EAAKC,EAAS,MAAA,CAAS,CAAA,EAAKC,CAAAA,CACjDR,CAAAA,CAAUG,CAAC,CAAA,CAAIO,CAAAA,CAAAA,CAAAA,CAAAA,CAAAA,CAIXA,CAAAA,GAEHT,CAAAA,CAAoB,KAAA,CAEhBC,CAAAA,GAAmB,EAAA,GAAIA,CAAAA,CAAiBC,CAAAA,CAAAA,EAE9C,CACID,CAAAA,GAAmB,KAAIA,CAAAA,CAAiB,CAAA,CAAA,CAI5C,IAAMS,CAAAA,CAGA,CAAC,CAAE,IAAA,CAAMX,CAAAA,CAAUE,CAAc,CAAA,CAAG,QAAA,CAAU,EAAG,CAAC,CAAA,CACxD,IAAA,IAASC,CAAAA,CAAID,CAAAA,CAAgBC,CAAAA,CAAID,CAAAA,CAAiB,CAAA,CAAGC,CAAAA,EAAAA,CAAK,CACzD,IAAIS,CAAAA,CAAUT,CAAAA,CAAI,CAAA,CACdU,CAAAA,CAAAA,CAAWV,CAAAA,CAAI,CAAA,EAAK,CAAA,CAExB,GACC,KAAK,WAAA,CACJL,CAAAA,CAAqBc,CAAO,CAAA,CAC5Bd,CAAAA,CAAqBe,CAAO,CAC7B,CAAA,CAEA,SAIAF,CAAAA,CAAuBA,CAAAA,CAAuB,MAAA,CAAS,CAAC,CAAA,CACjD,QAAA,CAAS,IAAA,CAAKC,CAAO,CAAA,CAGzBA,CAAAA,GAAY,CAAA,CAAI,CAAA,EAAKZ,CAAAA,CAAUY,CAAO,CAAA,GAAMZ,CAAAA,CAAUa,CAAO,CAAA,EAChEF,CAAAA,CAAuB,IAAA,CAAK,CAC3B,IAAA,CAAMX,CAAAA,CAAUa,CAAO,EACvB,QAAA,CAAU,EACX,CAAC,EACH,CAGA,IAAA,GAAS,CAAE,IAAA,CAAAC,CAAAA,CAAM,QAAA,CAAAC,CAAS,CAAA,GAAKJ,CAAAA,CAAwB,CACtD,GAAIG,IAAS,CAAA,CAAsB,CAClC,IAAA,IAASE,CAAAA,IAASD,CAAAA,CACjBhB,CAAAA,CAAS,IAAA,CAAK,CACb,IAAA,CAAAe,CAAAA,CACA,MAAA,CAAQ,CACPhB,CAAAA,CAAqBkB,CAAK,CAAA,CAC1BlB,CAAAA,CAAAA,CAAsBkB,EAAQ,CAAA,EAAK,CAAC,CACrC,CACD,CAAC,CAAA,CAEF,QACD,CAIA,GAAID,CAAAA,CAAS,MAAA,GAAW,CAAA,CAAG,CAG1BhB,CAAAA,CAAS,IAAA,CAAK,CACb,OACA,MAAA,CAAQ,CACPD,CAAAA,CAAqBiB,CAAAA,CAAS,CAAC,CAAC,CAAA,CAChCjB,CAAAA,CAAAA,CAAsBiB,CAAAA,CAAS,CAAC,CAAA,CAAI,CAAA,EAAK,CAAC,CAC3C,CACD,CAAC,EACD,QACD,CAEA,IAAME,CAAAA,CAAiBF,CAAAA,CAAS,GAAA,CAAIZ,CAAAA,EAAKL,CAAAA,CAAqBK,CAAC,CAAC,CAAA,CAEhEc,CAAAA,CAAe,IAAA,CACdnB,CAAAA,CAAAA,CAAsBiB,CAAAA,CAASA,CAAAA,CAAS,MAAA,CAAS,CAAC,CAAA,CAAI,CAAA,EAAK,CAAC,CAC7D,CAAA,CAGA,IAAMG,CAAAA,CAAcjB,CAAAA,CACRkB,YAAA,CAAA,aAAA,CACTvC,CAAAA,CAAQqC,CAAAA,CAAe,CAAC,CAAC,CAAA,CACzBrC,EAAQqC,CAAAA,CAAeA,CAAAA,CAAe,MAAA,CAAS,CAAC,CAAC,CACjD,CAAA,CACSE,YAAA,CAAA,aAAA,CACTvC,CAAAA,CAAQqC,CAAAA,CAAe,CAAC,CAAC,CAAA,CACzBrC,CAAAA,CAAQqC,CAAAA,CAAe,CAAC,CAAC,CACzB,CAAA,CACGG,CAAAA,CAAenB,CAAAA,CAClBiB,CAAAA,CAAY,GAAA,CAAIG,CAAAA,EAAS,CAACA,CAAK,CAAA,CACtBF,YAAA,CAAA,aAAA,CACTvC,CAAAA,CAAQqC,CAAAA,CAAeA,CAAAA,CAAe,MAAA,CAAS,CAAC,CAAC,CAAA,CACjDrC,CAAAA,CAAQqC,CAAAA,CAAeA,CAAAA,CAAe,MAAA,CAAS,CAAC,CAAC,CACjD,CAAA,CAEGK,CAAAA,CAAiCH,YAAA,CAAA,QAAA,CACtCF,CAAAA,CAAe,GAAA,CAAIrC,CAAO,CAAA,CAC1BsC,CAAAA,CACAE,EACA,IAAA,CAAK,qBACN,CAAA,CAAE,GAAA,CAAI,CAAC,CAAChB,CAAAA,CAAOmB,CAAAA,CAAIC,CAAAA,CAAInB,CAAG,CAAA,IAAO,CAChC,IAAA,CAAA,CAAA,CACA,MAAA,CAAQ,CACPvB,CAAAA,CAAQsB,CAAK,CAAA,CACbtB,CAAAA,CAAQyC,CAAE,CAAA,CACVzC,CAAAA,CAAQ0C,CAAE,CAAA,CACV1C,CAAAA,CAAQuB,CAAG,CACZ,CACD,CAAA,CAAE,CAAA,CAEF,IAAA,IAASoB,CAAAA,IAAOH,CAAAA,CACXG,EAAI,MAAA,CAAO,IAAA,CAAK,CAAC,CAAE,CAAA,CAAAhD,CAAAA,CAAG,CAAA,CAAAI,CAAE,CAAA,GAAM,KAAA,CAAMJ,CAAC,CAAA,EAAK,KAAA,CAAMI,CAAC,CAAC,CAAA,EACrD,QAAQ,GAAA,CACP,CAAA;AAAA,CAAA,CACA,KAAK,KAAA,CACL;AAAA,CAAA,CACAoC,CAAAA,CACA;AAAA,CAAA,CACAC,CAAAA,CACA;AAAA,CAAA,CACAE,CAAAA,CACA;AAAA,CAAA,CACAK,CAAAA,CACA;AAAA,CAAA,CACAR,CAAAA,CAAeA,CAAAA,CAAe,MAAA,CAAS,CAAC,CAAA,CACxC;AAAA,CAAA,CACAA,CAAAA,CAAeA,CAAAA,CAAe,MAAA,CAAS,CAAC,CACzC,CAAA,CAGFlB,CAAAA,CAAS,IAAA,CAAK,GAAGuB,CAAM,EACxB,CAEA,OAAOvB,CACR,CAEQ,eAAA,CAAgBP,CAAAA,CAAmB,CAC1C,OAAO,IAAA,CAAK,gBAAA,CAAiBA,CAAE,CAAA,CAAE,OAAS,CAC3C,CAEQ,gBAAA,CAAiBA,CAAAA,CAA0B,CAClD,IAAMkC,CAAAA,CAAwB,EAAC,CAEzBC,EAAO,IAAA,CAAK,KAAA,CAAQ,CAAA,CACpBC,CAAAA,CAAO,IAAA,CAAK,MAAA,CAAS,CAAA,CAE3B,OAAI,KAAK,GAAA,CAAIpC,CAAAA,CAAG,CAAA,CAAI,CAAC,GAAK,EAAA,EAAKkC,CAAAA,CAAM,IAAA,CAAA,CAAsB,CAAA,CACvD,KAAK,GAAA,CAAIlC,CAAAA,CAAG,CAAA,CAAImC,CAAI,CAAA,EAAK,EAAA,EAAKD,CAAAA,CAAM,IAAA,CAAA,CAAuB,EAC3D,IAAA,CAAK,GAAA,CAAIlC,CAAAA,CAAG,CAAA,CAAI,CAAC,CAAA,EAAK,EAAA,EAAKkC,CAAAA,CAAM,IAAA,CAAA,CAAqB,EACtD,IAAA,CAAK,GAAA,CAAIlC,CAAAA,CAAG,CAAA,CAAIoC,CAAI,CAAA,EAAK,EAAA,EAAKF,CAAAA,CAAM,MAAwB,CAAA,CAEzDA,CACR,CAEQ,SAAA,CAAU,CAAE,CAAA,CAAAjD,CAAAA,CAAG,CAAA,CAAAI,CAAE,EAAS6C,CAAAA,CAA6B,CAC9D,IAAMlC,CAAAA,CAAK,CAAE,CAAA,CAAAf,CAAAA,CAAG,CAAA,CAAAI,CAAE,CAAA,CAClB,OAAI6C,CAAAA,CAAM,QAAA,CAAA,CAA0B,IAAGlC,CAAAA,CAAG,CAAA,CAAI,CAAA,CAAA,CAC1CkC,CAAAA,CAAM,UAA2B,CAAA,GAAGlC,CAAAA,CAAG,CAAA,CAAI,IAAA,CAAK,KAAA,CAAA,CAChDkC,CAAAA,CAAM,QAAA,CAAA,CAAyB,CAAA,GAAGlC,EAAG,CAAA,CAAI,CAAA,CAAA,CACzCkC,CAAAA,CAAM,QAAA,CAAA,CAA4B,IAAGlC,CAAAA,CAAG,CAAA,CAAI,IAAA,CAAK,MAAA,CAAA,CAC9CA,CACR,CAEQ,WAAA,CAAYqC,CAAAA,CAASV,CAAAA,CAAkB,CAC9C,OAAOU,CAAAA,CAAE,CAAA,GAAMV,EAAE,CAAA,EAAKU,CAAAA,CAAE,CAAA,GAAMV,CAAAA,CAAE,CACjC,CAEA,WAAA,EAAsB,CACrB,GAAI,CAAC,IAAA,CAAK,YAAA,CAAc,OAAO,EAAA,CAE/B,IAAIW,CAAAA,CAAiB,EAAC,CAEhBC,EAAa,IAAA,CAAK,YAAA,CAAa,CAAC,CAAA,CACtCD,EAAK,IAAA,CACJ,CAAA,EAAA,EAAKtD,CAAAA,CAAGuD,CAAAA,CAAW,OAAO,CAAC,CAAA,CAAE,CAAC,CAAC,CAAA,CAAA,EAAIvD,CAAAA,CAAGuD,CAAAA,CAAW,MAAA,CAAO,CAAC,CAAA,CAAE,CAAC,CAAC,CAAA,CAC9D,EAEA,IAAA,GAAS,CAAE,IAAA,CAAAjB,CAAAA,CAAM,OAAAnB,CAAO,CAAA,GAAK,IAAA,CAAK,YAAA,CAC7BA,CAAAA,CAAO,IAAA,CAAKH,CAAAA,EAAM,KAAA,CAAMA,EAAG,CAAC,CAAC,CAAA,EAChC,OAAA,CAAQ,IACP,MAAA,CACAsB,CAAAA,GAAS,CAAA,CACTnB,CAAAA,CAAO,MACR,CAAA,CACDmC,CAAAA,CAAK,IAAA,CACJhB,CAAAA,GAAS,CAAA,CACN,CAAA,EAAA,EAAKtC,CAAAA,CAAGmB,CAAAA,CAAO,CAAC,CAAA,CAAE,CAAC,CAAC,CAAA,CAAA,EAAInB,EAAGmB,CAAAA,CAAO,CAAC,CAAA,CAAE,CAAC,CAAC,CAAA,EAAA,EACpCnB,CAAAA,CAAImB,CAAAA,CAAO,CAAC,CAAA,CAAW,CAAC,CAAC,CAAA,CAAA,EAAInB,EAC9BmB,CAAAA,CAAO,CAAC,CAAA,CAAW,CACrB,CAAC,CAAA,EAAA,EACEnB,CAAAA,CAAImB,CAAAA,CAAO,CAAC,EAAW,CAAC,CAAC,CAAA,CAAA,EAAInB,CAAAA,CAC9BmB,CAAAA,CAAO,CAAC,CAAA,CAAW,CACrB,CAAC,CAAA,CAAA,CACDmB,CAAAA,GAAS,CAAA,CACT,CAAA,EAAA,EAAKnB,EAAO,CAAC,CAAA,CAAE,CAAC,CAAA,CAAA,EAAInB,EAAGmB,CAAAA,CAAO,CAAC,CAAA,CAAE,CAAC,CAAC,CAAA,CAAA,CACnC,EACJ,CAAA,CAGD,OAAAmC,CAAAA,CAAK,IAAA,CAAK,GAAG,CAAA,CAENA,EAAK,IAAA,CAAK,GAAG,CACrB,CAEA,aAAsB,CAOrB,OAAK,IAAA,CAAK,OAAA,CAET,CAAA,gBAAA,EAAmB,IAAA,CAAK,KAAA,CAAM,CAAC,IAAI,IAAA,CAAK,KAAA,CAAM,CAAC,CAAA,CAAA,EAAI,KAAK,KAAA,CAAM,CAAC,CAAA,MAAA,EACzD,IAAA,CAAK,aAAa,CAAA;AAAA,CAAA,CAHC,EAK3B,CACD,ECxSO,IAAME,CAAAA,CAAN,KAAiB,CACd,KAAA,CACA,MAAA,CACA,qBAAA,CACA,gBACA,iBAAA,CACA,UAAA,CACA,gBACA,gBAAA,CAUT,WAAA,CACCC,EACAC,CAAAA,CACAC,CAAAA,CACC,CACD,GAAI,CAACF,CAAAA,CAAW,MAAM,IAAI,KAAA,CAAM,uBAAuB,CAAA,CACvD,GAAI,CAACC,CAAAA,EAAS,OACb,MAAM,IAAI,MAAM,yCAAyC,CAAA,CAE1D,GAAM,CACL,2BAAA,CAAAE,CAAAA,CACA,qBAAA,CAAAhD,EACA,eAAA,CAAAiD,CAAAA,CAAkB,CAAA,CAClB,iBAAA,CAAAC,EAAoB,CAAA,CACpB,gBAAA,CAAAC,CACD,CAAA,CAAIJ,EAEJ,IAAA,CAAK,KAAA,CAAQF,EAAU,KAAA,CACvB,IAAA,CAAK,OAASA,CAAAA,CAAU,MAAA,CACxB,IAAA,CAAK,qBAAA,CACJ7C,GAAyB,IAAA,CAAK,GAAA,CAAI,IAAA,CAAK,KAAA,CAAO,KAAK,MAAM,CAAA,CAAI,GAAA,CAAA,CAC9D,IAAA,CAAK,gBAAkB,IAAA,CAAK,GAAA,CAAI,EAAGgD,CAA2B,CAAA,CAC9D,KAAK,iBAAA,CAAoB,IAAA,CAAK,GAAA,CAAI,CAAA,CAAG,KAAK,KAAA,CAAME,CAAiB,CAAC,CAAA,CAClE,KAAK,eAAA,CAAkBD,CAAAA,CACvB,IAAA,CAAK,gBAAA,CAAmBE,EAGxB,IAAMC,CAAAA,CAAO,IAAI,GAAA,CACjBN,CAAAA,CAAUA,EAAQ,MAAA,CAAOO,CAAAA,EAAK,CAC7B,IAAMC,EAAM,CAAA,EAAGD,CAAAA,CAAE,CAAC,CAAA,CAAA,EAAIA,EAAE,CAAC,CAAA,CAAA,EAAIA,CAAAA,CAAE,CAAC,GAChC,OAAID,CAAAA,CAAK,IAAIE,CAAG,CAAA,CAAU,OAC1BF,CAAAA,CAAK,GAAA,CAAIE,CAAG,CAAA,CACL,KACR,CAAC,CAAA,CACD,IAAA,CAAK,UAAA,CAAa,KAAK,sBAAA,CAAuBT,CAAAA,CAAWC,CAAO,EACjE,CAKA,eAAA,CAAgBjD,CAAAA,CAAsB,CACrC,OAAO,IAAA,CAAK,WAAW,MAAA,CAAO0D,CAAAA,EAC7B,IAAA,CAAK,WAAA,CAAYA,EAAK,KAAA,CAAO1D,CAAK,CACnC,CACD,CAMA,aAAa2D,CAAAA,CAAiC,CAC7C,IAAMC,CAAAA,CAAgB,CACrB,CAAA,YAAA,EAAe,IAAA,CAAK,KAAK,CAAA,UAAA,EAAa,IAAA,CAAK,MAAM,CAAA,EAAA,CAAA,CACjD,CAAA;AAAA,CACD,EAEA,GAAID,CAAAA,GAAoB,OAAW,CAClC,GAAM,CAAE,CAAA,CAAAE,CAAAA,CAAG,EAAAC,CAAAA,CAAG,CAAA,CAAA5B,CAAE,CAAA,CAAIyB,CAAAA,CACpBC,EAAI,IAAA,CACH,CAAA,aAAA,EAAgB,KAAK,KAAK,CAAA,UAAA,EAAa,IAAA,CAAK,MAAM,2BACxBC,CAAC,CAAA,CAAA,EAAIC,CAAC,CAAA,CAAA,EAAI5B,CAAC,qBACtC,EACD,CAEA,QAAWwB,CAAAA,IAAQ,IAAA,CAAK,WAGvB,GAFAE,CAAAA,CAAI,KAAKF,CAAAA,CAAK,WAAA,EAAa,CAAA,CAG1B,IAAA,CAAK,gBAAA,GAAqB,MAAA,EAC1BA,EAAK,YAAA,GAAiB,MAAA,CACrB,CACD,IAAMK,CAAAA,CAAW,KAAK,KAAA,CAAM,IAAA,CAAK,iBAAmB,CAAC,CAAA,CAErD,QAASC,CAAAA,IAAWN,CAAAA,CAAK,aAAc,CACtC,GAAIM,EAAQ,IAAA,GAAS,CAAA,CAAsB,CAC1C,GAAM,CAAC7C,EAAOC,CAAG,CAAA,CAAI4C,EAAQ,MAAA,CAC7BJ,CAAAA,CAAI,KACH,CAAA,YAAA,EAAerE,CAAAA,CAAG4B,EAAM,CAAC,CAAC,SAAS5B,CAAAA,CAClC4B,CAAAA,CAAM,CACP,CAAC,CAAA,KAAA,EACA,KAAK,gBACN,CAAA;AAAA,CACD,EACAyC,CAAAA,CAAI,IAAA,CACH,CAAA,YAAA,EAAerE,CAAAA,CAAG6B,EAAI,CAAC,CAAC,CAAA,MAAA,EAAS7B,CAAAA,CAAG6B,EAAI,CAAC,CAAC,CAAA,KAAA,EACzC,IAAA,CAAK,iBAAmB,CACzB,CAAA;AAAA,CACD,CAAA,CAEA,IAAM6C,CAAAA,CAAM,CACX,CAAA,CAAG9C,CAAAA,CAAM,CAAA,CAAI,CAAA,CAAIC,CAAAA,CAAI,CAAA,CAAI,CAAA,CACzB,CAAA,CAAGD,CAAAA,CAAM,CAAA,CAAI,CAAA,CAAIC,CAAAA,CAAI,CAAA,CAAI,CAC1B,CAAA,CACAwC,CAAAA,CAAI,IAAA,CACH,CAAA,SAAA,EAAYrE,CAAAA,CAAG0E,CAAAA,CAAI,CAAC,CAAC,CAAA,KAAA,EAAQ1E,CAAAA,CAC5B0E,CAAAA,CAAI,CACL,CAAC,CAAA,oBAAA,EAAuBF,CAAQ,CAAA,mCAAA,CACjC,CAAA,CACA,QACD,CAGA,GAAM,CAAC5C,CAAAA,CAAOmB,CAAAA,CAAIC,CAAAA,CAAInB,CAAG,CAAA,CAAI4C,CAAAA,CAAQ,MAAA,CACrCJ,CAAAA,CAAI,IAAA,CACH,CAAA,YAAA,EAAerE,CAAAA,CAAG4B,CAAAA,CAAM,CAAC,CAAC,CAAA,MAAA,EAAS5B,CAAAA,CAAG4B,CAAAA,CAAM,CAAC,CAAC,CAAA,KAAA,EAC7C,IAAA,CAAK,gBACN,CAAA;AAAA,YAAA,EACgB5B,CAAAA,CAAG+C,CAAAA,CAAG,CAAC,CAAC,CAAA,MAAA,EAAS/C,CAAAA,CAAG+C,CAAAA,CAAG,CAAC,CAAC,CAAA,KAAA,EACvC,IAAA,CAAK,gBAAA,CAAmB,CACzB,CAAA;AAAA,YAAA,EACe/C,CAAAA,CAAGgD,CAAAA,CAAG,CAAC,CAAC,CAAA,MAAA,EAAShD,CAAAA,CAAGgD,CAAAA,CAAG,CAAC,CAAC,CAAA,KAAA,EACvC,IAAA,CAAK,gBAAA,CAAmB,CACzB,CAAA;AAAA,YAAA,EACehD,CAAAA,CAAG6B,CAAAA,CAAI,CAAC,CAAC,CAAA,MAAA,EAAS7B,CAAAA,CAAG6B,CAAAA,CAAI,CAAC,CAAC,CAAA,KAAA,EACzC,IAAA,CAAK,gBAAA,CAAmB,CACzB,CAAA;AAAA,CACF,EACA,IAAM6C,CAAAA,CAAM,CACX,CAAA,CAAG9C,CAAAA,CAAM,EAAI,CAAA,CAAIC,CAAAA,CAAI,EAAI,CAAA,CAAIkB,CAAAA,CAAG,EAAI,CAAA,CAAIC,CAAAA,CAAG,EAAI,CAAA,CAC/C,CAAA,CAAGpB,EAAM,CAAA,CAAI,CAAA,CAAIC,CAAAA,CAAI,CAAA,CAAI,EAAIkB,CAAAA,CAAG,CAAA,CAAI,EAAIC,CAAAA,CAAG,CAAA,CAAI,CAChD,CAAA,CACAqB,CAAAA,CAAI,KACH,CAAA,SAAA,EAAYrE,CAAAA,CAAG0E,EAAI,CAAC,CAAC,QAAQ1E,CAAAA,CAC5B0E,CAAAA,CAAI,CACL,CAAC,CAAA,oBAAA,EAAuBF,CAAQ,CAAA,uBAAA,CACjC,EACD,CACD,CAED,OAAAH,CAAAA,CAAI,IAAA,CAAK,QAAQ,CAAA,CACVA,CAAAA,CAAI,KAAK,EAAE,CACnB,CAOO,WAAA,CAAYM,CAAAA,CAAkBP,EAA+B,CACnE,GAAI,OAAO,QAAA,CAAa,GAAA,EAAe,OAAO,MAAA,CAAW,GAAA,CACxD,MAAM,IAAI,KAAA,CAAM,4CAA4C,CAAA,CAGzDO,CAAAA,CAAS,MAAMA,CAAAA,CAAS,MAAA,CAAS,CAAC,CAAA,CAAE,WAAA,KAAkB,MAAA,GACzDA,CAAAA,EAAY,QAEb,IAAMC,CAAAA,CAAU,KAAK,YAAA,CAAaR,CAAe,CAAA,CAC3CS,CAAAA,CAAO,IAAI,IAAA,CAAK,CAACD,CAAO,CAAA,CAAG,CAChC,KAAM,6BACP,CAAC,EACKE,CAAAA,CAAM,GAAA,CAAI,gBAAgBD,CAAI,CAAA,CAE9BxB,EAAI,QAAA,CAAS,aAAA,CAAc,GAAG,CAAA,CACpCA,CAAAA,CAAE,MAAM,OAAA,CAAU,MAAA,CAClBA,EAAE,IAAA,CAAOyB,CAAAA,CACTzB,EAAE,QAAA,CAAWsB,CAAAA,CAEb,SAAS,IAAA,CAAK,WAAA,CAAYtB,CAAC,CAAA,CAC3BA,CAAAA,CAAE,OAAM,CACR,QAAA,CAAS,KAAK,WAAA,CAAYA,CAAC,EAG3B,UAAA,CAAW,IAAM,GAAA,CAAI,eAAA,CAAgByB,CAAG,CAAA,CAAG,GAAK,EACjD,CAEQ,sBAAA,CACPrB,EACAC,CAAAA,CACS,CACT,OAAOA,CAAAA,CACL,GAAA,CAAIjD,GAAS,IAAA,CAAK,mBAAA,CAAoBgD,EAAWhD,CAAK,CAAC,EACvD,IAAA,EAAK,CACL,OAAO0D,CAAAA,EAAQA,CAAAA,CAAK,OAAO,CAC9B,CAEQ,oBACPV,CAAAA,CACAhD,CAAAA,CACS,CACT,IAAMsE,CAAAA,CAAa,KAAK,oBAAA,CAAqBtB,CAAAA,CAAWhD,CAAK,CAAA,CAE7D,OADoB,KAAK,mBAAA,CAAoBsE,CAAU,EACpC,GAAA,CAClBC,CAAAA,EACC,IAAIzE,CAAAA,CACHE,EACAuE,CAAAA,CACA,IAAA,CAAK,gBACL,IAAA,CAAK,qBAAA,CACL,KAAK,KAAA,CACL,IAAA,CAAK,MACN,CACF,CACD,CAEQ,mBAAA,CAAoB7D,CAAAA,CAA0B,CACrD,IAAM8D,CAAAA,CAAmB,EAAC,CAC1B,GAAI9D,EAAO,MAAA,GAAW,CAAA,CAAG,OAAO8D,CAAAA,CAIhC,IAAMC,EAAY,IAAA,CAAK,GAAA,CAAI,EAAG,IAAA,CAAK,eAAe,EAClD,GAAI,IAAA,CAAK,kBAAoBA,CAAAA,CAC5B,MAAM,IAAI,KAAA,CACT,qEACD,EAID,IAAMC,CAAAA,CAAcD,CAAAA,CAAYA,CAAAA,CAG1BE,EAAWF,CAAAA,CACXG,CAAAA,CAAO,IAAI,GAAA,CACjB,IAAA,IAAS1D,EAAI,CAAA,CAAGA,CAAAA,CAAIR,EAAO,MAAA,CAAQQ,CAAAA,EAAAA,CAAK,CACvC,IAAM2D,CAAAA,CAAInE,EAAOQ,CAAC,CAAA,CACZ4D,EAAK,IAAA,CAAK,KAAA,CAAMD,EAAE,CAAA,CAAIF,CAAQ,EAC9BI,CAAAA,CAAK,IAAA,CAAK,MAAMF,CAAAA,CAAE,CAAA,CAAIF,CAAQ,CAAA,CAC9BlB,CAAAA,CAAM,GAAGqB,CAAE,CAAA,CAAA,EAAIC,CAAE,CAAA,CAAA,CAAA,CAEtBH,CAAAA,CAAK,IAAInB,CAAG,CAAA,EAAKmB,EAAK,GAAA,CAAInB,CAAAA,CAAK,EAAE,EAAE,GAAA,CAAIA,CAAG,GAAI,IAAA,CAAKvC,CAAC,EACtD,CAEA,IAAM8D,EAAU,IAAI,UAAA,CAAWtE,EAAO,MAAM,CAAA,CAE5C,QAASQ,CAAAA,CAAI,CAAA,CAAGA,EAAIR,CAAAA,CAAO,MAAA,CAAQQ,IAAK,CACvC,GAAI8D,EAAQ9D,CAAC,CAAA,CAAG,SAGhB,IAAM+D,CAAAA,CAAgB,EAAC,CACjBC,CAAAA,CAAkB,EAAC,CACrBC,CAAAA,CAAK,EAIT,IAHAD,CAAAA,CAAM,KAAKhE,CAAC,CAAA,CACZ8D,EAAQ9D,CAAC,CAAA,CAAI,CAAA,CAENiE,CAAAA,CAAKD,EAAM,MAAA,EAAQ,CACzB,IAAME,CAAAA,CAAMF,CAAAA,CAAMC,GAAI,CAAA,CAChBN,CAAAA,CAAInE,EAAO0E,CAAG,CAAA,CACpBH,EAAM,IAAA,CAAKJ,CAAC,EAIZ,IAAMC,CAAAA,CAAK,KAAK,KAAA,CAAMD,CAAAA,CAAE,EAAIF,CAAQ,CAAA,CAC9BI,EAAK,IAAA,CAAK,KAAA,CAAMF,EAAE,CAAA,CAAIF,CAAQ,EACpC,IAAA,IAASU,CAAAA,CAAKP,EAAK,CAAA,CAAGO,CAAAA,EAAMP,EAAK,CAAA,CAAGO,CAAAA,EAAAA,CACnC,QAASC,CAAAA,CAAKP,CAAAA,CAAK,EAAGO,CAAAA,EAAMP,CAAAA,CAAK,CAAA,CAAGO,CAAAA,EAAAA,CAAM,CACzC,IAAM7B,CAAAA,CAAM,GAAG4B,CAAE,CAAA,CAAA,EAAIC,CAAE,CAAA,CAAA,CACjBC,CAAAA,CAASX,EAAK,GAAA,CAAInB,CAAG,EAC3B,GAAK8B,CAAAA,CACL,QAAWC,CAAAA,IAASD,CAAAA,CAAQ,CAC3B,GAAIP,CAAAA,CAAQQ,CAAK,CAAA,CAAG,SACpB,IAAMC,CAAAA,CAAI/E,CAAAA,CAAO8E,CAAK,CAAA,CAChBE,CAAAA,CAAKD,EAAE,CAAA,CAAIZ,CAAAA,CAAE,EACbc,CAAAA,CAAKF,CAAAA,CAAE,EAAIZ,CAAAA,CAAE,CAAA,CAKf,KAAK,GAAA,CAAIa,CAAE,EAAI,IAAA,CAAK,GAAA,CAAIC,CAAE,CAAA,CAAIlB,EAAY,CAAA,EAI1CiB,CAAAA,CAAKA,EAAKC,CAAAA,CAAKA,CAAAA,EAAMjB,IACxBM,CAAAA,CAAQQ,CAAK,EAAI,CAAA,CACjBN,CAAAA,CAAM,KAAKM,CAAK,CAAA,EAElB,CACD,CAEF,CAEIP,EAAM,MAAA,EAAQT,CAAAA,CAAO,KAAKS,CAAK,EACpC,CAEA,OAAOT,CACR,CAEQ,oBAAA,CACPxB,CAAAA,CACAhD,EACS,CACT,GAAM,CAAE,IAAA,CAAA6C,CAAAA,CAAM,MAAAzC,CAAAA,CAAO,MAAA,CAAAC,CAAO,CAAA,CAAI2C,CAAAA,CAC1BtC,EAAiB,EAAC,CAClBkF,CAAAA,CAAS,IAAA,CAAK,kBAEpB,IAAA,IAAShG,CAAAA,CAAI,EAAGA,CAAAA,CAAIS,CAAAA,CAAQT,GAAKgG,CAAAA,CAChC,IAAA,IAASpG,EAAI,CAAA,CAAGA,CAAAA,CAAIY,EAAOZ,CAAAA,EAAKoG,CAAAA,CAAQ,CACvC,IAAMC,CAAAA,CAAAA,CAASjG,EAAIQ,CAAAA,CAAQZ,CAAAA,EAAK,EAC5B,IAAA,CAAK,YAAA,CAAaqD,EAAMgD,CAAAA,CAAO7F,CAAK,GACvCU,CAAAA,CAAO,IAAA,CAAK,CAAE,CAAA,CAAAlB,CAAAA,CAAG,EAAAI,CAAE,CAAC,EAEtB,CAED,OAAOc,CACR,CAEQ,YAAA,CACPmC,EACAgD,CAAAA,CACA7F,CAAAA,CACU,CACV,OACC6C,EAAKgD,CAAAA,CAAQ,CAAC,IAAM,CAAA,EACpBhD,CAAAA,CAAKgD,CAAK,CAAA,GAAM7F,CAAAA,CAAM,GACtB6C,CAAAA,CAAKgD,CAAAA,CAAQ,CAAC,CAAA,GAAM7F,CAAAA,CAAM,GAC1B6C,CAAAA,CAAKgD,CAAAA,CAAQ,CAAC,CAAA,GAAM7F,CAAAA,CAAM,CAE5B,CAEQ,WAAA,CAAYsC,EAAWC,CAAAA,CAAoB,CAClD,OAAOD,CAAAA,CAAG,CAAA,GAAMC,EAAG,CAAA,EAAKD,CAAAA,CAAG,IAAMC,CAAAA,CAAG,CAAA,EAAKD,EAAG,CAAA,GAAMC,CAAAA,CAAG,CACtD,CACD,ECrVA,SAASuD,CAAAA,CAAOC,CAAAA,CAASnD,CAAAA,CAASV,CAAAA,CAAiB,CAClD,OAAA,CAAQU,CAAAA,CAAE,EAAImD,CAAAA,CAAE,CAAA,GAAM7D,EAAE,CAAA,CAAI6D,CAAAA,CAAE,IAAMnD,CAAAA,CAAE,CAAA,CAAImD,EAAE,CAAA,GAAM7D,CAAAA,CAAE,EAAI6D,CAAAA,CAAE,CAAA,CAC3D,CAEA,SAASC,CAAAA,CAAYpD,EAASV,CAAAA,CAAkB,CAC/C,OAAOU,CAAAA,CAAE,CAAA,GAAMV,EAAE,CAAA,EAAKU,CAAAA,CAAE,IAAMV,CAAAA,CAAE,CACjC,CAEO,SAAS+D,CAAAA,CAAuB1B,EAA4B,CAClE,GAAIA,EAAW,MAAA,EAAU,CAAA,CACxB,OAAOA,CAAAA,CAAW,KAAA,EAAM,CAGzB,IAAM2B,EAAS3B,CAAAA,CAAW,IAAA,CAAK,CAAC3B,CAAAA,CAAGV,CAAAA,GAClCU,EAAE,CAAA,GAAMV,CAAAA,CAAE,EAAIU,CAAAA,CAAE,CAAA,CAAIV,EAAE,CAAA,CAAIU,CAAAA,CAAE,EAAIV,CAAAA,CAAE,CACnC,EAEMiE,CAAAA,CAAiB,GACvB,IAAA,IAAWC,CAAAA,IAASF,GACf,CAACC,CAAAA,CAAO,QAAU,CAACH,CAAAA,CAAYG,EAAOA,CAAAA,CAAO,MAAA,CAAS,CAAC,CAAA,CAAGC,CAAK,IAClED,CAAAA,CAAO,IAAA,CAAKC,CAAK,CAAA,CAInB,GAAID,EAAO,MAAA,EAAU,CAAA,CACpB,OAAOA,CAAAA,CAAO,OAAM,CAGrB,IAAME,EAAgB,EAAC,CACvB,QAAWD,CAAAA,IAASD,CAAAA,CAAQ,CAC3B,KACCE,CAAAA,CAAM,QAAU,CAAA,EAChBP,CAAAA,CAAOO,EAAMA,CAAAA,CAAM,MAAA,CAAS,CAAC,CAAA,CAAGA,CAAAA,CAAMA,EAAM,MAAA,CAAS,CAAC,EAAGD,CAAK,CAAA,EAAK,GAEnEC,CAAAA,CAAM,GAAA,GAEPA,CAAAA,CAAM,IAAA,CAAKD,CAAK,EACjB,CAEA,IAAME,CAAAA,CAAgB,GACtB,IAAA,IAAS,CAAA,CAAIH,EAAO,MAAA,CAAS,CAAA,CAAG,CAAA,EAAK,CAAA,CAAG,IAAK,CAC5C,IAAMC,EAAQD,CAAAA,CAAO,CAAC,EACtB,KACCG,CAAAA,CAAM,QAAU,CAAA,EAChBR,CAAAA,CAAOQ,EAAMA,CAAAA,CAAM,MAAA,CAAS,CAAC,CAAA,CAAGA,CAAAA,CAAMA,EAAM,MAAA,CAAS,CAAC,EAAGF,CAAK,CAAA,EAAK,GAEnEE,CAAAA,CAAM,GAAA,GAEPA,CAAAA,CAAM,IAAA,CAAKF,CAAK,EACjB,CAEA,OAAAC,CAAAA,CAAM,GAAA,GACNC,CAAAA,CAAM,GAAA,GAECD,CAAAA,CAAM,MAAA,CAAOC,CAAK,CAC1B","file":"index.cjs","sourcesContent":["export function nf(x: number, precision = 3): string {\r\n\tconst k10 = 10 ** precision;\r\n\treturn (Math.round(x * k10) / k10).toString();\r\n}\r\n","import type { Color, Vec2 } from './types';\r\n\r\nimport concaveman from 'concaveman';\r\nimport simplify from 'simplify-js';\r\nimport * as FitCurve from 'fit-curve';\r\nimport { nf } from './util';\r\nimport { PathSegmentType, PathSegment, BoundarySide } from './types';\r\n\r\nconst vec2Arr = ({ x, y }: Vec2) => [x, y];\r\nconst arr2Vec = ([x, y]: number[]) => ({ x, y });\r\nexport class Hull {\r\n\tstatic concavity = 1;\r\n\r\n\treadonly hullPoints: Vec2[];\r\n\treadonly pathSegments?: PathSegment[];\r\n\r\n\treadonly isValid: boolean;\r\n\r\n\tconstructor(\r\n\t\tpublic color: Color,\r\n\t\tpublic readonly sampledPoints: Vec2[],\r\n\t\tpublic readonly pathSimplification: number,\r\n\t\tpublic readonly curveFittingTolerance: number,\r\n\t\tpublic readonly width: number,\r\n\t\tpublic readonly height: number\r\n\t) {\r\n\t\tthis.color = color;\r\n\t\tthis.width = width;\r\n\t\tthis.height = height;\r\n\t\tthis.curveFittingTolerance = curveFittingTolerance;\r\n\r\n\t\t// const rc = () => Math.round(random() * 255);\r\n\t\t// this.color = { r: rc(), g: rc(), b: 128 };\r\n\r\n\t\tconst arrayPoints = sampledPoints.map(pt => [pt.x, pt.y]);\r\n\t\tconst concaveHull = concaveman(arrayPoints, Hull.concavity, 1).map(\r\n\t\t\t([x, y]) => ({\r\n\t\t\t\tx,\r\n\t\t\t\ty,\r\n\t\t\t})\r\n\t\t);\r\n\r\n\t\tthis.hullPoints = this.reducePoints(concaveHull, pathSimplification);\r\n\t\t// more info:\r\n\t\t// https://github.com/mapbox/concaveman\r\n\r\n\t\tthis.isValid = this.hullPoints.length >= 3;\r\n\r\n\t\tif (this.isValid) {\r\n\t\t\tthis.pathSegments = this.createPathSegments(this.hullPoints);\r\n\t\t}\r\n\t}\r\n\r\n\t/**\r\n\t * Reduces the number of points in a path while maintaining its shape\r\n\t */\r\n\treducePoints(points: Vec2[], tolerance: number): Vec2[] {\r\n\t\treturn simplify(points, tolerance, true);\r\n\t}\r\n\r\n\tcreatePathSegments(simplifiedHullPoints: Vec2[]): PathSegment[] {\r\n\t\tconst segments: PathSegment[] = [];\r\n\r\n\t\tconst n = simplifiedHullPoints.length;\r\n\r\n\t\tconst edgeTypes: PathSegmentType[] = new Array(n);\r\n\t\tlet isClosedFreeShape = true;\r\n\t\tlet nextStartIndex = -1; // finds border point if available for next iteration\r\n\t\tfor (let i = 0; i < n; i++) {\r\n\t\t\tlet start = simplifiedHullPoints[i];\r\n\t\t\tlet end = simplifiedHullPoints[(i + 1) % n];\r\n\t\t\tconst startSides = this.getBoundarySides(start);\r\n\t\t\tconst endSides = this.getBoundarySides(end);\r\n\t\t\tconst doShareSide = startSides.some(side =>\r\n\t\t\t\tendSides.includes(side)\r\n\t\t\t);\r\n\r\n\t\t\tif (startSides.length > 0)\r\n\t\t\t\tsimplifiedHullPoints[i] = start = this.putOnSide(\r\n\t\t\t\t\tstart,\r\n\t\t\t\t\tstartSides\r\n\t\t\t\t);\r\n\t\t\tif (endSides.length > 0)\r\n\t\t\t\tsimplifiedHullPoints[(i + 1) % n] = end = this.putOnSide(\r\n\t\t\t\t\tend,\r\n\t\t\t\t\tendSides\r\n\t\t\t\t);\r\n\r\n\t\t\t// edge i is the edge from pt i to pt i+1\r\n\t\t\tconst isEdgeOnBorder =\r\n\t\t\t\tstartSides.length > 0 && endSides.length > 0 && doShareSide;\r\n\t\t\tedgeTypes[i] = isEdgeOnBorder\r\n\t\t\t\t? PathSegmentType.Line\r\n\t\t\t\t: PathSegmentType.Curve;\r\n\r\n\t\t\tif (isEdgeOnBorder) {\r\n\t\t\t\t// if there is at least one line, the shape can't be a 'free' shape\r\n\t\t\t\tisClosedFreeShape = false;\r\n\r\n\t\t\t\tif (nextStartIndex === -1) nextStartIndex = i; // start of border edge (=== `start`)\r\n\t\t\t}\r\n\t\t}\r\n\t\tif (nextStartIndex === -1) nextStartIndex = 0;\r\n\r\n\t\t// cut points into segment point groups by type, in original order\r\n\t\t// this will become the structure of `segments`\r\n\t\tconst pathSegEdgeArrangement: {\r\n\t\t\ttype: PathSegmentType;\r\n\t\t\tedgeInds: number[];\r\n\t\t}[] = [{ type: edgeTypes[nextStartIndex], edgeInds: [] }];\r\n\t\tfor (let i = nextStartIndex; i < nextStartIndex + n; i++) {\r\n\t\t\tlet currInd = i % n;\r\n\t\t\tlet nextInd = (i + 1) % n;\r\n\r\n\t\t\tif (\r\n\t\t\t\tthis.isSamePoint(\r\n\t\t\t\t\tsimplifiedHullPoints[currInd],\r\n\t\t\t\t\tsimplifiedHullPoints[nextInd]\r\n\t\t\t\t)\r\n\t\t\t) {\r\n\t\t\t\tcontinue;\r\n\t\t\t}\r\n\r\n\t\t\tconst lastSeg =\r\n\t\t\t\tpathSegEdgeArrangement[pathSegEdgeArrangement.length - 1];\r\n\t\t\tlastSeg.edgeInds.push(currInd);\r\n\r\n\t\t\t// change segment type if the next edge type is different\r\n\t\t\tif (currInd !== n - 1 && edgeTypes[currInd] !== edgeTypes[nextInd])\r\n\t\t\t\tpathSegEdgeArrangement.push({\r\n\t\t\t\t\ttype: edgeTypes[nextInd],\r\n\t\t\t\t\tedgeInds: [],\r\n\t\t\t\t});\r\n\t\t}\r\n\r\n\t\t// convert edge arrangement into lines and curves\r\n\t\tfor (let { type, edgeInds } of pathSegEdgeArrangement) {\r\n\t\t\tif (type === PathSegmentType.Line) {\r\n\t\t\t\tfor (let ptInd of edgeInds) {\r\n\t\t\t\t\tsegments.push({\r\n\t\t\t\t\t\ttype,\r\n\t\t\t\t\t\tpoints: [\r\n\t\t\t\t\t\t\tsimplifiedHullPoints[ptInd],\r\n\t\t\t\t\t\t\tsimplifiedHullPoints[(ptInd + 1) % n],\r\n\t\t\t\t\t\t],\r\n\t\t\t\t\t});\r\n\t\t\t\t}\r\n\t\t\t\tcontinue;\r\n\t\t\t}\r\n\r\n\t\t\t// type === 'curve':\r\n\r\n\t\t\tif (edgeInds.length === 1) {\r\n\t\t\t\t// this curve has to be a small corner or a spanning rectangle\r\n\t\t\t\t// render as a line and continue\r\n\t\t\t\tsegments.push({\r\n\t\t\t\t\ttype: PathSegmentType.Line,\r\n\t\t\t\t\tpoints: [\r\n\t\t\t\t\t\tsimplifiedHullPoints[edgeInds[0]],\r\n\t\t\t\t\t\tsimplifiedHullPoints[(edgeInds[0] + 1) % n],\r\n\t\t\t\t\t],\r\n\t\t\t\t});\r\n\t\t\t\tcontinue;\r\n\t\t\t}\r\n\r\n\t\t\tconst curveRunPoints = edgeInds.map(i => simplifiedHullPoints[i]);\r\n\t\t\t// edges go to pt i + 1 so also add the next point\r\n\t\t\tcurveRunPoints.push(\r\n\t\t\t\tsimplifiedHullPoints[(edgeInds[edgeInds.length - 1] + 1) % n]\r\n\t\t\t);\r\n\r\n\t\t\t// open curve path with > 2 points\r\n\t\t\tconst leftTangent = isClosedFreeShape\r\n\t\t\t\t? FitCurve.createTangent(\r\n\t\t\t\t\t\tvec2Arr(curveRunPoints[1]),\r\n\t\t\t\t\t\tvec2Arr(curveRunPoints[curveRunPoints.length - 2])\r\n\t\t\t\t  )\r\n\t\t\t\t: FitCurve.createTangent(\r\n\t\t\t\t\t\tvec2Arr(curveRunPoints[1]),\r\n\t\t\t\t\t\tvec2Arr(curveRunPoints[0])\r\n\t\t\t\t  );\r\n\t\t\tconst rightTangent = isClosedFreeShape\r\n\t\t\t\t? leftTangent.map(value => -value)\r\n\t\t\t\t: FitCurve.createTangent(\r\n\t\t\t\t\t\tvec2Arr(curveRunPoints[curveRunPoints.length - 2]),\r\n\t\t\t\t\t\tvec2Arr(curveRunPoints[curveRunPoints.length - 1])\r\n\t\t\t\t  );\r\n\r\n\t\t\tconst fitted: PathSegment[] = FitCurve.fitCubic(\r\n\t\t\t\tcurveRunPoints.map(vec2Arr),\r\n\t\t\t\tleftTangent,\r\n\t\t\t\trightTangent,\r\n\t\t\t\tthis.curveFittingTolerance\r\n\t\t\t).map(([start, c1, c2, end]) => ({\r\n\t\t\t\ttype: PathSegmentType.Curve,\r\n\t\t\t\tpoints: [\r\n\t\t\t\t\tarr2Vec(start),\r\n\t\t\t\t\tarr2Vec(c1),\r\n\t\t\t\t\tarr2Vec(c2),\r\n\t\t\t\t\tarr2Vec(end),\r\n\t\t\t\t],\r\n\t\t\t}));\r\n\r\n\t\t\tfor (let fit of fitted) {\r\n\t\t\t\tif (fit.points.some(({ x, y }) => isNaN(x) || isNaN(y)))\r\n\t\t\t\t\tconsole.log(\r\n\t\t\t\t\t\t'NaN detected:\\n',\r\n\t\t\t\t\t\tthis.color,\r\n\t\t\t\t\t\t'\\n',\r\n\t\t\t\t\t\tcurveRunPoints,\r\n\t\t\t\t\t\t'\\n',\r\n\t\t\t\t\t\tleftTangent,\r\n\t\t\t\t\t\t'\\n',\r\n\t\t\t\t\t\trightTangent,\r\n\t\t\t\t\t\t'\\n',\r\n\t\t\t\t\t\tfit,\r\n\t\t\t\t\t\t'\\n',\r\n\t\t\t\t\t\tcurveRunPoints[curveRunPoints.length - 2],\r\n\t\t\t\t\t\t'\\n',\r\n\t\t\t\t\t\tcurveRunPoints[curveRunPoints.length - 1]\r\n\t\t\t\t\t);\r\n\t\t\t}\r\n\r\n\t\t\tsegments.push(...fitted);\r\n\t\t}\r\n\r\n\t\treturn segments;\r\n\t}\r\n\r\n\tprivate isBoundaryPoint(pt: Vec2): boolean {\r\n\t\treturn this.getBoundarySides(pt).length > 0;\r\n\t}\r\n\r\n\tprivate getBoundarySides(pt: Vec2): BoundarySide[] {\r\n\t\tconst sides: BoundarySide[] = [];\r\n\t\tconst eps = 0.5;\r\n\t\tconst maxX = this.width - 1;\r\n\t\tconst maxY = this.height - 1;\r\n\r\n\t\tif (Math.abs(pt.x - 0) <= eps) sides.push(BoundarySide.Left);\r\n\t\tif (Math.abs(pt.x - maxX) <= eps) sides.push(BoundarySide.Right);\r\n\t\tif (Math.abs(pt.y - 0) <= eps) sides.push(BoundarySide.Top);\r\n\t\tif (Math.abs(pt.y - maxY) <= eps) sides.push(BoundarySide.Bottom);\r\n\r\n\t\treturn sides;\r\n\t}\r\n\r\n\tprivate putOnSide({ x, y }: Vec2, sides: BoundarySide[]): Vec2 {\r\n\t\tconst pt = { x, y };\r\n\t\tif (sides.includes(BoundarySide.Left)) pt.x = 0;\r\n\t\tif (sides.includes(BoundarySide.Right)) pt.x = this.width;\r\n\t\tif (sides.includes(BoundarySide.Top)) pt.y = 0;\r\n\t\tif (sides.includes(BoundarySide.Bottom)) pt.y = this.height;\r\n\t\treturn pt;\r\n\t}\r\n\r\n\tprivate isSamePoint(a: Vec2, b: Vec2): boolean {\r\n\t\treturn a.x === b.x && a.y === b.y;\r\n\t}\r\n\r\n\tgetPathData(): string {\r\n\t\tif (!this.pathSegments) return '';\r\n\r\n\t\tlet data: string[] = [];\r\n\r\n\t\tconst firstCurve = this.pathSegments[0];\r\n\t\tdata.push(\r\n\t\t\t`M ${nf(firstCurve.points[0].x)} ${nf(firstCurve.points[0].y)}`\r\n\t\t);\r\n\r\n\t\tfor (let { type, points } of this.pathSegments) {\r\n\t\t\tif (points.some(pt => isNaN(pt.x)))\r\n\t\t\t\tconsole.log(\r\n\t\t\t\t\t'NAN:',\r\n\t\t\t\t\ttype === PathSegmentType.Curve,\r\n\t\t\t\t\tpoints.length\r\n\t\t\t\t);\r\n\t\t\tdata.push(\r\n\t\t\t\ttype === PathSegmentType.Curve\r\n\t\t\t\t\t? `C ${nf(points[1].x)} ${nf(points[1].y)}, ` +\r\n\t\t\t\t\t\t\t`${nf((points[2] as Vec2).x)} ${nf(\r\n\t\t\t\t\t\t\t\t(points[2] as Vec2).y\r\n\t\t\t\t\t\t\t)}, ` +\r\n\t\t\t\t\t\t\t`${nf((points[3] as Vec2).x)} ${nf(\r\n\t\t\t\t\t\t\t\t(points[3] as Vec2).y\r\n\t\t\t\t\t\t\t)}`\r\n\t\t\t\t\t: type === PathSegmentType.Line\r\n\t\t\t\t\t? `L ${points[1].x} ${nf(points[1].y)}`\r\n\t\t\t\t\t: ''\r\n\t\t\t);\r\n\t\t}\r\n\r\n\t\tdata.push(`Z`);\r\n\r\n\t\treturn data.join(' ');\r\n\t}\r\n\r\n\tgetPathElem(): string {\r\n\t\t// if (!this.isValid) return '';\r\n\t\t// return (\r\n\t\t// \t`<path fill=\"rgb(${this.color.r},${this.color.g},${this.color.b})\" ` +\r\n\t\t// \t`d=\"${this.getPathData()}\" />\\n`\r\n\t\t// );\r\n\r\n\t\tif (!this.isValid) return '';\r\n\t\tconst q =\r\n\t\t\t`<path fill=\"rgb(${this.color.r},${this.color.g},${this.color.b})\" ` +\r\n\t\t\t`d=\"${this.getPathData()}\" />\\n`;\r\n\t\treturn q; //.indexOf('NaN') > -1 ? q : '';\r\n\t}\r\n}\r\n\r\nvar seed = 1;\r\nfunction random() {\r\n\tvar x = Math.sin(seed++) * 10000;\r\n\treturn x - Math.floor(x);\r\n}\r\n","import {\r\n\tColor,\r\n\tVec2,\r\n\tImageDataLike,\r\n\tImageTraceOptions,\r\n\tPathSegmentType,\r\n} from './types';\r\nimport { Hull } from './Hull';\r\nimport { nf } from './util';\r\n\r\n/**\r\n * ImageTrace converts raster images to vector graphics by detecting and tracing\r\n * color-matched regions into SVG paths.\r\n */\r\nexport class ImageTrace {\r\n\treadonly width: number;\r\n\treadonly height: number;\r\n\treadonly curveFittingTolerance: number;\r\n\treadonly pathSimpMinDist: number;\r\n\treadonly pixelGridStepSize: number;\r\n\treadonly validHulls: Hull[];\r\n\treadonly minHullDistance: number;\r\n\treadonly debugPointRadius?: number;\r\n\r\n\t/**\r\n\t * Creates a new ImageTrace instance\r\n\t *\r\n\t * @param imageData - The source image data to trace\r\n\t * @param palette - Array of colors to match against\r\n\t * @param options - Configuration options for tracing\r\n\t * @throws {Error} If imageData or palette is invalid\r\n\t */\r\n\tconstructor(\r\n\t\timageData: ImageDataLike,\r\n\t\tpalette: Color[],\r\n\t\toptions: ImageTraceOptions\r\n\t) {\r\n\t\tif (!imageData) throw new Error('imageData is required');\r\n\t\tif (!palette?.length)\r\n\t\t\tthrow new Error('palette must contain at least one color');\r\n\r\n\t\tconst {\r\n\t\t\tpathSimplificationTolerance,\r\n\t\t\tcurveFittingTolerance,\r\n\t\t\tminHullDistance = 3,\r\n\t\t\tpixelGridStepSize = 1,\r\n\t\t\tdebugPointRadius,\r\n\t\t} = options;\r\n\r\n\t\tthis.width = imageData.width;\r\n\t\tthis.height = imageData.height;\r\n\t\tthis.curveFittingTolerance =\r\n\t\t\tcurveFittingTolerance * (Math.max(this.width, this.height) / 1000);\r\n\t\tthis.pathSimpMinDist = Math.max(0, pathSimplificationTolerance);\r\n\t\tthis.pixelGridStepSize = Math.max(1, Math.round(pixelGridStepSize));\r\n\t\tthis.minHullDistance = minHullDistance;\r\n\t\tthis.debugPointRadius = debugPointRadius;\r\n\r\n\t\t// remove duplicate colors (preserve first occurrence)\r\n\t\tconst seen = new Set<string>();\r\n\t\tpalette = palette.filter(c => {\r\n\t\t\tconst key = `${c.r},${c.g},${c.b}`;\r\n\t\t\tif (seen.has(key)) return false;\r\n\t\t\tseen.add(key);\r\n\t\t\treturn true;\r\n\t\t});\r\n\t\tthis.validHulls = this.createHullsFromPalette(imageData, palette);\r\n\t}\r\n\r\n\t/**\r\n\t * Retrieves a hull by its color\r\n\t */\r\n\tgetHullsByColor(color: Color): Hull[] {\r\n\t\treturn this.validHulls.filter(hull =>\r\n\t\t\tthis.colorsMatch(hull.color, color)\r\n\t\t);\r\n\t}\r\n\r\n\t/**\r\n\t * Generates an SVG string representation of the traced image\r\n\t * @param backgroundColor - optional background color to include in the SVG\r\n\t */\r\n\tgetSVGString(backgroundColor?: Color): string {\r\n\t\tconst svg: string[] = [\r\n\t\t\t`<svg width=\"${this.width}\" height=\"${this.height}\" `,\r\n\t\t\t'version=\"1.1\" xmlns=\"http://www.w3.org/2000/svg\">\\n',\r\n\t\t];\r\n\r\n\t\tif (backgroundColor !== undefined) {\r\n\t\t\tconst { r, g, b } = backgroundColor;\r\n\t\t\tsvg.push(\r\n\t\t\t\t`<rect width=\"${this.width}\" height=\"${this.height}\" ` +\r\n\t\t\t\t\t`x=\"0\" y=\"0\" fill=\"rgb(${r},${g},${b})\" stroke=\"none\" />`\r\n\t\t\t);\r\n\t\t}\r\n\r\n\t\tfor (const hull of this.validHulls) {\r\n\t\t\tsvg.push(hull.getPathElem());\r\n\r\n\t\t\tif (\r\n\t\t\t\tthis.debugPointRadius !== undefined &&\r\n\t\t\t\thull.pathSegments !== undefined\r\n\t\t\t) {\r\n\t\t\t\tconst fontSize = Math.round(this.debugPointRadius * 2);\r\n\r\n\t\t\t\tfor (let segment of hull.pathSegments) {\r\n\t\t\t\t\tif (segment.type === PathSegmentType.Line) {\r\n\t\t\t\t\t\tconst [start, end] = segment.points;\r\n\t\t\t\t\t\tsvg.push(\r\n\t\t\t\t\t\t\t`<circle cx=\"${nf(start.x)}\" cy=\"${nf(\r\n\t\t\t\t\t\t\t\tstart.y\r\n\t\t\t\t\t\t\t)}\" r=\"${\r\n\t\t\t\t\t\t\t\tthis.debugPointRadius\r\n\t\t\t\t\t\t\t}\" fill=\"#f006\" stroke=\"#f00\" />\\n`\r\n\t\t\t\t\t\t);\r\n\t\t\t\t\t\tsvg.push(\r\n\t\t\t\t\t\t\t`<circle cx=\"${nf(end.x)}\" cy=\"${nf(end.y)}\" r=\"${\r\n\t\t\t\t\t\t\t\tthis.debugPointRadius / 3\r\n\t\t\t\t\t\t\t}\" fill=\"#f00\" stroke=\"none\" />\\n`\r\n\t\t\t\t\t\t);\r\n\r\n\t\t\t\t\t\tconst mid = {\r\n\t\t\t\t\t\t\tx: start.x / 2 + end.x / 2,\r\n\t\t\t\t\t\t\ty: start.y / 2 + end.y / 2,\r\n\t\t\t\t\t\t};\r\n\t\t\t\t\t\tsvg.push(\r\n\t\t\t\t\t\t\t`<text x=\"${nf(mid.x)}\" y=\"${nf(\r\n\t\t\t\t\t\t\t\tmid.y\r\n\t\t\t\t\t\t\t)}\" style=\"font: bold ${fontSize}px sans-serif; fill: #f00\">L</text>`\r\n\t\t\t\t\t\t);\r\n\t\t\t\t\t\tcontinue;\r\n\t\t\t\t\t}\r\n\r\n\t\t\t\t\t// PathSegmentType.Curve:\r\n\t\t\t\t\tconst [start, c1, c2, end] = segment.points;\r\n\t\t\t\t\tsvg.push(\r\n\t\t\t\t\t\t`<circle cx=\"${nf(start.x)}\" cy=\"${nf(start.y)}\" r=\"${\r\n\t\t\t\t\t\t\tthis.debugPointRadius\r\n\t\t\t\t\t\t}\" fill=\"#0006\" stroke=\"#000\" />\\n` +\r\n\t\t\t\t\t\t\t`<circle cx=\"${nf(c1.x)}\" cy=\"${nf(c1.y)}\" r=\"${\r\n\t\t\t\t\t\t\t\tthis.debugPointRadius / 2\r\n\t\t\t\t\t\t\t}\" fill=\"none\" stroke=\"#000\" />\\n` +\r\n\t\t\t\t\t\t\t`<circle cx=\"${nf(c2.x)}\" cy=\"${nf(c2.y)}\" r=\"${\r\n\t\t\t\t\t\t\t\tthis.debugPointRadius / 2\r\n\t\t\t\t\t\t\t}\" fill=\"none\" stroke=\"#000\" />\\n` +\r\n\t\t\t\t\t\t\t`<circle cx=\"${nf(end.x)}\" cy=\"${nf(end.y)}\" r=\"${\r\n\t\t\t\t\t\t\t\tthis.debugPointRadius / 3\r\n\t\t\t\t\t\t\t}\" fill=\"#000\" stroke=\"none\" />\\n`\r\n\t\t\t\t\t);\r\n\t\t\t\t\tconst mid = {\r\n\t\t\t\t\t\tx: start.x / 4 + end.x / 4 + c1.x / 4 + c2.x / 4,\r\n\t\t\t\t\t\ty: start.y / 4 + end.y / 4 + c1.y / 4 + c2.y / 4,\r\n\t\t\t\t\t};\r\n\t\t\t\t\tsvg.push(\r\n\t\t\t\t\t\t`<text x=\"${nf(mid.x)}\" y=\"${nf(\r\n\t\t\t\t\t\t\tmid.y\r\n\t\t\t\t\t\t)}\" style=\"font: bold ${fontSize}px sans-serif\">C</text>`\r\n\t\t\t\t\t);\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\tsvg.push('</svg>');\r\n\t\treturn svg.join('');\r\n\t}\r\n\r\n\t/**\r\n\t * Creates and initiates a download of the SVG generated by getSVGString.\r\n\t * @param fileName - filename for the downloaded file\r\n\t * @param backgroundColor - optional background color to include in the SVG\r\n\t */\r\n\tpublic downloadSVG(fileName: string, backgroundColor?: Color): void {\r\n\t\tif (typeof document === 'undefined' || typeof window === 'undefined') {\r\n\t\t\tthrow new Error('downloadSVG requires a browser environment');\r\n\t\t}\r\n\r\n\t\tif (fileName.slice(fileName.length - 4).toLowerCase() !== '.svg')\r\n\t\t\tfileName += '.svg';\r\n\r\n\t\tconst svgText = this.getSVGString(backgroundColor);\r\n\t\tconst blob = new Blob([svgText], {\r\n\t\t\ttype: 'image/svg+xml;charset=utf-8',\r\n\t\t});\r\n\t\tconst url = URL.createObjectURL(blob);\r\n\r\n\t\tconst a = document.createElement('a');\r\n\t\ta.style.display = 'none';\r\n\t\ta.href = url;\r\n\t\ta.download = fileName;\r\n\r\n\t\tdocument.body.appendChild(a);\r\n\t\ta.click();\r\n\t\tdocument.body.removeChild(a);\r\n\r\n\t\t// revoke the object URL after 10s to ensure the download finished.\r\n\t\tsetTimeout(() => URL.revokeObjectURL(url), 10000);\r\n\t}\r\n\r\n\tprivate createHullsFromPalette(\r\n\t\timageData: ImageDataLike,\r\n\t\tpalette: Color[]\r\n\t): Hull[] {\r\n\t\treturn palette\r\n\t\t\t.map(color => this.createHullsForColor(imageData, color))\r\n\t\t\t.flat()\r\n\t\t\t.filter(hull => hull.isValid);\r\n\t}\r\n\r\n\tprivate createHullsForColor(\r\n\t\timageData: ImageDataLike,\r\n\t\tcolor: Color\r\n\t): Hull[] {\r\n\t\tconst maskPoints = this.createMaskPointCloud(imageData, color);\r\n\t\tconst pointClouds = this.separatePointClouds(maskPoints);\r\n\t\treturn pointClouds.map(\r\n\t\t\tpointCloud =>\r\n\t\t\t\tnew Hull(\r\n\t\t\t\t\tcolor,\r\n\t\t\t\t\tpointCloud,\r\n\t\t\t\t\tthis.pathSimpMinDist,\r\n\t\t\t\t\tthis.curveFittingTolerance,\r\n\t\t\t\t\tthis.width,\r\n\t\t\t\t\tthis.height\r\n\t\t\t\t)\r\n\t\t);\r\n\t}\r\n\r\n\tprivate separatePointClouds(points: Vec2[]): Vec2[][] {\r\n\t\tconst clouds: Vec2[][] = [];\r\n\t\tif (points.length === 0) return clouds;\r\n\r\n\t\t// Determine an effective threshold that respects both the configured minimum\r\n\t\t// hull distance and the sampling grid step size.\r\n\t\tconst threshold = Math.max(0, this.minHullDistance);\r\n\t\tif (this.pixelGridStepSize > threshold) {\r\n\t\t\tthrow new Error(\r\n\t\t\t\t'Pixel grid step needs to be smaller than the minimum hull distance.'\r\n\t\t\t);\r\n\t\t}\r\n\r\n\t\t// We'll compare squared Euclidean distances for the tight membership test.\r\n\t\tconst thresholdSq = threshold * threshold;\r\n\r\n\t\t// Use a spatial hash (grid) to limit neighbor candidate checks.\r\n\t\tconst cellSize = threshold; // one point of distance per cell is sufficient\r\n\t\tconst grid = new Map<string, number[]>();\r\n\t\tfor (let i = 0; i < points.length; i++) {\r\n\t\t\tconst p = points[i];\r\n\t\t\tconst cx = Math.floor(p.x / cellSize);\r\n\t\t\tconst cy = Math.floor(p.y / cellSize);\r\n\t\t\tconst key = `${cx},${cy}`;\r\n\t\t\t// set grid cell (or initialize first)\r\n\t\t\t(grid.get(key) ?? grid.set(key, []).get(key)!).push(i);\r\n\t\t}\r\n\r\n\t\tconst visited = new Uint8Array(points.length);\r\n\r\n\t\tfor (let i = 0; i < points.length; i++) {\r\n\t\t\tif (visited[i]) continue;\r\n\r\n\t\t\t// Start a new cloud\r\n\t\t\tconst cloud: Vec2[] = [];\r\n\t\t\tconst queue: number[] = [];\r\n\t\t\tlet qi = 0;\r\n\t\t\tqueue.push(i);\r\n\t\t\tvisited[i] = 1;\r\n\r\n\t\t\twhile (qi < queue.length) {\r\n\t\t\t\tconst idx = queue[qi++];\r\n\t\t\t\tconst p = points[idx];\r\n\t\t\t\tcloud.push(p);\r\n\r\n\t\t\t\t// Check neighboring grid cells (only need to check adjacent cells because\r\n\t\t\t\t// cellSize == threshold). This keeps candidate lookups small.\r\n\t\t\t\tconst cx = Math.floor(p.x / cellSize);\r\n\t\t\t\tconst cy = Math.floor(p.y / cellSize);\r\n\t\t\t\tfor (let gx = cx - 1; gx <= cx + 1; gx++) {\r\n\t\t\t\t\tfor (let gy = cy - 1; gy <= cy + 1; gy++) {\r\n\t\t\t\t\t\tconst key = `${gx},${gy}`;\r\n\t\t\t\t\t\tconst bucket = grid.get(key);\r\n\t\t\t\t\t\tif (!bucket) continue;\r\n\t\t\t\t\t\tfor (const nbIdx of bucket) {\r\n\t\t\t\t\t\t\tif (visited[nbIdx]) continue;\r\n\t\t\t\t\t\t\tconst q = points[nbIdx];\r\n\t\t\t\t\t\t\tconst dx = q.x - p.x;\r\n\t\t\t\t\t\t\tconst dy = q.y - p.y;\r\n\r\n\t\t\t\t\t\t\t// Fast reject: use Manhattan distance as a cheap filter\r\n\t\t\t\t\t\t\t// because points are integer grid samples. This avoids one\r\n\t\t\t\t\t\t\t// multiplication for far-away candidates.\r\n\t\t\t\t\t\t\tif (Math.abs(dx) + Math.abs(dy) > threshold * 2)\r\n\t\t\t\t\t\t\t\tcontinue;\r\n\r\n\t\t\t\t\t\t\t// Final check: squared Euclidean distance against threshold^2\r\n\t\t\t\t\t\t\tif (dx * dx + dy * dy <= thresholdSq) {\r\n\t\t\t\t\t\t\t\tvisited[nbIdx] = 1;\r\n\t\t\t\t\t\t\t\tqueue.push(nbIdx);\r\n\t\t\t\t\t\t\t}\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\r\n\t\t\tif (cloud.length) clouds.push(cloud);\r\n\t\t}\r\n\r\n\t\treturn clouds;\r\n\t}\r\n\r\n\tprivate createMaskPointCloud(\r\n\t\timageData: ImageDataLike,\r\n\t\tcolor: Color\r\n\t): Vec2[] {\r\n\t\tconst { data, width, height } = imageData;\r\n\t\tconst points: Vec2[] = [];\r\n\t\tconst stride = this.pixelGridStepSize;\r\n\r\n\t\tfor (let y = 0; y < height; y += stride) {\r\n\t\t\tfor (let x = 0; x < width; x += stride) {\r\n\t\t\t\tconst index = (y * width + x) * 4;\r\n\t\t\t\tif (this.pixelMatches(data, index, color)) {\r\n\t\t\t\t\tpoints.push({ x, y });\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\treturn points;\r\n\t}\r\n\r\n\tprivate pixelMatches(\r\n\t\tdata: ArrayLike<number>,\r\n\t\tindex: number,\r\n\t\tcolor: Color\r\n\t): boolean {\r\n\t\treturn (\r\n\t\t\tdata[index + 3] !== 0 && // alpha\r\n\t\t\tdata[index] === color.r &&\r\n\t\t\tdata[index + 1] === color.g &&\r\n\t\t\tdata[index + 2] === color.b\r\n\t\t);\r\n\t}\r\n\r\n\tprivate colorsMatch(c1: Color, c2: Color): boolean {\r\n\t\treturn c1.r === c2.r && c1.g === c2.g && c1.b === c2.b;\r\n\t}\r\n}\r\n","import type { Vec2 } from './types';\r\n\r\nfunction cross2(o: Vec2, a: Vec2, b: Vec2): number {\r\n\treturn (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);\r\n}\r\n\r\nfunction pointsEqual(a: Vec2, b: Vec2): boolean {\r\n\treturn a.x === b.x && a.y === b.y;\r\n}\r\n\r\nexport function createConvexHullPoints(pointCloud: Vec2[]): Vec2[] {\r\n\tif (pointCloud.length <= 1) {\r\n\t\treturn pointCloud.slice();\r\n\t}\r\n\r\n\tconst sorted = pointCloud.sort((a, b) =>\r\n\t\ta.x === b.x ? a.y - b.y : a.x - b.x\r\n\t);\r\n\r\n\tconst unique: Vec2[] = [];\r\n\tfor (const point of sorted) {\r\n\t\tif (!unique.length || !pointsEqual(unique[unique.length - 1], point)) {\r\n\t\t\tunique.push(point);\r\n\t\t}\r\n\t}\r\n\r\n\tif (unique.length <= 1) {\r\n\t\treturn unique.slice();\r\n\t}\r\n\r\n\tconst lower: Vec2[] = [];\r\n\tfor (const point of unique) {\r\n\t\twhile (\r\n\t\t\tlower.length >= 2 &&\r\n\t\t\tcross2(lower[lower.length - 2], lower[lower.length - 1], point) <= 0\r\n\t\t) {\r\n\t\t\tlower.pop();\r\n\t\t}\r\n\t\tlower.push(point);\r\n\t}\r\n\r\n\tconst upper: Vec2[] = [];\r\n\tfor (let i = unique.length - 1; i >= 0; i--) {\r\n\t\tconst point = unique[i];\r\n\t\twhile (\r\n\t\t\tupper.length >= 2 &&\r\n\t\t\tcross2(upper[upper.length - 2], upper[upper.length - 1], point) <= 0\r\n\t\t) {\r\n\t\t\tupper.pop();\r\n\t\t}\r\n\t\tupper.push(point);\r\n\t}\r\n\r\n\tlower.pop();\r\n\tupper.pop();\r\n\r\n\treturn lower.concat(upper);\r\n}\r\n"]}