@turf/polygonize - npm Package Compare versions

Comparing version

7.2.0

7.3.0

+2

-2

dist/cjs/index.cjs

		@@ -631,7 +631,7 @@ "use strict";Object.defineProperty(exports, "__esModule", {value: true});// index.ts
		}
		var turf_polygonize_default = polygonize;
		var index_default = polygonize;



		exports.default = turf_polygonize_default; exports.polygonize = polygonize;
		exports.default = index_default; exports.polygonize = polygonize;
		//# sourceMappingURL=index.cjs.map

+1

-1

dist/cjs/index.cjs.map

		@@ -1,1 +0,1 @@
		{"version":3,"sources":["/home/runner/work/turf/turf/packages/turf-polygonize/dist/cjs/index.cjs","../../index.ts","../../lib/util.ts","../../lib/Node.ts","../../lib/Edge.ts","../../lib/EdgeRing.ts","../../lib/Graph.ts"],"names":["point","booleanPointInPolygon"],"mappings":"AAAA;ACOA,wCAAkC;ADLlC;AACA;AEFA,uEAAsC;AACtC;AAGA,SAAS,QAAA,CAAS,CAAA,EAAW;AAC3B,EAAA,OAAA,CAAS,EAAA,EAAI,CAAA,EAAA,EAAA,CAA6B,EAAA,EAAI,CAAA,EAAA,GAA4B,CAAC,CAAA;AAC7E;AAgBO,SAAS,gBAAA,CAAiB,EAAA,EAAc,EAAA,EAAc,CAAA,EAAa;AACxE,EAAA,MAAM,IAAA,EAAM,EAAA,CAAG,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA,EACtB,IAAA,EAAM,EAAA,CAAG,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA,EAClB,IAAA,EAAM,CAAA,CAAE,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA,EACjB,IAAA,EAAM,CAAA,CAAE,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA;AAEnB,EAAA,OAAO,QAAA,CAAS,IAAA,EAAM,IAAA,EAAM,IAAA,EAAM,GAAG,CAAA;AACvC;AAWO,SAAS,eAAA,CACd,IAAA,EACA,IAAA,EACA;AACA,EAAA,MAAM,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA,EACxD,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA,EACpD,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA,EACpD,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA;AAEtD,EAAA,OACE,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,GAC1D,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,GAC1D,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,GAC1D,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,CAAA;AAE9D;AAaO,SAAS,gBAAA,CACd,IAAA,EACA,GAAA,EACA;AACA,EAAA,OAAO,GAAA,CAAI,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,KAAA;AAAA,IAAM,CAAC,CAAA,EAAA,GACxC,0DAAA,4BAAsB,CAAO,CAAA,EAAG,IAAI;AAAA,EACtC,CAAA;AACF;AASO,SAAS,gBAAA,CAAiB,MAAA,EAAkB,MAAA,EAAkB;AACnE,EAAA,OAAO,MAAA,CAAO,CAAC,EAAA,IAAM,MAAA,CAAO,CAAC,EAAA,GAAK,MAAA,CAAO,CAAC,EAAA,IAAM,MAAA,CAAO,CAAC,CAAA;AAC1D;AF9DA;AACA;AGpBA,IAAM,KAAA,EAAN,MAAM,MAAK;AAAA,EACT,OAAO,OAAA,CAAQ,WAAA,EAAuB;AACpC,IAAA,OAAO,WAAA,CAAY,IAAA,CAAK,GAAG,CAAA;AAAA,EAC7B;AAAA,EAQA,WAAA,CAAY,WAAA,EAAuB;AACjC,IAAA,IAAA,CAAK,GAAA,EAAK,KAAA,CAAK,OAAA,CAAQ,WAAW,CAAA;AAClC,IAAA,IAAA,CAAK,YAAA,EAAc,WAAA;AACnB,IAAA,IAAA,CAAK,WAAA,EAAa,CAAC,CAAA;AAGnB,IAAA,IAAA,CAAK,WAAA,EAAa,CAAC,CAAA;AACnB,IAAA,IAAA,CAAK,iBAAA,EAAmB,KAAA;AAAA,EAC1B;AAAA,EAEA,eAAA,CAAgB,IAAA,EAAY;AAC1B,IAAA,IAAA,CAAK,WAAA,EAAa,IAAA,CAAK,UAAA,CAAW,MAAA,CAAO,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,IAAA,CAAK,GAAA,IAAO,IAAA,CAAK,IAAA,CAAK,EAAE,CAAA;AAAA,EAC5E;AAAA,EAEA,eAAA,CAAgB,IAAA,EAAY;AAC1B,IAAA,IAAA,CAAK,WAAA,EAAa,IAAA,CAAK,UAAA,CAAW,MAAA,CAAO,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,EAAA,CAAG,GAAA,IAAO,IAAA,CAAK,EAAA,CAAG,EAAE,CAAA;AAAA,EACxE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,YAAA,CAAa,IAAA,EAAY;AACvB,IAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,IAAI,CAAA;AACzB,IAAA,IAAA,CAAK,iBAAA,EAAmB,KAAA;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,cAAA,CAAA,EAAiB;AACf,IAAA,GAAA,CAAI,CAAC,IAAA,CAAK,gBAAA,EAAkB;AAG1B,MAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,CAAC,CAAA,EAAG,CAAA,EAAA,GAAM;AAC7B,QAAA,MAAM,MAAA,EAAQ,CAAA,CAAE,EAAA,EACd,MAAA,EAAQ,CAAA,CAAE,EAAA;AAEZ,QAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,EAAA,GAC9C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EAAI,CAAA;AAE7C,UAAA,OAAO,CAAA;AACT,QAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EAAI,EAAA,GAC7C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,CAAA;AAE9C,UAAA,OAAO,CAAA,CAAA;AAET,QAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,IAAM,EAAA,GAC/C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,IAAM,CAAA,EAC/C;AACA,UAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,EAAA,GAC9C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,CAAA;AAE9C,YAAA,OAAO,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,KAAA,CAAM,WAAA,CAAY,CAAC,CAAA;AACnD,UAAA,OAAO,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,KAAA,CAAM,WAAA,CAAY,CAAC,CAAA;AAAA,QACnD;AAEA,QAAA,MAAM,IAAA,EAAM,gBAAA;AAAA,UACV,IAAA,CAAK,WAAA;AAAA,UACL,KAAA,CAAM,WAAA;AAAA,UACN,KAAA,CAAM;AAAA,QACR,CAAA;AACA,QAAA,GAAA,CAAI,IAAA,EAAM,CAAA,EAAG,OAAO,CAAA;AACpB,QAAA,GAAA,CAAI,IAAA,EAAM,CAAA,EAAG,OAAO,CAAA,CAAA;AAEpB,QAAA,MAAM,GAAA,EACF,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,EAAA,EACtD,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,CAAA,EACxD,GAAA,EACE,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,EAAA,EACtD,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,CAAA;AAE1D,QAAA,OAAO,GAAA,EAAK,EAAA;AAAA,MACd,CAAC,CAAA;AACD,MAAA,IAAA,CAAK,iBAAA,EAAmB,IAAA;AAAA,IAC1B;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,aAAA,CAAA,EAAgB;AACd,IAAA,IAAA,CAAK,cAAA,CAAe,CAAA;AACpB,IAAA,OAAO,IAAA,CAAK,UAAA;AAAA,EACd;AAAA,EAEA,YAAA,CAAa,CAAA,EAAW;AACtB,IAAA,IAAA,CAAK,cAAA,CAAe,CAAA;AACpB,IAAA,OAAO,IAAA,CAAK,UAAA,CAAW,CAAC,CAAA;AAAA,EAC1B;AAAA,EAEA,YAAA,CAAa,IAAA,EAAY;AACvB,IAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,IAAI,CAAA;AAAA,EAC3B;AACF,CAAA;AHnBA;AACA;AI3GA;AAQA,IAAM,KAAA,EAAN,MAAM,MAAK;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaT,WAAA,CAAA,EAAc;AACZ,IAAA,GAAA,CAAI,CAAC,IAAA,CAAK,QAAA,EAAU;AAClB,MAAA,IAAA,CAAK,SAAA,EAAW,IAAI,KAAA,CAAK,IAAA,CAAK,EAAA,EAAI,IAAA,CAAK,IAAI,CAAA;AAC3C,MAAA,IAAA,CAAK,QAAA,CAAS,SAAA,EAAW,IAAA;AAAA,IAC3B;AAEA,IAAA,OAAO,IAAA,CAAK,QAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,WAAA,CAAY,IAAA,EAAY,EAAA,EAAU;AAChC,IAAA,IAAA,CAAK,KAAA,EAAO,IAAA;AACZ,IAAA,IAAA,CAAK,GAAA,EAAK,EAAA;AAEV,IAAA,IAAA,CAAK,KAAA,EAAO,KAAA,CAAA;AACZ,IAAA,IAAA,CAAK,MAAA,EAAQ,KAAA,CAAA;AACb,IAAA,IAAA,CAAK,SAAA,EAAW,KAAA,CAAA;AAChB,IAAA,IAAA,CAAK,KAAA,EAAO,KAAA,CAAA;AAEZ,IAAA,IAAA,CAAK,IAAA,CAAK,YAAA,CAAa,IAAI,CAAA;AAC3B,IAAA,IAAA,CAAK,EAAA,CAAG,YAAA,CAAa,IAAI,CAAA;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA,EAKA,UAAA,CAAA,EAAa;AACX,IAAA,IAAA,CAAK,IAAA,CAAK,eAAA,CAAgB,IAAI,CAAA;AAC9B,IAAA,IAAA,CAAK,EAAA,CAAG,eAAA,CAAgB,IAAI,CAAA;AAAA,EAC9B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAA,CAAQ,IAAA,EAAY;AAClB,IAAA,OAAO,IAAA,CAAK,IAAA,CAAK,GAAA,IAAO,IAAA,CAAK,IAAA,CAAK,GAAA,GAAM,IAAA,CAAK,EAAA,CAAG,GAAA,IAAO,IAAA,CAAK,EAAA,CAAG,EAAA;AAAA,EACjE;AAAA,EAEA,QAAA,CAAA,EAAW;AACT,IAAA,OAAO,CAAA,OAAA,EAAU,IAAA,CAAK,IAAA,CAAK,EAAE,CAAA,IAAA,EAAO,IAAA,CAAK,EAAA,CAAG,EAAE,CAAA,EAAA,CAAA;AAAA,EAChD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,YAAA,CAAA,EAAe;AACb,IAAA,OAAO,iCAAA,CAAY,IAAA,CAAK,IAAA,CAAK,WAAA,EAAa,IAAA,CAAK,EAAA,CAAG,WAAW,CAAC,CAAA;AAAA,EAChE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,SAAA,CAAU,IAAA,EAAY;AACpB,IAAA,OAAO,gBAAA;AAAA,MACL,IAAA,CAAK,IAAA,CAAK,WAAA;AAAA,MACV,IAAA,CAAK,EAAA,CAAG,WAAA;AAAA,MACR,IAAA,CAAK,EAAA,CAAG;AAAA,IACV,CAAA;AAAA,EACF;AACF,CAAA;AJsFA;AACA;AKjLA;AACA,0CAAyB;AACzB;AAUA,IAAM,SAAA,EAAN,MAAe;AAAA,EAeb,WAAA,CAAA,EAAc;AACZ,IAAA,IAAA,CAAK,MAAA,EAAQ,CAAC,CAAA;AACd,IAAA,IAAA,CAAK,QAAA,EAAU,KAAA,CAAA;AACf,IAAA,IAAA,CAAK,SAAA,EAAW,KAAA,CAAA;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAA,CAAK,IAAA,EAAY;AACf,IAAA,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,IAAI,CAAA;AACpB,IAAA,IAAA,CAAK,QAAA,EAAU,IAAA,CAAK,SAAA,EAAW,KAAA,CAAA;AAAA,EACjC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,GAAA,CAAI,CAAA,EAAW;AACb,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,CAAC,CAAA;AAAA,EACrB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,MAAA,CAAA,EAAS;AACX,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,MAAA;AAAA,EACpB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAA,CAAQ,CAAA,EAAuD;AAC7D,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,CAAA;AAAA,EACtB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,GAAA,CAAO,CAAA,EAAyD;AAC9D,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,GAAA,CAAI,CAAC,CAAA;AAAA,EACzB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAA,CAAK,CAAA,EAA0D;AAC7D,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,CAAC,CAAA;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,OAAA,CAAA,EAAU;AAER,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,MAAA,CAAA,EAAS;AAGP,IAAA,MAAM,QAAA,EAAU,IAAA,CAAK,KAAA,CAAM,MAAA,CAAO,CAAC,IAAA,EAAM,IAAA,EAAM,CAAA,EAAA,GAAM;AACjD,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,KAAA,CAAM,IAAI,CAAA,CAAE,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA;AAChE,QAAA,KAAA,EAAO,CAAA;AACT,MAAA,OAAO,IAAA;AAAA,IACT,CAAA,EAAG,CAAC,CAAA,EACJ,MAAA,EAAA,CAAS,QAAA,IAAY,EAAA,EAAI,IAAA,CAAK,OAAA,EAAS,OAAA,EAAA,EAAW,CAAA,EAClD,MAAA,EAAA,CAAS,QAAA,EAAU,CAAA,EAAA,EAAK,IAAA,CAAK,MAAA,EAC7B,KAAA,EAAO,gBAAA;AAAA,MACL,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK,WAAA;AAAA,MACvB,IAAA,CAAK,KAAA,CAAM,OAAO,CAAA,CAAE,IAAA,CAAK,WAAA;AAAA,MACzB,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK;AAAA,IACzB,CAAA;AAEF,IAAA,GAAA,CAAI,KAAA,IAAS,CAAA;AACX,MAAA,OACE,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EACpC,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA;AAExC,IAAA,OAAO,KAAA,EAAO,CAAA;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,YAAA,CAAA,EAAe;AACb,IAAA,OAAO,iCAAA,IAAW,CAAK,KAAA,CAAM,GAAA,CAAI,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,IAAA,CAAK,WAAW,CAAC,CAAA;AAAA,EACnE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,SAAA,CAAA,EAAY;AACV,IAAA,GAAA,CAAI,IAAA,CAAK,OAAA,EAAS,OAAO,IAAA,CAAK,OAAA;AAC9B,IAAA,MAAM,YAAA,EAAc,IAAA,CAAK,KAAA,CAAM,GAAA,CAAI,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,IAAA,CAAK,WAAW,CAAA;AAClE,IAAA,WAAA,CAAY,IAAA,CAAK,IAAA,CAAK,KAAA,CAAM,CAAC,CAAA,CAAE,IAAA,CAAK,WAAW,CAAA;AAC/C,IAAA,OAAQ,IAAA,CAAK,QAAA,EAAU,8BAAA,CAAS,WAAW,CAAC,CAAA;AAAA,EAC9C;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,WAAA,CAAA,EAAc;AACZ,IAAA,GAAA,CAAI,IAAA,CAAK,QAAA,EAAU,OAAO,IAAA,CAAK,QAAA;AAC/B,IAAA,OAAQ,IAAA,CAAK,SAAA,EAAW,gCAAA,IAAS,CAAK,SAAA,CAAU,CAAC,CAAA;AAAA,EAInD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAO,sBAAA,CACL,YAAA,EACA,SAAA,EACsB;AACtB,IAAA,MAAM,aAAA,EAAe,YAAA,CAAa,WAAA,CAAY,CAAA;AAE9C,IAAA,IAAI,WAAA,EAA+B,QAAA;AACnC,IAAA,SAAA,CAAU,OAAA,CAAQ,CAAC,KAAA,EAAA,GAAU;AAC3B,MAAA,MAAM,YAAA,EAAc,KAAA,CAAM,WAAA,CAAY,CAAA;AAEtC,MAAA,GAAA,CAAI,QAAA,EAAU,YAAA,EAAc,QAAA,CAAS,WAAA,CAAY,CAAA;AAGjD,MAAA,GAAA,CAAI,eAAA,CAAgB,WAAA,EAAa,YAAY,CAAA,EAAG,MAAA;AAEhD,MAAA,GAAA,CAAI,gBAAA,CAAiB,WAAA,EAAa,YAAY,CAAA,EAAG;AAC/C,QAAA,MAAM,wBAAA,EAA0B,YAAA,CAAa,GAAA;AAAA,UAC3C,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,IAAA,CAAK;AAAA,QACtB,CAAA;AAEA,QAAA,IAAI,SAAA;AACJ,QAAA,IAAA,CAAA,MAAW,GAAA,GAAM,uBAAA,EAAyB;AACxC,UAAA,GAAA,CACE,CAAC,KAAA,CAAM,IAAA,CAAK,CAAC,IAAA,EAAA,GAAS,gBAAA,CAAiB,EAAA,EAAI,IAAA,CAAK,IAAA,CAAK,WAAW,CAAC,CAAA,EACjE;AACA,YAAA,UAAA,EAAY,EAAA;AAAA,UACd;AAAA,QACF;AAEA,QAAA,GAAA,CAAI,UAAA,GAAa,KAAA,CAAM,MAAA,CAAOA,4BAAAA,SAAe,CAAC,CAAA,EAAG;AAC/C,UAAA,GAAA,CAAI,CAAC,SAAA,GAAY,gBAAA,CAAiB,WAAA,EAAa,WAAW,CAAA;AACxD,YAAA,SAAA,EAAW,KAAA;AAAA,QACf;AAAA,MACF;AAAA,IACF,CAAC,CAAA;AAED,IAAA,OAAO,QAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,MAAA,CAAO,EAAA,EAAoB;AACzB,IAAA,OAAOC,0DAAAA,EAAsB,EAAI,IAAA,CAAK,SAAA,CAAU,CAAC,CAAA;AAAA,EACnD;AACF,CAAA;ALqHA;AACA;AMxWA,kCAAyC;AACzC,4CAA0B;AAe1B,SAAS,eAAA,CAAgB,OAAA,EAAqB;AAC5C,EAAA,GAAA,CAAI,CAAC,OAAA,EAAS,MAAM,IAAI,KAAA,CAAM,mBAAmB,CAAA;AAEjD,EAAA,GAAA,CACE,OAAA,CAAQ,KAAA,IAAS,oBAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,qBAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,kBAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,aAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,SAAA;AAEjB,IAAA,MAAM,IAAI,KAAA;AAAA,MACR,CAAA,oBAAA,EAAuB,OAAA,CAAQ,IAAI,CAAA,gGAAA;AAAA,IACrC,CAAA;AACJ;AAWA,IAAM,MAAA,EAAN,MAAM,OAAM;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWV,OAAO,WAAA,CACL,OAAA,EAKA;AACA,IAAA,eAAA,CAAgB,OAAO,CAAA;AAEvB,IAAA,MAAM,MAAA,EAAQ,IAAI,MAAA,CAAM,CAAA;AACxB,IAAA,+BAAA,OAAY,EAAS,CAAC,OAAA,EAAA,GAAY;AAChC,MAAA,kCAAA,OAAU,EAAS,YAAA,EAAc,oBAAoB,CAAA;AAErD,MAAA,+BAAA,OAAsB,EAAS,CAAC,IAAA,EAAM,GAAA,EAAA,GAAQ;AAC5C,QAAA,GAAA,CAAI,IAAA,EAAM;AACR,UAAA,MAAM,MAAA,EAAQ,KAAA,CAAM,OAAA,CAAQ,IAAI,CAAA,EAC9B,IAAA,EAAM,KAAA,CAAM,OAAA,CAAQ,GAAG,CAAA;AAEzB,UAAA,KAAA,CAAM,OAAA,CAAQ,KAAA,EAAO,GAAG,CAAA;AAAA,QAC1B;AACA,QAAA,OAAO,GAAA;AAAA,MACT,CAAC,CAAA;AAAA,IACH,CAAC,CAAA;AAED,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAA,CAAQ,WAAA,EAAuB;AAC7B,IAAA,MAAM,GAAA,EAAK,IAAA,CAAK,OAAA,CAAQ,WAAW,CAAA;AACnC,IAAA,IAAI,KAAA,EAAO,IAAA,CAAK,KAAA,CAAM,EAAE,CAAA;AACxB,IAAA,GAAA,CAAI,CAAC,IAAA,EAAM,KAAA,EAAO,IAAA,CAAK,KAAA,CAAM,EAAE,EAAA,EAAI,IAAI,IAAA,CAAK,WAAW,CAAA;AAEvD,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAA,CAAQ,IAAA,EAAY,EAAA,EAAU;AAC5B,IAAA,MAAM,KAAA,EAAO,IAAI,IAAA,CAAK,IAAA,EAAM,EAAE,CAAA,EAC5B,aAAA,EAAe,IAAA,CAAK,WAAA,CAAY,CAAA;AAElC,IAAA,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,IAAI,CAAA;AACpB,IAAA,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,YAAY,CAAA;AAAA,EAC9B;AAAA,EAEA,WAAA,CAAA,EAAc;AACZ,IAAA,IAAA,CAAK,MAAA,EAAQ,CAAC,CAAA;AAGd,IAAA,IAAA,CAAK,MAAA,EAAQ,CAAC,CAAA;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA,EAKA,aAAA,CAAA,EAAgB;AACd,IAAA,MAAA,CAAO,IAAA,CAAK,IAAA,CAAK,KAAK,CAAA,CACnB,GAAA,CAAI,CAAC,EAAA,EAAA,GAAO,IAAA,CAAK,KAAA,CAAM,EAAE,CAAC,CAAA,CAC1B,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,eAAA,CAAgB,IAAI,CAAC,CAAA;AAAA,EACjD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,eAAA,CAAgB,IAAA,EAAY;AAE1B,IAAA,GAAA,CAAI,IAAA,CAAK,UAAA,CAAW,OAAA,GAAU,CAAA,EAAG;AAC/B,MAAA,MAAM,WAAA,EAAa,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,EAAE,CAAA;AACvD,MAAA,IAAA,CAAK,UAAA,CAAW,IAAI,CAAA;AACpB,MAAA,UAAA,CAAW,OAAA,CAAQ,CAAC,CAAA,EAAA,GAAM,IAAA,CAAK,eAAA,CAAgB,CAAC,CAAC,CAAA;AAAA,IACnD;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,cAAA,CAAA,EAAiB;AACf,IAAA,IAAA,CAAK,mBAAA,CAAoB,CAAA;AACzB,IAAA,IAAA,CAAK,qBAAA,CAAsB,CAAA;AAG3B,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,GAAA,CAAI,IAAA,CAAK,MAAA,IAAU,IAAA,CAAK,QAAA,CAAU,KAAA,EAAO;AACvC,QAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,QAAS,CAAA;AAC9B,QAAA,IAAA,CAAK,UAAA,CAAW,IAAI,CAAA;AAAA,MACtB;AAAA,IACF,CAAC,CAAA;AAAA,EACH;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,mBAAA,CAAoB,IAAA,EAAa;AAC/B,IAAA,GAAA,CAAI,OAAO,KAAA,IAAS,WAAA,EAAa;AAC/B,MAAA,MAAA,CAAO,IAAA,CAAK,IAAA,CAAK,KAAK,CAAA,CAAE,OAAA;AAAA,QAAQ,CAAC,EAAA,EAAA,GAC/B,IAAA,CAAK,mBAAA,CAAoB,IAAA,CAAK,KAAA,CAAM,EAAE,CAAC;AAAA,MACzC,CAAA;AAAA,IACF,EAAA,KAAO;AACL,MAAA,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAM,CAAA,EAAA,GAAM;AACxC,QAAA,IAAA,CAAK,YAAA;AAAA,UAAA,CACF,EAAA,IAAM,EAAA,EAAI,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,EAAS,CAAA,EAAA,EAAK;AAAA,QAChD,CAAA,CAAE,QAAA,CAAU,KAAA,EAAO,IAAA;AAAA,MACrB,CAAC,CAAA;AAAA,IACH;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,oBAAA,CAAqB,IAAA,EAAY,KAAA,EAAe;AAC9C,IAAA,MAAM,MAAA,EAAQ,IAAA,CAAK,aAAA,CAAc,CAAA;AACjC,IAAA,IAAI,UAAA,EAAY,QAAA;AAEhB,IAAA,IAAA,CAAA,IAAS,EAAA,EAAI,KAAA,CAAM,OAAA,EAAS,CAAA,EAAG,EAAA,GAAK,CAAA,EAAG,EAAE,CAAA,EAAG;AAC1C,MAAA,IAAI,GAAA,EAAK,KAAA,CAAM,CAAC,CAAA,EACd,IAAA,EAAM,EAAA,CAAG,QAAA,EACT,KAAA,EACA,IAAA;AAEF,MAAA,GAAA,CAAI,EAAA,CAAG,MAAA,IAAU,KAAA,EAAO,MAAA,EAAQ,EAAA;AAEhC,MAAA,GAAA,CAAI,GAAA,CAAK,MAAA,IAAU,KAAA,EAAO,KAAA,EAAO,GAAA;AAEjC,MAAA,GAAA,CAAI,CAAC,MAAA,GAAS,CAAC,IAAA;AAEb,QAAA,QAAA;AAEF,MAAA,GAAA,CAAI,IAAA,EAAM,SAAA,EAAW,IAAA;AAErB,MAAA,GAAA,CAAI,KAAA,EAAO;AACT,QAAA,GAAA,CAAI,QAAA,EAAU;AACZ,UAAA,QAAA,CAAS,KAAA,EAAO,KAAA;AAChB,UAAA,SAAA,EAAW,KAAA,CAAA;AAAA,QACb;AAEA,QAAA,GAAA,CAAI,CAAC,UAAA,EAAY,WAAA,EAAa,KAAA;AAAA,MAChC;AAAA,IACF;AAEA,IAAA,GAAA,CAAI,QAAA,EAAU,QAAA,CAAS,KAAA,EAAO,UAAA;AAAA,EAChC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,qBAAA,CAAA,EAAwB;AACtB,IAAA,MAAM,eAAA,EAAyB,CAAC,CAAA;AAChC,IAAA,IAAI,MAAA,EAAQ,CAAA;AACZ,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,GAAA,CAAI,IAAA,CAAK,MAAA,GAAU,CAAA,EAAG,MAAA;AAEtB,MAAA,cAAA,CAAe,IAAA,CAAK,IAAI,CAAA;AAExB,MAAA,IAAI,EAAA,EAAI,IAAA;AACR,MAAA,GAAG;AACD,QAAA,CAAA,CAAE,MAAA,EAAQ,KAAA;AACV,QAAA,EAAA,EAAI,CAAA,CAAE,IAAA;AAAA,MACR,EAAA,MAAA,CAAS,CAAC,IAAA,CAAK,OAAA,CAAQ,CAAC,CAAA,CAAA;AAExB,MAAA,KAAA,EAAA;AAAA,IACF,CAAC,CAAA;AAED,IAAA,OAAO,cAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,YAAA,CAAA,EAAe;AACb,IAAA,IAAA,CAAK,mBAAA,CAAoB,CAAA;AAGzB,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,IAAA,CAAK,MAAA,EAAQ,KAAA,CAAA;AAAA,IACf,CAAC,CAAA;AAED,IAAA,IAAA,CAAK,qBAAA,CAAsB,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAE7C,MAAA,IAAA,CAAK,sBAAA,CAAuB,IAAI,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAClD,QAAA,IAAA,CAAK,oBAAA,CAAqB,IAAA,EAAM,IAAA,CAAK,KAAM,CAAA;AAAA,MAC7C,CAAC,CAAA;AAAA,IACH,CAAC,CAAA;AAED,IAAA,MAAM,aAAA,EAA2B,CAAC,CAAA;AAGlC,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,EAAM,MAAA;AACf,MAAA,YAAA,CAAa,IAAA,CAAK,IAAA,CAAK,aAAA,CAAc,IAAI,CAAC,CAAA;AAAA,IAC5C,CAAC,CAAA;AAED,IAAA,OAAO,YAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,sBAAA,CAAuB,SAAA,EAAiB;AACtC,IAAA,MAAM,kBAAA,EAAoB,CAAC,CAAA;AAC3B,IAAA,IAAI,KAAA,EAAO,SAAA;AACX,IAAA,GAAG;AAED,MAAA,IAAI,OAAA,EAAS,CAAA;AACb,MAAA,IAAA,CAAK,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,CAAQ,CAAC,CAAA,EAAA,GAAM;AACvC,QAAA,GAAA,CAAI,CAAA,CAAE,MAAA,IAAU,SAAA,CAAU,KAAA,EAAO,EAAE,MAAA;AAAA,MACrC,CAAC,CAAA;AAED,MAAA,GAAA,CAAI,OAAA,EAAS,CAAA,EAAG,iBAAA,CAAkB,IAAA,CAAK,IAAA,CAAK,IAAI,CAAA;AAEhD,MAAA,KAAA,EAAO,IAAA,CAAK,IAAA;AAAA,IACd,EAAA,MAAA,CAAS,CAAC,SAAA,CAAU,OAAA,CAAQ,IAAI,CAAA,CAAA;AAEhC,IAAA,OAAO,iBAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,aAAA,CAAc,SAAA,EAAiB;AAC7B,IAAA,IAAI,KAAA,EAAO,SAAA;AACX,IAAA,MAAM,SAAA,EAAW,IAAI,QAAA,CAAS,CAAA;AAE9B,IAAA,GAAG;AACD,MAAA,QAAA,CAAS,IAAA,CAAK,IAAI,CAAA;AAClB,MAAA,IAAA,CAAK,KAAA,EAAO,QAAA;AACZ,MAAA,KAAA,EAAO,IAAA,CAAK,IAAA;AAAA,IACd,EAAA,MAAA,CAAS,CAAC,SAAA,CAAU,OAAA,CAAQ,IAAI,CAAA,CAAA;AAEhC,IAAA,OAAO,QAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,UAAA,CAAW,IAAA,EAAY;AACrB,IAAA,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,UAAA,CAAW,IAAI,CAAC,CAAA;AAC5D,IAAA,IAAA,CAAK,UAAA,CAAW,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,UAAA,CAAW,IAAI,CAAC,CAAA;AACvD,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,EAAE,CAAA;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,UAAA,CAAW,IAAA,EAAY;AACrB,IAAA,IAAA,CAAK,MAAA,EAAQ,IAAA,CAAK,KAAA,CAAM,MAAA,CAAO,CAAC,CAAA,EAAA,GAAM,CAAC,CAAA,CAAE,OAAA,CAAQ,IAAI,CAAC,CAAA;AACtD,IAAA,IAAA,CAAK,UAAA,CAAW,CAAA;AAAA,EAClB;AACF,CAAA;ANuQA;AACA;AC1kBA,SAAS,UAAA,CACP,OAAA,EAC4B;AAC5B,EAAA,MAAM,MAAA,EAAQ,KAAA,CAAM,WAAA,CAAY,OAAO,CAAA;AAGvC,EAAA,KAAA,CAAM,aAAA,CAAc,CAAA;AAGpB,EAAA,KAAA,CAAM,cAAA,CAAe,CAAA;AAGrB,EAAA,MAAM,MAAA,EAAoB,CAAC,CAAA,EACzB,OAAA,EAAqB,CAAC,CAAA;AAExB,EAAA,KAAA,CACG,YAAA,CAAa,CAAA,CACb,MAAA,CAAO,CAAC,QAAA,EAAA,GAAa,QAAA,CAAS,OAAA,CAAQ,CAAC,CAAA,CACvC,OAAA,CAAQ,CAAC,QAAA,EAAA,GAAa;AACrB,IAAA,GAAA,CAAI,QAAA,CAAS,MAAA,CAAO,CAAA,EAAG,KAAA,CAAM,IAAA,CAAK,QAAQ,CAAA;AAAA,IAAA,KACrC,MAAA,CAAO,IAAA,CAAK,QAAQ,CAAA;AAAA,EAC3B,CAAC,CAAA;AAGH,EAAA,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AACtB,IAAA,GAAA,CAAI,QAAA,CAAS,sBAAA,CAAuB,IAAA,EAAM,MAAM,CAAA,EAAG,MAAA,CAAO,IAAA,CAAK,IAAI,CAAA;AAAA,EACrE,CAAC,CAAA;AAGD,EAAA,OAAO,wCAAA,MAAkB,CAAO,GAAA,CAAI,CAAC,KAAA,EAAA,GAAU,KAAA,CAAM,SAAA,CAAU,CAAC,CAAC,CAAA;AACnE;AAGA,IAAO,wBAAA,EAAQ,UAAA;ADyjBf;AACE;AACA;AACF,2EAAC","file":"/home/runner/work/turf/turf/packages/turf-polygonize/dist/cjs/index.cjs","sourcesContent":[null,"import {\n Feature,\n FeatureCollection,\n LineString,\n MultiLineString,\n Polygon,\n} from \"geojson\";\nimport { featureCollection } from \"@turf/helpers\";\nimport { Graph } from \"./lib/Graph.js\";\nimport { EdgeRing } from \"./lib/EdgeRing.js\";\n\n/*\n Polygonizes {@link LineString\|(Multi)LineString(s)} into {@link Polygons}.\n \n Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).\n \n Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly\n * noded, i.e., they must only meet at their endpoints.\n \n The implementation correctly handles:\n \n - Dangles: edges which have one or both ends which are not incident on another edge endpoint.\n * - Cut Edges (bridges): edges that are connected at both ends but which do not form part of a polygon.\n \n @function\n * @param {FeatureCollection\|Geometry\|Feature<LineString\|MultiLineString>} geoJson Lines in order to polygonize\n * @returns {FeatureCollection<Polygon>} Polygons created\n * @throws {Error} if geoJson is invalid.\n /\nfunction polygonize<T extends LineString \| MultiLineString>(\n geoJson: Feature<T> \| FeatureCollection<T> \| T\n): FeatureCollection<Polygon> {\n const graph = Graph.fromGeoJson(geoJson);\n\n // 1. Remove dangle node\n graph.deleteDangles();\n\n // 2. Remove cut-edges (bridge edges)\n graph.deleteCutEdges();\n\n // 3. Get all holes and shells\n const holes: EdgeRing[] = [],\n shells: EdgeRing[] = [];\n\n graph\n .getEdgeRings()\n .filter((edgeRing) => edgeRing.isValid())\n .forEach((edgeRing) => {\n if (edgeRing.isHole()) holes.push(edgeRing);\n else shells.push(edgeRing);\n });\n\n // 4. Assign Holes to Shells\n holes.forEach((hole) => {\n if (EdgeRing.findEdgeRingContaining(hole, shells)) shells.push(hole);\n });\n\n // 5. EdgeRings to Polygons\n return featureCollection(shells.map((shell) => shell.toPolygon()));\n}\n\nexport { polygonize };\nexport default polygonize;\n","import { Feature, Polygon } from \"geojson\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { point } from \"@turf/helpers\";\n\n// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/sign#Polyfill\nfunction mathSign(x: number) {\n return ((x > 0) as unknown as number) - ((x < 0) as unknown as number) \|\| +x;\n}\n\n/\n Returns the direction of the point q relative to the vector p1 -> p2.\n \n Implementation of geos::algorithm::CGAlgorithm::orientationIndex()\n * (same as geos::algorithm::CGAlgorithm::computeOrientation())\n \n @param {number[]} p1 - the origin point of the vector\n * @param {number[]} p2 - the final point of the vector\n * @param {number[]} q - the point to compute the direction to\n \n @returns {number} - 1 if q is ccw (left) from p1->p2,\n * -1 if q is cw (right) from p1->p2,\n * 0 if q is colinear with p1->p2\n /\nexport function orientationIndex(p1: number[], p2: number[], q: number[]) {\n const dx1 = p2[0] - p1[0],\n dy1 = p2[1] - p1[1],\n dx2 = q[0] - p2[0],\n dy2 = q[1] - p2[1];\n\n return mathSign(dx1 dy2 - dx2 * dy1);\n}\n\n/*\n Checks if two envelopes are equal.\n \n The function assumes that the arguments are envelopes, i.e.: Rectangular polygon\n \n @param {Feature<Polygon>} env1 - Envelope\n * @param {Feature<Polygon>} env2 - Envelope\n * @returns {boolean} - True if the envelopes are equal\n /\nexport function envelopeIsEqual(\n env1: Feature<Polygon>,\n env2: Feature<Polygon>\n) {\n const envX1 = env1.geometry.coordinates[0].map((c) => c[0]),\n envY1 = env1.geometry.coordinates[0].map((c) => c[1]),\n envX2 = env2.geometry.coordinates[0].map((c) => c[0]),\n envY2 = env2.geometry.coordinates[0].map((c) => c[1]);\n\n return (\n Math.max.apply(null, envX1) === Math.max.apply(null, envX2) &&\n Math.max.apply(null, envY1) === Math.max.apply(null, envY2) &&\n Math.min.apply(null, envX1) === Math.min.apply(null, envX2) &&\n Math.min.apply(null, envY1) === Math.min.apply(null, envY2)\n );\n}\n\n/\n Check if a envelope is contained in other one.\n \n The function assumes that the arguments are envelopes, i.e.: Convex polygon\n * XXX: Envelopes are rectangular, checking if a point is inside a rectangule is something easy,\n * this could be further improved.\n \n @param {Feature<Polygon>} self - Envelope\n * @param {Feature<Polygon>} env - Envelope\n * @returns {boolean} - True if env is contained in self\n /\nexport function envelopeContains(\n self: Feature<Polygon>,\n env: Feature<Polygon>\n) {\n return env.geometry.coordinates[0].every((c) =>\n booleanPointInPolygon(point(c), self)\n );\n}\n\n/\n Checks if two coordinates are equal.\n \n @param {number[]} coord1 - First coordinate\n * @param {number[]} coord2 - Second coordinate\n * @returns {boolean} - True if coordinates are equal\n /\nexport function coordinatesEqual(coord1: number[], coord2: number[]) {\n return coord1[0] === coord2[0] && coord1[1] === coord2[1];\n}\n","import { orientationIndex } from \"./util.js\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Node\n /\nclass Node {\n static buildId(coordinates: number[]) {\n return coordinates.join(\",\");\n }\n\n public id: string;\n public coordinates: number[];\n public innerEdges: Edge[];\n private outerEdges: Edge[];\n private outerEdgesSorted: boolean;\n\n constructor(coordinates: number[]) {\n this.id = Node.buildId(coordinates);\n this.coordinates = coordinates; //< {Number[]}\n this.innerEdges = []; //< {Edge[]}\n\n // We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does\n this.outerEdges = []; //< {Edge[]}\n this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted\n }\n\n removeInnerEdge(edge: Edge) {\n this.innerEdges = this.innerEdges.filter((e) => e.from.id !== edge.from.id);\n }\n\n removeOuterEdge(edge: Edge) {\n this.outerEdges = this.outerEdges.filter((e) => e.to.id !== edge.to.id);\n }\n\n /\n Outer edges are stored CCW order.\n \n @memberof Node\n * @param {Edge} edge - Edge to add as an outerEdge.\n /\n addOuterEdge(edge: Edge) {\n this.outerEdges.push(edge);\n this.outerEdgesSorted = false;\n }\n\n /\n Sorts outer edges in CCW way.\n \n @memberof Node\n * @private\n /\n sortOuterEdges() {\n if (!this.outerEdgesSorted) {\n //this.outerEdges.sort((a, b) => a.compareTo(b));\n // Using this comparator in order to be deterministic\n this.outerEdges.sort((a, b) => {\n const aNode = a.to,\n bNode = b.to;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] >= 0 &&\n bNode.coordinates[0] - this.coordinates[0] < 0\n )\n return 1;\n if (\n aNode.coordinates[0] - this.coordinates[0] < 0 &&\n bNode.coordinates[0] - this.coordinates[0] >= 0\n )\n return -1;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] === 0 &&\n bNode.coordinates[0] - this.coordinates[0] === 0\n ) {\n if (\n aNode.coordinates[1] - this.coordinates[1] >= 0 \|\|\n bNode.coordinates[1] - this.coordinates[1] >= 0\n )\n return aNode.coordinates[1] - bNode.coordinates[1];\n return bNode.coordinates[1] - aNode.coordinates[1];\n }\n\n const det = orientationIndex(\n this.coordinates,\n aNode.coordinates,\n bNode.coordinates\n );\n if (det < 0) return 1;\n if (det > 0) return -1;\n\n const d1 =\n Math.pow(aNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(aNode.coordinates[1] - this.coordinates[1], 2),\n d2 =\n Math.pow(bNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(bNode.coordinates[1] - this.coordinates[1], 2);\n\n return d1 - d2;\n });\n this.outerEdgesSorted = true;\n }\n }\n\n /\n Retrieves outer edges.\n \n They are sorted if they aren't in the CCW order.\n \n @memberof Node\n * @returns {Edge[]} - List of outer edges sorted in a CCW order.\n /\n getOuterEdges() {\n this.sortOuterEdges();\n return this.outerEdges;\n }\n\n getOuterEdge(i: number) {\n this.sortOuterEdges();\n return this.outerEdges[i];\n }\n\n addInnerEdge(edge: Edge) {\n this.innerEdges.push(edge);\n }\n}\n\nexport { Node };\nexport default Node;\n","import { lineString } from \"@turf/helpers\";\nimport { orientationIndex } from \"./util.js\";\nimport { Node } from \"./Node.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\n\n/\n This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge\n /\nclass Edge {\n public label?: number;\n public symetric?: Edge;\n public from: Node;\n public to: Node;\n public next?: Edge;\n public ring?: EdgeRing;\n\n /\n Creates or get the symetric Edge.\n \n @returns {Edge} - Symetric Edge.\n /\n getSymetric() {\n if (!this.symetric) {\n this.symetric = new Edge(this.to, this.from);\n this.symetric.symetric = this;\n }\n\n return this.symetric;\n }\n\n /\n @param {Node} from - start node of the Edge\n * @param {Node} to - end node of the edge\n /\n constructor(from: Node, to: Node) {\n this.from = from; //< start\n this.to = to; //< End\n\n this.next = undefined; //< The edge to be computed after\n this.label = undefined; //< Used in order to detect Cut Edges (Bridges)\n this.symetric = undefined; //< The symetric edge of this\n this.ring = undefined; //< EdgeRing in which the Edge is\n\n this.from.addOuterEdge(this);\n this.to.addInnerEdge(this);\n }\n\n /\n Removes edge from from and to nodes.\n /\n deleteEdge() {\n this.from.removeOuterEdge(this);\n this.to.removeInnerEdge(this);\n }\n\n /\n Compares Edge equallity.\n \n An edge is equal to another, if the from and to nodes are the same.\n \n @param {Edge} edge - Another Edge\n * @returns {boolean} - True if Edges are equal, False otherwise\n /\n isEqual(edge: Edge) {\n return this.from.id === edge.from.id && this.to.id === edge.to.id;\n }\n\n toString() {\n return `Edge { ${this.from.id} -> ${this.to.id} }`;\n }\n\n /\n Returns a LineString representation of the Edge\n \n @returns {Feature<LineString>} - LineString representation of the Edge\n /\n toLineString() {\n return lineString([this.from.coordinates, this.to.coordinates]);\n }\n\n /\n Comparator of two edges.\n \n Implementation of geos::planargraph::DirectedEdge::compareTo.\n \n @param {Edge} edge - Another edge to compare with this one\n * @returns {number} -1 if this Edge has a greater angle with the positive x-axis than b,\n * 0 if the Edges are colinear,\n * 1 otherwise\n /\n compareTo(edge: Edge) {\n return orientationIndex(\n edge.from.coordinates,\n edge.to.coordinates,\n this.to.coordinates\n );\n }\n}\n\nexport { Edge };\nexport default Edge;\n","import { Polygon, Feature, Point, Position } from \"geojson\";\nimport {\n orientationIndex,\n envelopeIsEqual,\n envelopeContains,\n coordinatesEqual,\n} from \"./util.js\";\nimport { multiPoint, polygon, point } from \"@turf/helpers\";\nimport { envelope } from \"@turf/envelope\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Ring of edges which form a polygon.\n \n The ring may be either an outer shell or a hole.\n \n This class is inspired in GEOS's geos::operation::polygonize::EdgeRing\n /\nclass EdgeRing {\n private edges: Edge[];\n private polygon?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n private envelope?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n\n constructor() {\n this.edges = [];\n this.polygon = undefined; //< Caches Polygon representation\n this.envelope = undefined; //< Caches Envelope representation\n }\n\n /\n Add an edge to the ring, inserting it in the last position.\n \n @memberof EdgeRing\n * @param {Edge} edge - Edge to be inserted\n /\n push(edge: Edge) {\n this.edges.push(edge);\n this.polygon = this.envelope = undefined;\n }\n\n /\n Get Edge.\n \n @memberof EdgeRing\n * @param {number} i - Index\n * @returns {Edge} - Edge in the i position\n /\n get(i: number) {\n return this.edges[i];\n }\n\n /\n Getter of length property.\n \n @memberof EdgeRing\n * @returns {number} - Length of the edge ring.\n /\n get length() {\n return this.edges.length;\n }\n\n /\n Similar to Array.prototype.forEach for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.forEach\n /\n forEach(f: (edge: Edge, index: number, array: Edge[]) => void) {\n this.edges.forEach(f);\n }\n\n /\n Similar to Array.prototype.map for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.map\n * @returns {Array} - The mapped values in the function\n /\n map<T>(f: (edge: Edge, index: number, array: Edge[]) => T): T[] {\n return this.edges.map(f);\n }\n\n /\n Similar to Array.prototype.some for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.some\n * @returns {boolean} - True if an Edge check the condition\n /\n some(f: (edge: Edge, index: number, array: Edge[]) => boolean) {\n return this.edges.some(f);\n }\n\n /\n Check if the ring is valid in geomtry terms.\n \n A ring must have either 0 or 4 or more points. The first and the last must be\n * equal (in 2D)\n * geos::geom::LinearRing::validateConstruction\n \n @memberof EdgeRing\n * @returns {boolean} - Validity of the EdgeRing\n /\n isValid() {\n // TODO: stub\n return true;\n }\n\n /\n Tests whether this ring is a hole.\n \n A ring is a hole if it is oriented counter-clockwise.\n * Similar implementation of geos::algorithm::CGAlgorithms::isCCW\n \n @memberof EdgeRing\n * @returns {boolean} - true: if it is a hole\n /\n isHole() {\n // XXX: Assuming Ring is valid\n // Find highest point\n const hiIndex = this.edges.reduce((high, edge, i) => {\n if (edge.from.coordinates[1] > this.edges[high].from.coordinates[1])\n high = i;\n return high;\n }, 0),\n iPrev = (hiIndex === 0 ? this.length : hiIndex) - 1,\n iNext = (hiIndex + 1) % this.length,\n disc = orientationIndex(\n this.edges[iPrev].from.coordinates,\n this.edges[hiIndex].from.coordinates,\n this.edges[iNext].from.coordinates\n );\n\n if (disc === 0)\n return (\n this.edges[iPrev].from.coordinates[0] >\n this.edges[iNext].from.coordinates[0]\n );\n return disc > 0;\n }\n\n /\n Creates a MultiPoint representing the EdgeRing (discarts edges directions).\n \n @memberof EdgeRing\n * @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing\n /\n toMultiPoint() {\n return multiPoint(this.edges.map((edge) => edge.from.coordinates));\n }\n\n /\n Creates a Polygon representing the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - Polygon representation of the Edge Ring\n /\n toPolygon() {\n if (this.polygon) return this.polygon;\n const coordinates = this.edges.map((edge) => edge.from.coordinates);\n coordinates.push(this.edges[0].from.coordinates);\n return (this.polygon = polygon([coordinates]));\n }\n\n /\n Calculates the envelope of the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - envelope\n /\n getEnvelope() {\n if (this.envelope) return this.envelope;\n return (this.envelope = envelope(this.toPolygon()) as Feature<\n Polygon,\n { [name: string]: any }\n >);\n }\n\n /\n `geos::operation::polygonize::EdgeRing::findEdgeRingContaining`\n \n @param {EdgeRing} testEdgeRing - EdgeRing to look in the list\n * @param {EdgeRing[]} shellList - List of EdgeRing in which to search\n \n @returns {EdgeRing} - EdgeRing which contains the testEdgeRing\n /\n static findEdgeRingContaining(\n testEdgeRing: EdgeRing,\n shellList: EdgeRing[]\n ): EdgeRing \| undefined {\n const testEnvelope = testEdgeRing.getEnvelope();\n\n let minEnvelope: Feature<Polygon>, minShell: EdgeRing \| undefined;\n shellList.forEach((shell) => {\n const tryEnvelope = shell.getEnvelope();\n\n if (minShell) minEnvelope = minShell.getEnvelope();\n\n // the hole envelope cannot equal the shell envelope\n if (envelopeIsEqual(tryEnvelope, testEnvelope)) return;\n\n if (envelopeContains(tryEnvelope, testEnvelope)) {\n const testEdgeRingCoordinates = testEdgeRing.map(\n (edge) => edge.from.coordinates\n );\n\n let testPoint: Position \| undefined;\n for (const pt of testEdgeRingCoordinates) {\n if (\n !shell.some((edge) => coordinatesEqual(pt, edge.from.coordinates))\n ) {\n testPoint = pt;\n }\n }\n\n if (testPoint && shell.inside(point(testPoint))) {\n if (!minShell \|\| envelopeContains(minEnvelope, tryEnvelope))\n minShell = shell;\n }\n }\n });\n\n return minShell;\n }\n\n /\n Checks if the point is inside the edgeRing\n \n @param {Feature<Point>} pt - Point to check if it is inside the edgeRing\n * @returns {boolean} - True if it is inside, False otherwise\n /\n inside(pt: Feature<Point>) {\n return booleanPointInPolygon(pt, this.toPolygon());\n }\n}\n\nexport { EdgeRing };\nexport default EdgeRing;\n","import { Node } from \"./Node.js\";\nimport { Edge } from \"./Edge.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\nimport { flattenEach, coordReduce } from \"@turf/meta\";\nimport { featureOf } from \"@turf/invariant\";\nimport {\n FeatureCollection,\n LineString,\n MultiLineString,\n Feature,\n} from \"geojson\";\nimport { AllGeoJSON } from \"@turf/helpers\";\n\n/\n Validates the geoJson.\n \n @param {GeoJSON} geoJson - input geoJson.\n * @throws {Error} if geoJson is invalid.\n /\nfunction validateGeoJson(geoJson: AllGeoJSON) {\n if (!geoJson) throw new Error(\"No geojson passed\");\n\n if (\n geoJson.type !== \"FeatureCollection\" &&\n geoJson.type !== \"GeometryCollection\" &&\n geoJson.type !== \"MultiLineString\" &&\n geoJson.type !== \"LineString\" &&\n geoJson.type !== \"Feature\"\n )\n throw new Error(\n `Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`\n );\n}\n\n/\n Represents a planar graph of edges and nodes that can be used to compute a polygonization.\n \n Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,\n * it isn't a rewrite. As regards algorithm, this class implements the same logic, but it\n * isn't a javascript transcription of the C++ source.\n \n This graph is directed (both directions are created)\n /\nclass Graph {\n private nodes: { [id: string]: Node };\n private edges: Edge[];\n\n /\n Creates a graph from a GeoJSON.\n \n @param {FeatureCollection<LineString>} geoJson - it must comply with the restrictions detailed in the index\n * @returns {Graph} - The newly created graph\n * @throws {Error} if geoJson is invalid.\n /\n static fromGeoJson(\n geoJson:\n \| FeatureCollection<LineString \| MultiLineString>\n \| LineString\n \| MultiLineString\n \| Feature<LineString \| MultiLineString>\n ) {\n validateGeoJson(geoJson);\n\n const graph = new Graph();\n flattenEach(geoJson, (feature) => {\n featureOf(feature, \"LineString\", \"Graph::fromGeoJson\");\n // When a LineString if formed by many segments, split them\n coordReduce<number[]>(feature, (prev, cur) => {\n if (prev) {\n const start = graph.getNode(prev),\n end = graph.getNode(cur);\n\n graph.addEdge(start, end);\n }\n return cur;\n });\n });\n\n return graph;\n }\n\n /\n Creates or get a Node.\n \n @param {number[]} coordinates - Coordinates of the node\n * @returns {Node} - The created or stored node\n /\n getNode(coordinates: number[]) {\n const id = Node.buildId(coordinates);\n let node = this.nodes[id];\n if (!node) node = this.nodes[id] = new Node(coordinates);\n\n return node;\n }\n\n /\n Adds an Edge and its symetricall.\n \n Edges are added symetrically, i.e.: we also add its symetric\n \n @param {Node} from - Node which starts the Edge\n * @param {Node} to - Node which ends the Edge\n /\n addEdge(from: Node, to: Node) {\n const edge = new Edge(from, to),\n symetricEdge = edge.getSymetric();\n\n this.edges.push(edge);\n this.edges.push(symetricEdge);\n }\n\n constructor() {\n this.edges = []; //< {Edge[]} dirEdges\n\n // The key is the `id` of the Node (ie: coordinates.join(','))\n this.nodes = {};\n }\n\n /\n Removes Dangle Nodes (nodes with grade 1).\n /\n deleteDangles() {\n Object.keys(this.nodes)\n .map((id) => this.nodes[id])\n .forEach((node) => this._removeIfDangle(node));\n }\n\n /\n Check if node is dangle, if so, remove it.\n \n It calls itself recursively, removing a dangling node might cause another dangling node\n \n @param {Node} node - Node to check if it's a dangle\n /\n _removeIfDangle(node: Node) {\n // As edges are directed and symetrical, we count only innerEdges\n if (node.innerEdges.length <= 1) {\n const outerNodes = node.getOuterEdges().map((e) => e.to);\n this.removeNode(node);\n outerNodes.forEach((n) => this._removeIfDangle(n));\n }\n }\n\n /\n Delete cut-edges (bridge edges).\n \n The graph will be traversed, all the edges will be labeled according the ring\n * in which they are. (The label is a number incremented by 1). Edges with the same\n * label are cut-edges.\n /\n deleteCutEdges() {\n this._computeNextCWEdges();\n this._findLabeledEdgeRings();\n\n // Cut-edges (bridges) are edges where both edges have the same label\n this.edges.forEach((edge) => {\n if (edge.label === edge.symetric!.label) {\n this.removeEdge(edge.symetric!);\n this.removeEdge(edge);\n }\n });\n }\n\n /\n Set the `next` property of each Edge.\n \n The graph will be transversed in a CW form, so, we set the next of the symetrical edge as the previous one.\n * OuterEdges are sorted CCW.\n \n @param {Node} [node] - If no node is passed, the function calls itself for every node in the Graph\n /\n _computeNextCWEdges(node?: Node) {\n if (typeof node === \"undefined\") {\n Object.keys(this.nodes).forEach((id) =>\n this._computeNextCWEdges(this.nodes[id])\n );\n } else {\n node.getOuterEdges().forEach((edge, i) => {\n node.getOuterEdge(\n (i === 0 ? node.getOuterEdges().length : i) - 1\n ).symetric!.next = edge;\n });\n }\n }\n\n /\n Computes the next edge pointers going CCW around the given node, for the given edgering label.\n \n This algorithm has the effect of converting maximal edgerings into minimal edgerings\n \n XXX: method literally transcribed from `geos::operation::polygonize::PolygonizeGraph::computeNextCCWEdges`,\n * could be written in a more javascript way.\n \n @param {Node} node - Node\n * @param {number} label - Ring's label\n /\n _computeNextCCWEdges(node: Node, label: number) {\n const edges = node.getOuterEdges();\n let firstOutDE, prevInDE;\n\n for (let i = edges.length - 1; i >= 0; --i) {\n let de = edges[i],\n sym = de.symetric,\n outDE,\n inDE;\n\n if (de.label === label) outDE = de;\n\n if (sym!.label === label) inDE = sym;\n\n if (!outDE \|\| !inDE)\n // This edge is not in edgering\n continue;\n\n if (inDE) prevInDE = inDE;\n\n if (outDE) {\n if (prevInDE) {\n prevInDE.next = outDE;\n prevInDE = undefined;\n }\n\n if (!firstOutDE) firstOutDE = outDE;\n }\n }\n\n if (prevInDE) prevInDE.next = firstOutDE;\n }\n\n /\n Finds rings and labels edges according to which rings are.\n \n The label is a number which is increased for each ring.\n \n @returns {Edge[]} edges that start rings\n /\n _findLabeledEdgeRings() {\n const edgeRingStarts: Edge[] = [];\n let label = 0;\n this.edges.forEach((edge) => {\n if (edge.label! >= 0) return;\n\n edgeRingStarts.push(edge);\n\n let e = edge;\n do {\n e.label = label;\n e = e.next!;\n } while (!edge.isEqual(e));\n\n label++;\n });\n\n return edgeRingStarts;\n }\n\n /\n Computes the EdgeRings formed by the edges in this graph.\n \n @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.\n /\n getEdgeRings() {\n this._computeNextCWEdges();\n\n // Clear labels\n this.edges.forEach((edge) => {\n edge.label = undefined;\n });\n\n this._findLabeledEdgeRings().forEach((edge) => {\n // convertMaximalToMinimalEdgeRings\n this._findIntersectionNodes(edge).forEach((node) => {\n this._computeNextCCWEdges(node, edge.label!);\n });\n });\n\n const edgeRingList: EdgeRing[] = [];\n\n // find all edgerings\n this.edges.forEach((edge) => {\n if (edge.ring) return;\n edgeRingList.push(this._findEdgeRing(edge));\n });\n\n return edgeRingList;\n }\n\n /\n Find all nodes in a Maxima EdgeRing which are self-intersection nodes.\n \n @param {Node} startEdge - Start Edge of the Ring\n * @returns {Node[]} - intersection nodes\n /\n _findIntersectionNodes(startEdge: Edge) {\n const intersectionNodes = [];\n let edge = startEdge;\n do {\n // getDegree\n let degree = 0;\n edge.from.getOuterEdges().forEach((e) => {\n if (e.label === startEdge.label) ++degree;\n });\n\n if (degree > 1) intersectionNodes.push(edge.from);\n\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return intersectionNodes;\n }\n\n /\n Get the edge-ring which starts from the provided Edge.\n \n @param {Edge} startEdge - starting edge of the edge ring\n * @returns {EdgeRing} - EdgeRing which start Edge is the provided one.\n /\n _findEdgeRing(startEdge: Edge) {\n let edge = startEdge;\n const edgeRing = new EdgeRing();\n\n do {\n edgeRing.push(edge);\n edge.ring = edgeRing;\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return edgeRing;\n }\n\n /\n Removes a node from the Graph.\n \n It also removes edges asociated to that node\n * @param {Node} node - Node to be removed\n /\n removeNode(node: Node) {\n node.getOuterEdges().forEach((edge) => this.removeEdge(edge));\n node.innerEdges.forEach((edge) => this.removeEdge(edge));\n delete this.nodes[node.id];\n }\n\n /\n Remove edge from the graph and deletes the edge.\n \n @param {Edge} edge - Edge to be removed\n */\n removeEdge(edge: Edge) {\n this.edges = this.edges.filter((e) => !e.isEqual(edge));\n edge.deleteEdge();\n }\n}\n\nexport { Graph };\nexport default Graph;\n"]}
		{"version":3,"sources":["/home/runner/work/turf/turf/packages/turf-polygonize/dist/cjs/index.cjs","../../index.ts","../../lib/util.ts","../../lib/Node.ts","../../lib/Edge.ts","../../lib/EdgeRing.ts","../../lib/Graph.ts"],"names":["point","booleanPointInPolygon"],"mappings":"AAAA;ACOA,wCAAkC;ADLlC;AACA;AEFA,uEAAsC;AACtC;AAGA,SAAS,QAAA,CAAS,CAAA,EAAW;AAC3B,EAAA,OAAA,CAAS,EAAA,EAAI,CAAA,EAAA,EAAA,CAA6B,EAAA,EAAI,CAAA,EAAA,GAA4B,CAAC,CAAA;AAC7E;AAgBO,SAAS,gBAAA,CAAiB,EAAA,EAAc,EAAA,EAAc,CAAA,EAAa;AACxE,EAAA,MAAM,IAAA,EAAM,EAAA,CAAG,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA,EACtB,IAAA,EAAM,EAAA,CAAG,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA,EAClB,IAAA,EAAM,CAAA,CAAE,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA,EACjB,IAAA,EAAM,CAAA,CAAE,CAAC,EAAA,EAAI,EAAA,CAAG,CAAC,CAAA;AAEnB,EAAA,OAAO,QAAA,CAAS,IAAA,EAAM,IAAA,EAAM,IAAA,EAAM,GAAG,CAAA;AACvC;AAWO,SAAS,eAAA,CACd,IAAA,EACA,IAAA,EACA;AACA,EAAA,MAAM,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA,EACxD,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA,EACpD,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA,EACpD,MAAA,EAAQ,IAAA,CAAK,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,CAAC,CAAC,CAAA;AAEtD,EAAA,OACE,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,GAC1D,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,GAC1D,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,GAC1D,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,EAAA,IAAM,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,IAAA,EAAM,KAAK,CAAA;AAE9D;AAaO,SAAS,gBAAA,CACd,IAAA,EACA,GAAA,EACA;AACA,EAAA,OAAO,GAAA,CAAI,QAAA,CAAS,WAAA,CAAY,CAAC,CAAA,CAAE,KAAA;AAAA,IAAM,CAAC,CAAA,EAAA,GACxC,0DAAA,4BAAsB,CAAO,CAAA,EAAG,IAAI;AAAA,EACtC,CAAA;AACF;AASO,SAAS,gBAAA,CAAiB,MAAA,EAAkB,MAAA,EAAkB;AACnE,EAAA,OAAO,MAAA,CAAO,CAAC,EAAA,IAAM,MAAA,CAAO,CAAC,EAAA,GAAK,MAAA,CAAO,CAAC,EAAA,IAAM,MAAA,CAAO,CAAC,CAAA;AAC1D;AF9DA;AACA;AGpBA,IAAM,KAAA,EAAN,MAAM,MAAK;AAAA,EACT,OAAO,OAAA,CAAQ,WAAA,EAAuB;AACpC,IAAA,OAAO,WAAA,CAAY,IAAA,CAAK,GAAG,CAAA;AAAA,EAC7B;AAAA,EAQA,WAAA,CAAY,WAAA,EAAuB;AACjC,IAAA,IAAA,CAAK,GAAA,EAAK,KAAA,CAAK,OAAA,CAAQ,WAAW,CAAA;AAClC,IAAA,IAAA,CAAK,YAAA,EAAc,WAAA;AACnB,IAAA,IAAA,CAAK,WAAA,EAAa,CAAC,CAAA;AAGnB,IAAA,IAAA,CAAK,WAAA,EAAa,CAAC,CAAA;AACnB,IAAA,IAAA,CAAK,iBAAA,EAAmB,KAAA;AAAA,EAC1B;AAAA,EAEA,eAAA,CAAgB,IAAA,EAAY;AAC1B,IAAA,IAAA,CAAK,WAAA,EAAa,IAAA,CAAK,UAAA,CAAW,MAAA,CAAO,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,IAAA,CAAK,GAAA,IAAO,IAAA,CAAK,IAAA,CAAK,EAAE,CAAA;AAAA,EAC5E;AAAA,EAEA,eAAA,CAAgB,IAAA,EAAY;AAC1B,IAAA,IAAA,CAAK,WAAA,EAAa,IAAA,CAAK,UAAA,CAAW,MAAA,CAAO,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,EAAA,CAAG,GAAA,IAAO,IAAA,CAAK,EAAA,CAAG,EAAE,CAAA;AAAA,EACxE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,YAAA,CAAa,IAAA,EAAY;AACvB,IAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,IAAI,CAAA;AACzB,IAAA,IAAA,CAAK,iBAAA,EAAmB,KAAA;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,cAAA,CAAA,EAAiB;AACf,IAAA,GAAA,CAAI,CAAC,IAAA,CAAK,gBAAA,EAAkB;AAG1B,MAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,CAAC,CAAA,EAAG,CAAA,EAAA,GAAM;AAC7B,QAAA,MAAM,MAAA,EAAQ,CAAA,CAAE,EAAA,EACd,MAAA,EAAQ,CAAA,CAAE,EAAA;AAEZ,QAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,EAAA,GAC9C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EAAI,CAAA;AAE7C,UAAA,OAAO,CAAA;AACT,QAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EAAI,EAAA,GAC7C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,CAAA;AAE9C,UAAA,OAAO,CAAA,CAAA;AAET,QAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,IAAM,EAAA,GAC/C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,IAAM,CAAA,EAC/C;AACA,UAAA,GAAA,CACE,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,EAAA,GAC9C,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,GAAK,CAAA;AAE9C,YAAA,OAAO,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,KAAA,CAAM,WAAA,CAAY,CAAC,CAAA;AACnD,UAAA,OAAO,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,KAAA,CAAM,WAAA,CAAY,CAAC,CAAA;AAAA,QACnD;AAEA,QAAA,MAAM,IAAA,EAAM,gBAAA;AAAA,UACV,IAAA,CAAK,WAAA;AAAA,UACL,KAAA,CAAM,WAAA;AAAA,UACN,KAAA,CAAM;AAAA,QACR,CAAA;AACA,QAAA,GAAA,CAAI,IAAA,EAAM,CAAA,EAAG,OAAO,CAAA;AACpB,QAAA,GAAA,CAAI,IAAA,EAAM,CAAA,EAAG,OAAO,CAAA,CAAA;AAEpB,QAAA,MAAM,GAAA,EACF,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,EAAA,EACtD,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,CAAA,EACxD,GAAA,EACE,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,EAAA,EACtD,IAAA,CAAK,GAAA,CAAI,KAAA,CAAM,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA,EAAG,CAAC,CAAA;AAE1D,QAAA,OAAO,GAAA,EAAK,EAAA;AAAA,MACd,CAAC,CAAA;AACD,MAAA,IAAA,CAAK,iBAAA,EAAmB,IAAA;AAAA,IAC1B;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,aAAA,CAAA,EAAgB;AACd,IAAA,IAAA,CAAK,cAAA,CAAe,CAAA;AACpB,IAAA,OAAO,IAAA,CAAK,UAAA;AAAA,EACd;AAAA,EAEA,YAAA,CAAa,CAAA,EAAW;AACtB,IAAA,IAAA,CAAK,cAAA,CAAe,CAAA;AACpB,IAAA,OAAO,IAAA,CAAK,UAAA,CAAW,CAAC,CAAA;AAAA,EAC1B;AAAA,EAEA,YAAA,CAAa,IAAA,EAAY;AACvB,IAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,IAAI,CAAA;AAAA,EAC3B;AACF,CAAA;AHnBA;AACA;AI3GA;AAQA,IAAM,KAAA,EAAN,MAAM,MAAK;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaT,WAAA,CAAA,EAAc;AACZ,IAAA,GAAA,CAAI,CAAC,IAAA,CAAK,QAAA,EAAU;AAClB,MAAA,IAAA,CAAK,SAAA,EAAW,IAAI,KAAA,CAAK,IAAA,CAAK,EAAA,EAAI,IAAA,CAAK,IAAI,CAAA;AAC3C,MAAA,IAAA,CAAK,QAAA,CAAS,SAAA,EAAW,IAAA;AAAA,IAC3B;AAEA,IAAA,OAAO,IAAA,CAAK,QAAA;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,WAAA,CAAY,IAAA,EAAY,EAAA,EAAU;AAChC,IAAA,IAAA,CAAK,KAAA,EAAO,IAAA;AACZ,IAAA,IAAA,CAAK,GAAA,EAAK,EAAA;AAEV,IAAA,IAAA,CAAK,KAAA,EAAO,KAAA,CAAA;AACZ,IAAA,IAAA,CAAK,MAAA,EAAQ,KAAA,CAAA;AACb,IAAA,IAAA,CAAK,SAAA,EAAW,KAAA,CAAA;AAChB,IAAA,IAAA,CAAK,KAAA,EAAO,KAAA,CAAA;AAEZ,IAAA,IAAA,CAAK,IAAA,CAAK,YAAA,CAAa,IAAI,CAAA;AAC3B,IAAA,IAAA,CAAK,EAAA,CAAG,YAAA,CAAa,IAAI,CAAA;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA,EAKA,UAAA,CAAA,EAAa;AACX,IAAA,IAAA,CAAK,IAAA,CAAK,eAAA,CAAgB,IAAI,CAAA;AAC9B,IAAA,IAAA,CAAK,EAAA,CAAG,eAAA,CAAgB,IAAI,CAAA;AAAA,EAC9B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAA,CAAQ,IAAA,EAAY;AAClB,IAAA,OAAO,IAAA,CAAK,IAAA,CAAK,GAAA,IAAO,IAAA,CAAK,IAAA,CAAK,GAAA,GAAM,IAAA,CAAK,EAAA,CAAG,GAAA,IAAO,IAAA,CAAK,EAAA,CAAG,EAAA;AAAA,EACjE;AAAA,EAEA,QAAA,CAAA,EAAW;AACT,IAAA,OAAO,CAAA,OAAA,EAAU,IAAA,CAAK,IAAA,CAAK,EAAE,CAAA,IAAA,EAAO,IAAA,CAAK,EAAA,CAAG,EAAE,CAAA,EAAA,CAAA;AAAA,EAChD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,YAAA,CAAA,EAAe;AACb,IAAA,OAAO,iCAAA,CAAY,IAAA,CAAK,IAAA,CAAK,WAAA,EAAa,IAAA,CAAK,EAAA,CAAG,WAAW,CAAC,CAAA;AAAA,EAChE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,SAAA,CAAU,IAAA,EAAY;AACpB,IAAA,OAAO,gBAAA;AAAA,MACL,IAAA,CAAK,IAAA,CAAK,WAAA;AAAA,MACV,IAAA,CAAK,EAAA,CAAG,WAAA;AAAA,MACR,IAAA,CAAK,EAAA,CAAG;AAAA,IACV,CAAA;AAAA,EACF;AACF,CAAA;AJsFA;AACA;AKjLA;AACA,0CAAyB;AACzB;AAUA,IAAM,SAAA,EAAN,MAAe;AAAA,EAeb,WAAA,CAAA,EAAc;AACZ,IAAA,IAAA,CAAK,MAAA,EAAQ,CAAC,CAAA;AACd,IAAA,IAAA,CAAK,QAAA,EAAU,KAAA,CAAA;AACf,IAAA,IAAA,CAAK,SAAA,EAAW,KAAA,CAAA;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAA,CAAK,IAAA,EAAY;AACf,IAAA,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,IAAI,CAAA;AACpB,IAAA,IAAA,CAAK,QAAA,EAAU,IAAA,CAAK,SAAA,EAAW,KAAA,CAAA;AAAA,EACjC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,GAAA,CAAI,CAAA,EAAW;AACb,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,CAAC,CAAA;AAAA,EACrB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,MAAA,CAAA,EAAS;AACX,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,MAAA;AAAA,EACpB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAA,CAAQ,CAAA,EAAuD;AAC7D,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,CAAA;AAAA,EACtB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,GAAA,CAAO,CAAA,EAAyD;AAC9D,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,GAAA,CAAI,CAAC,CAAA;AAAA,EACzB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAA,CAAK,CAAA,EAA0D;AAC7D,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,CAAC,CAAA;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,OAAA,CAAA,EAAU;AAER,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,MAAA,CAAA,EAAS;AAGP,IAAA,MAAM,QAAA,EAAU,IAAA,CAAK,KAAA,CAAM,MAAA,CAAO,CAAC,IAAA,EAAM,IAAA,EAAM,CAAA,EAAA,GAAM;AACjD,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EAAI,IAAA,CAAK,KAAA,CAAM,IAAI,CAAA,CAAE,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA;AAChE,QAAA,KAAA,EAAO,CAAA;AACT,MAAA,OAAO,IAAA;AAAA,IACT,CAAA,EAAG,CAAC,CAAA,EACJ,MAAA,EAAA,CAAS,QAAA,IAAY,EAAA,EAAI,IAAA,CAAK,OAAA,EAAS,OAAA,EAAA,EAAW,CAAA,EAClD,MAAA,EAAA,CAAS,QAAA,EAAU,CAAA,EAAA,EAAK,IAAA,CAAK,MAAA,EAC7B,KAAA,EAAO,gBAAA;AAAA,MACL,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK,WAAA;AAAA,MACvB,IAAA,CAAK,KAAA,CAAM,OAAO,CAAA,CAAE,IAAA,CAAK,WAAA;AAAA,MACzB,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK;AAAA,IACzB,CAAA;AAEF,IAAA,GAAA,CAAI,KAAA,IAAS,CAAA;AACX,MAAA,OACE,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK,WAAA,CAAY,CAAC,EAAA,EACpC,IAAA,CAAK,KAAA,CAAM,KAAK,CAAA,CAAE,IAAA,CAAK,WAAA,CAAY,CAAC,CAAA;AAExC,IAAA,OAAO,KAAA,EAAO,CAAA;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,YAAA,CAAA,EAAe;AACb,IAAA,OAAO,iCAAA,IAAW,CAAK,KAAA,CAAM,GAAA,CAAI,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,IAAA,CAAK,WAAW,CAAC,CAAA;AAAA,EACnE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,SAAA,CAAA,EAAY;AACV,IAAA,GAAA,CAAI,IAAA,CAAK,OAAA,EAAS,OAAO,IAAA,CAAK,OAAA;AAC9B,IAAA,MAAM,YAAA,EAAc,IAAA,CAAK,KAAA,CAAM,GAAA,CAAI,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,IAAA,CAAK,WAAW,CAAA;AAClE,IAAA,WAAA,CAAY,IAAA,CAAK,IAAA,CAAK,KAAA,CAAM,CAAC,CAAA,CAAE,IAAA,CAAK,WAAW,CAAA;AAC/C,IAAA,OAAQ,IAAA,CAAK,QAAA,EAAU,8BAAA,CAAS,WAAW,CAAC,CAAA;AAAA,EAC9C;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,WAAA,CAAA,EAAc;AACZ,IAAA,GAAA,CAAI,IAAA,CAAK,QAAA,EAAU,OAAO,IAAA,CAAK,QAAA;AAC/B,IAAA,OAAQ,IAAA,CAAK,SAAA,EAAW,gCAAA,IAAS,CAAK,SAAA,CAAU,CAAC,CAAA;AAAA,EAInD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAO,sBAAA,CACL,YAAA,EACA,SAAA,EACsB;AACtB,IAAA,MAAM,aAAA,EAAe,YAAA,CAAa,WAAA,CAAY,CAAA;AAE9C,IAAA,IAAI,WAAA,EAA+B,QAAA;AACnC,IAAA,SAAA,CAAU,OAAA,CAAQ,CAAC,KAAA,EAAA,GAAU;AAC3B,MAAA,MAAM,YAAA,EAAc,KAAA,CAAM,WAAA,CAAY,CAAA;AAEtC,MAAA,GAAA,CAAI,QAAA,EAAU,YAAA,EAAc,QAAA,CAAS,WAAA,CAAY,CAAA;AAGjD,MAAA,GAAA,CAAI,eAAA,CAAgB,WAAA,EAAa,YAAY,CAAA,EAAG,MAAA;AAEhD,MAAA,GAAA,CAAI,gBAAA,CAAiB,WAAA,EAAa,YAAY,CAAA,EAAG;AAC/C,QAAA,MAAM,wBAAA,EAA0B,YAAA,CAAa,GAAA;AAAA,UAC3C,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,IAAA,CAAK;AAAA,QACtB,CAAA;AAEA,QAAA,IAAI,SAAA;AACJ,QAAA,IAAA,CAAA,MAAW,GAAA,GAAM,uBAAA,EAAyB;AACxC,UAAA,GAAA,CACE,CAAC,KAAA,CAAM,IAAA,CAAK,CAAC,IAAA,EAAA,GAAS,gBAAA,CAAiB,EAAA,EAAI,IAAA,CAAK,IAAA,CAAK,WAAW,CAAC,CAAA,EACjE;AACA,YAAA,UAAA,EAAY,EAAA;AAAA,UACd;AAAA,QACF;AAEA,QAAA,GAAA,CAAI,UAAA,GAAa,KAAA,CAAM,MAAA,CAAOA,4BAAAA,SAAe,CAAC,CAAA,EAAG;AAC/C,UAAA,GAAA,CAAI,CAAC,SAAA,GAAY,gBAAA,CAAiB,WAAA,EAAa,WAAW,CAAA;AACxD,YAAA,SAAA,EAAW,KAAA;AAAA,QACf;AAAA,MACF;AAAA,IACF,CAAC,CAAA;AAED,IAAA,OAAO,QAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,MAAA,CAAO,EAAA,EAAoB;AACzB,IAAA,OAAOC,0DAAAA,EAAsB,EAAI,IAAA,CAAK,SAAA,CAAU,CAAC,CAAA;AAAA,EACnD;AACF,CAAA;ALqHA;AACA;AMxWA,kCAAyC;AACzC,4CAA0B;AAe1B,SAAS,eAAA,CAAgB,OAAA,EAAqB;AAC5C,EAAA,GAAA,CAAI,CAAC,OAAA,EAAS,MAAM,IAAI,KAAA,CAAM,mBAAmB,CAAA;AAEjD,EAAA,GAAA,CACE,OAAA,CAAQ,KAAA,IAAS,oBAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,qBAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,kBAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,aAAA,GACjB,OAAA,CAAQ,KAAA,IAAS,SAAA;AAEjB,IAAA,MAAM,IAAI,KAAA;AAAA,MACR,CAAA,oBAAA,EAAuB,OAAA,CAAQ,IAAI,CAAA,gGAAA;AAAA,IACrC,CAAA;AACJ;AAWA,IAAM,MAAA,EAAN,MAAM,OAAM;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWV,OAAO,WAAA,CACL,OAAA,EAKA;AACA,IAAA,eAAA,CAAgB,OAAO,CAAA;AAEvB,IAAA,MAAM,MAAA,EAAQ,IAAI,MAAA,CAAM,CAAA;AACxB,IAAA,+BAAA,OAAY,EAAS,CAAC,OAAA,EAAA,GAAY;AAChC,MAAA,kCAAA,OAAU,EAAS,YAAA,EAAc,oBAAoB,CAAA;AAErD,MAAA,+BAAA,OAAsB,EAAS,CAAC,IAAA,EAAM,GAAA,EAAA,GAAQ;AAC5C,QAAA,GAAA,CAAI,IAAA,EAAM;AACR,UAAA,MAAM,MAAA,EAAQ,KAAA,CAAM,OAAA,CAAQ,IAAI,CAAA,EAC9B,IAAA,EAAM,KAAA,CAAM,OAAA,CAAQ,GAAG,CAAA;AAEzB,UAAA,KAAA,CAAM,OAAA,CAAQ,KAAA,EAAO,GAAG,CAAA;AAAA,QAC1B;AACA,QAAA,OAAO,GAAA;AAAA,MACT,CAAC,CAAA;AAAA,IACH,CAAC,CAAA;AAED,IAAA,OAAO,KAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAA,CAAQ,WAAA,EAAuB;AAC7B,IAAA,MAAM,GAAA,EAAK,IAAA,CAAK,OAAA,CAAQ,WAAW,CAAA;AACnC,IAAA,IAAI,KAAA,EAAO,IAAA,CAAK,KAAA,CAAM,EAAE,CAAA;AACxB,IAAA,GAAA,CAAI,CAAC,IAAA,EAAM,KAAA,EAAO,IAAA,CAAK,KAAA,CAAM,EAAE,EAAA,EAAI,IAAI,IAAA,CAAK,WAAW,CAAA;AAEvD,IAAA,OAAO,IAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAA,CAAQ,IAAA,EAAY,EAAA,EAAU;AAC5B,IAAA,MAAM,KAAA,EAAO,IAAI,IAAA,CAAK,IAAA,EAAM,EAAE,CAAA,EAC5B,aAAA,EAAe,IAAA,CAAK,WAAA,CAAY,CAAA;AAElC,IAAA,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,IAAI,CAAA;AACpB,IAAA,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,YAAY,CAAA;AAAA,EAC9B;AAAA,EAEA,WAAA,CAAA,EAAc;AACZ,IAAA,IAAA,CAAK,MAAA,EAAQ,CAAC,CAAA;AAGd,IAAA,IAAA,CAAK,MAAA,EAAQ,CAAC,CAAA;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA,EAKA,aAAA,CAAA,EAAgB;AACd,IAAA,MAAA,CAAO,IAAA,CAAK,IAAA,CAAK,KAAK,CAAA,CACnB,GAAA,CAAI,CAAC,EAAA,EAAA,GAAO,IAAA,CAAK,KAAA,CAAM,EAAE,CAAC,CAAA,CAC1B,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,eAAA,CAAgB,IAAI,CAAC,CAAA;AAAA,EACjD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,eAAA,CAAgB,IAAA,EAAY;AAE1B,IAAA,GAAA,CAAI,IAAA,CAAK,UAAA,CAAW,OAAA,GAAU,CAAA,EAAG;AAC/B,MAAA,MAAM,WAAA,EAAa,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,GAAA,CAAI,CAAC,CAAA,EAAA,GAAM,CAAA,CAAE,EAAE,CAAA;AACvD,MAAA,IAAA,CAAK,UAAA,CAAW,IAAI,CAAA;AACpB,MAAA,UAAA,CAAW,OAAA,CAAQ,CAAC,CAAA,EAAA,GAAM,IAAA,CAAK,eAAA,CAAgB,CAAC,CAAC,CAAA;AAAA,IACnD;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,cAAA,CAAA,EAAiB;AACf,IAAA,IAAA,CAAK,mBAAA,CAAoB,CAAA;AACzB,IAAA,IAAA,CAAK,qBAAA,CAAsB,CAAA;AAG3B,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,GAAA,CAAI,IAAA,CAAK,MAAA,IAAU,IAAA,CAAK,QAAA,CAAU,KAAA,EAAO;AACvC,QAAA,IAAA,CAAK,UAAA,CAAW,IAAA,CAAK,QAAS,CAAA;AAC9B,QAAA,IAAA,CAAK,UAAA,CAAW,IAAI,CAAA;AAAA,MACtB;AAAA,IACF,CAAC,CAAA;AAAA,EACH;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,mBAAA,CAAoB,IAAA,EAAa;AAC/B,IAAA,GAAA,CAAI,OAAO,KAAA,IAAS,WAAA,EAAa;AAC/B,MAAA,MAAA,CAAO,IAAA,CAAK,IAAA,CAAK,KAAK,CAAA,CAAE,OAAA;AAAA,QAAQ,CAAC,EAAA,EAAA,GAC/B,IAAA,CAAK,mBAAA,CAAoB,IAAA,CAAK,KAAA,CAAM,EAAE,CAAC;AAAA,MACzC,CAAA;AAAA,IACF,EAAA,KAAO;AACL,MAAA,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAM,CAAA,EAAA,GAAM;AACxC,QAAA,IAAA,CAAK,YAAA;AAAA,UAAA,CACF,EAAA,IAAM,EAAA,EAAI,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,EAAS,CAAA,EAAA,EAAK;AAAA,QAChD,CAAA,CAAE,QAAA,CAAU,KAAA,EAAO,IAAA;AAAA,MACrB,CAAC,CAAA;AAAA,IACH;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,oBAAA,CAAqB,IAAA,EAAY,KAAA,EAAe;AAC9C,IAAA,MAAM,MAAA,EAAQ,IAAA,CAAK,aAAA,CAAc,CAAA;AACjC,IAAA,IAAI,UAAA,EAAY,QAAA;AAEhB,IAAA,IAAA,CAAA,IAAS,EAAA,EAAI,KAAA,CAAM,OAAA,EAAS,CAAA,EAAG,EAAA,GAAK,CAAA,EAAG,EAAE,CAAA,EAAG;AAC1C,MAAA,IAAI,GAAA,EAAK,KAAA,CAAM,CAAC,CAAA,EACd,IAAA,EAAM,EAAA,CAAG,QAAA,EACT,KAAA,EACA,IAAA;AAEF,MAAA,GAAA,CAAI,EAAA,CAAG,MAAA,IAAU,KAAA,EAAO,MAAA,EAAQ,EAAA;AAEhC,MAAA,GAAA,CAAI,GAAA,CAAK,MAAA,IAAU,KAAA,EAAO,KAAA,EAAO,GAAA;AAEjC,MAAA,GAAA,CAAI,CAAC,MAAA,GAAS,CAAC,IAAA;AAEb,QAAA,QAAA;AAEF,MAAA,GAAA,CAAI,IAAA,EAAM,SAAA,EAAW,IAAA;AAErB,MAAA,GAAA,CAAI,KAAA,EAAO;AACT,QAAA,GAAA,CAAI,QAAA,EAAU;AACZ,UAAA,QAAA,CAAS,KAAA,EAAO,KAAA;AAChB,UAAA,SAAA,EAAW,KAAA,CAAA;AAAA,QACb;AAEA,QAAA,GAAA,CAAI,CAAC,UAAA,EAAY,WAAA,EAAa,KAAA;AAAA,MAChC;AAAA,IACF;AAEA,IAAA,GAAA,CAAI,QAAA,EAAU,QAAA,CAAS,KAAA,EAAO,UAAA;AAAA,EAChC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,qBAAA,CAAA,EAAwB;AACtB,IAAA,MAAM,eAAA,EAAyB,CAAC,CAAA;AAChC,IAAA,IAAI,MAAA,EAAQ,CAAA;AACZ,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,GAAA,CAAI,IAAA,CAAK,MAAA,GAAU,CAAA,EAAG,MAAA;AAEtB,MAAA,cAAA,CAAe,IAAA,CAAK,IAAI,CAAA;AAExB,MAAA,IAAI,EAAA,EAAI,IAAA;AACR,MAAA,GAAG;AACD,QAAA,CAAA,CAAE,MAAA,EAAQ,KAAA;AACV,QAAA,EAAA,EAAI,CAAA,CAAE,IAAA;AAAA,MACR,EAAA,MAAA,CAAS,CAAC,IAAA,CAAK,OAAA,CAAQ,CAAC,CAAA,CAAA;AAExB,MAAA,KAAA,EAAA;AAAA,IACF,CAAC,CAAA;AAED,IAAA,OAAO,cAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,YAAA,CAAA,EAAe;AACb,IAAA,IAAA,CAAK,mBAAA,CAAoB,CAAA;AAGzB,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,IAAA,CAAK,MAAA,EAAQ,KAAA,CAAA;AAAA,IACf,CAAC,CAAA;AAED,IAAA,IAAA,CAAK,qBAAA,CAAsB,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAE7C,MAAA,IAAA,CAAK,sBAAA,CAAuB,IAAI,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAClD,QAAA,IAAA,CAAK,oBAAA,CAAqB,IAAA,EAAM,IAAA,CAAK,KAAM,CAAA;AAAA,MAC7C,CAAC,CAAA;AAAA,IACH,CAAC,CAAA;AAED,IAAA,MAAM,aAAA,EAA2B,CAAC,CAAA;AAGlC,IAAA,IAAA,CAAK,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AAC3B,MAAA,GAAA,CAAI,IAAA,CAAK,IAAA,EAAM,MAAA;AACf,MAAA,YAAA,CAAa,IAAA,CAAK,IAAA,CAAK,aAAA,CAAc,IAAI,CAAC,CAAA;AAAA,IAC5C,CAAC,CAAA;AAED,IAAA,OAAO,YAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,sBAAA,CAAuB,SAAA,EAAiB;AACtC,IAAA,MAAM,kBAAA,EAAoB,CAAC,CAAA;AAC3B,IAAA,IAAI,KAAA,EAAO,SAAA;AACX,IAAA,GAAG;AAED,MAAA,IAAI,OAAA,EAAS,CAAA;AACb,MAAA,IAAA,CAAK,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,CAAQ,CAAC,CAAA,EAAA,GAAM;AACvC,QAAA,GAAA,CAAI,CAAA,CAAE,MAAA,IAAU,SAAA,CAAU,KAAA,EAAO,EAAE,MAAA;AAAA,MACrC,CAAC,CAAA;AAED,MAAA,GAAA,CAAI,OAAA,EAAS,CAAA,EAAG,iBAAA,CAAkB,IAAA,CAAK,IAAA,CAAK,IAAI,CAAA;AAEhD,MAAA,KAAA,EAAO,IAAA,CAAK,IAAA;AAAA,IACd,EAAA,MAAA,CAAS,CAAC,SAAA,CAAU,OAAA,CAAQ,IAAI,CAAA,CAAA;AAEhC,IAAA,OAAO,iBAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,aAAA,CAAc,SAAA,EAAiB;AAC7B,IAAA,IAAI,KAAA,EAAO,SAAA;AACX,IAAA,MAAM,SAAA,EAAW,IAAI,QAAA,CAAS,CAAA;AAE9B,IAAA,GAAG;AACD,MAAA,QAAA,CAAS,IAAA,CAAK,IAAI,CAAA;AAClB,MAAA,IAAA,CAAK,KAAA,EAAO,QAAA;AACZ,MAAA,KAAA,EAAO,IAAA,CAAK,IAAA;AAAA,IACd,EAAA,MAAA,CAAS,CAAC,SAAA,CAAU,OAAA,CAAQ,IAAI,CAAA,CAAA;AAEhC,IAAA,OAAO,QAAA;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,UAAA,CAAW,IAAA,EAAY;AACrB,IAAA,IAAA,CAAK,aAAA,CAAc,CAAA,CAAE,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,UAAA,CAAW,IAAI,CAAC,CAAA;AAC5D,IAAA,IAAA,CAAK,UAAA,CAAW,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS,IAAA,CAAK,UAAA,CAAW,IAAI,CAAC,CAAA;AACvD,IAAA,OAAO,IAAA,CAAK,KAAA,CAAM,IAAA,CAAK,EAAE,CAAA;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,UAAA,CAAW,IAAA,EAAY;AACrB,IAAA,IAAA,CAAK,MAAA,EAAQ,IAAA,CAAK,KAAA,CAAM,MAAA,CAAO,CAAC,CAAA,EAAA,GAAM,CAAC,CAAA,CAAE,OAAA,CAAQ,IAAI,CAAC,CAAA;AACtD,IAAA,IAAA,CAAK,UAAA,CAAW,CAAA;AAAA,EAClB;AACF,CAAA;ANuQA;AACA;AC1kBA,SAAS,UAAA,CACP,OAAA,EAC4B;AAC5B,EAAA,MAAM,MAAA,EAAQ,KAAA,CAAM,WAAA,CAAY,OAAO,CAAA;AAGvC,EAAA,KAAA,CAAM,aAAA,CAAc,CAAA;AAGpB,EAAA,KAAA,CAAM,cAAA,CAAe,CAAA;AAGrB,EAAA,MAAM,MAAA,EAAoB,CAAC,CAAA,EACzB,OAAA,EAAqB,CAAC,CAAA;AAExB,EAAA,KAAA,CACG,YAAA,CAAa,CAAA,CACb,MAAA,CAAO,CAAC,QAAA,EAAA,GAAa,QAAA,CAAS,OAAA,CAAQ,CAAC,CAAA,CACvC,OAAA,CAAQ,CAAC,QAAA,EAAA,GAAa;AACrB,IAAA,GAAA,CAAI,QAAA,CAAS,MAAA,CAAO,CAAA,EAAG,KAAA,CAAM,IAAA,CAAK,QAAQ,CAAA;AAAA,IAAA,KACrC,MAAA,CAAO,IAAA,CAAK,QAAQ,CAAA;AAAA,EAC3B,CAAC,CAAA;AAGH,EAAA,KAAA,CAAM,OAAA,CAAQ,CAAC,IAAA,EAAA,GAAS;AACtB,IAAA,GAAA,CAAI,QAAA,CAAS,sBAAA,CAAuB,IAAA,EAAM,MAAM,CAAA,EAAG,MAAA,CAAO,IAAA,CAAK,IAAI,CAAA;AAAA,EACrE,CAAC,CAAA;AAGD,EAAA,OAAO,wCAAA,MAAkB,CAAO,GAAA,CAAI,CAAC,KAAA,EAAA,GAAU,KAAA,CAAM,SAAA,CAAU,CAAC,CAAC,CAAA;AACnE;AAGA,IAAO,cAAA,EAAQ,UAAA;ADyjBf;AACE;AACA;AACF,iEAAC","file":"/home/runner/work/turf/turf/packages/turf-polygonize/dist/cjs/index.cjs","sourcesContent":[null,"import {\n Feature,\n FeatureCollection,\n LineString,\n MultiLineString,\n Polygon,\n} from \"geojson\";\nimport { featureCollection } from \"@turf/helpers\";\nimport { Graph } from \"./lib/Graph.js\";\nimport { EdgeRing } from \"./lib/EdgeRing.js\";\n\n/*\n Polygonizes {@link LineString\|(Multi)LineString(s)} into {@link Polygons}.\n \n Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).\n \n Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly\n * noded, i.e., they must only meet at their endpoints.\n \n The implementation correctly handles:\n \n - Dangles: edges which have one or both ends which are not incident on another edge endpoint.\n * - Cut Edges (bridges): edges that are connected at both ends but which do not form part of a polygon.\n \n @function\n * @param {FeatureCollection\|Geometry\|Feature<LineString\|MultiLineString>} geoJson Lines in order to polygonize\n * @returns {FeatureCollection<Polygon>} Polygons created\n * @throws {Error} if geoJson is invalid.\n /\nfunction polygonize<T extends LineString \| MultiLineString>(\n geoJson: Feature<T> \| FeatureCollection<T> \| T\n): FeatureCollection<Polygon> {\n const graph = Graph.fromGeoJson(geoJson);\n\n // 1. Remove dangle node\n graph.deleteDangles();\n\n // 2. Remove cut-edges (bridge edges)\n graph.deleteCutEdges();\n\n // 3. Get all holes and shells\n const holes: EdgeRing[] = [],\n shells: EdgeRing[] = [];\n\n graph\n .getEdgeRings()\n .filter((edgeRing) => edgeRing.isValid())\n .forEach((edgeRing) => {\n if (edgeRing.isHole()) holes.push(edgeRing);\n else shells.push(edgeRing);\n });\n\n // 4. Assign Holes to Shells\n holes.forEach((hole) => {\n if (EdgeRing.findEdgeRingContaining(hole, shells)) shells.push(hole);\n });\n\n // 5. EdgeRings to Polygons\n return featureCollection(shells.map((shell) => shell.toPolygon()));\n}\n\nexport { polygonize };\nexport default polygonize;\n","import { Feature, Polygon } from \"geojson\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { point } from \"@turf/helpers\";\n\n// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/sign#Polyfill\nfunction mathSign(x: number) {\n return ((x > 0) as unknown as number) - ((x < 0) as unknown as number) \|\| +x;\n}\n\n/\n Returns the direction of the point q relative to the vector p1 -> p2.\n \n Implementation of geos::algorithm::CGAlgorithm::orientationIndex()\n * (same as geos::algorithm::CGAlgorithm::computeOrientation())\n \n @param {number[]} p1 - the origin point of the vector\n * @param {number[]} p2 - the final point of the vector\n * @param {number[]} q - the point to compute the direction to\n \n @returns {number} - 1 if q is ccw (left) from p1->p2,\n * -1 if q is cw (right) from p1->p2,\n * 0 if q is colinear with p1->p2\n /\nexport function orientationIndex(p1: number[], p2: number[], q: number[]) {\n const dx1 = p2[0] - p1[0],\n dy1 = p2[1] - p1[1],\n dx2 = q[0] - p2[0],\n dy2 = q[1] - p2[1];\n\n return mathSign(dx1 dy2 - dx2 * dy1);\n}\n\n/*\n Checks if two envelopes are equal.\n \n The function assumes that the arguments are envelopes, i.e.: Rectangular polygon\n \n @param {Feature<Polygon>} env1 - Envelope\n * @param {Feature<Polygon>} env2 - Envelope\n * @returns {boolean} - True if the envelopes are equal\n /\nexport function envelopeIsEqual(\n env1: Feature<Polygon>,\n env2: Feature<Polygon>\n) {\n const envX1 = env1.geometry.coordinates[0].map((c) => c[0]),\n envY1 = env1.geometry.coordinates[0].map((c) => c[1]),\n envX2 = env2.geometry.coordinates[0].map((c) => c[0]),\n envY2 = env2.geometry.coordinates[0].map((c) => c[1]);\n\n return (\n Math.max.apply(null, envX1) === Math.max.apply(null, envX2) &&\n Math.max.apply(null, envY1) === Math.max.apply(null, envY2) &&\n Math.min.apply(null, envX1) === Math.min.apply(null, envX2) &&\n Math.min.apply(null, envY1) === Math.min.apply(null, envY2)\n );\n}\n\n/\n Check if a envelope is contained in other one.\n \n The function assumes that the arguments are envelopes, i.e.: Convex polygon\n * XXX: Envelopes are rectangular, checking if a point is inside a rectangule is something easy,\n * this could be further improved.\n \n @param {Feature<Polygon>} self - Envelope\n * @param {Feature<Polygon>} env - Envelope\n * @returns {boolean} - True if env is contained in self\n /\nexport function envelopeContains(\n self: Feature<Polygon>,\n env: Feature<Polygon>\n) {\n return env.geometry.coordinates[0].every((c) =>\n booleanPointInPolygon(point(c), self)\n );\n}\n\n/\n Checks if two coordinates are equal.\n \n @param {number[]} coord1 - First coordinate\n * @param {number[]} coord2 - Second coordinate\n * @returns {boolean} - True if coordinates are equal\n /\nexport function coordinatesEqual(coord1: number[], coord2: number[]) {\n return coord1[0] === coord2[0] && coord1[1] === coord2[1];\n}\n","import { orientationIndex } from \"./util.js\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Node\n /\nclass Node {\n static buildId(coordinates: number[]) {\n return coordinates.join(\",\");\n }\n\n public id: string;\n public coordinates: number[];\n public innerEdges: Edge[];\n private outerEdges: Edge[];\n private outerEdgesSorted: boolean;\n\n constructor(coordinates: number[]) {\n this.id = Node.buildId(coordinates);\n this.coordinates = coordinates; //< {Number[]}\n this.innerEdges = []; //< {Edge[]}\n\n // We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does\n this.outerEdges = []; //< {Edge[]}\n this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted\n }\n\n removeInnerEdge(edge: Edge) {\n this.innerEdges = this.innerEdges.filter((e) => e.from.id !== edge.from.id);\n }\n\n removeOuterEdge(edge: Edge) {\n this.outerEdges = this.outerEdges.filter((e) => e.to.id !== edge.to.id);\n }\n\n /\n Outer edges are stored CCW order.\n \n @memberof Node\n * @param {Edge} edge - Edge to add as an outerEdge.\n /\n addOuterEdge(edge: Edge) {\n this.outerEdges.push(edge);\n this.outerEdgesSorted = false;\n }\n\n /\n Sorts outer edges in CCW way.\n \n @memberof Node\n * @private\n /\n sortOuterEdges() {\n if (!this.outerEdgesSorted) {\n //this.outerEdges.sort((a, b) => a.compareTo(b));\n // Using this comparator in order to be deterministic\n this.outerEdges.sort((a, b) => {\n const aNode = a.to,\n bNode = b.to;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] >= 0 &&\n bNode.coordinates[0] - this.coordinates[0] < 0\n )\n return 1;\n if (\n aNode.coordinates[0] - this.coordinates[0] < 0 &&\n bNode.coordinates[0] - this.coordinates[0] >= 0\n )\n return -1;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] === 0 &&\n bNode.coordinates[0] - this.coordinates[0] === 0\n ) {\n if (\n aNode.coordinates[1] - this.coordinates[1] >= 0 \|\|\n bNode.coordinates[1] - this.coordinates[1] >= 0\n )\n return aNode.coordinates[1] - bNode.coordinates[1];\n return bNode.coordinates[1] - aNode.coordinates[1];\n }\n\n const det = orientationIndex(\n this.coordinates,\n aNode.coordinates,\n bNode.coordinates\n );\n if (det < 0) return 1;\n if (det > 0) return -1;\n\n const d1 =\n Math.pow(aNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(aNode.coordinates[1] - this.coordinates[1], 2),\n d2 =\n Math.pow(bNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(bNode.coordinates[1] - this.coordinates[1], 2);\n\n return d1 - d2;\n });\n this.outerEdgesSorted = true;\n }\n }\n\n /\n Retrieves outer edges.\n \n They are sorted if they aren't in the CCW order.\n \n @memberof Node\n * @returns {Edge[]} - List of outer edges sorted in a CCW order.\n /\n getOuterEdges() {\n this.sortOuterEdges();\n return this.outerEdges;\n }\n\n getOuterEdge(i: number) {\n this.sortOuterEdges();\n return this.outerEdges[i];\n }\n\n addInnerEdge(edge: Edge) {\n this.innerEdges.push(edge);\n }\n}\n\nexport { Node };\nexport default Node;\n","import { lineString } from \"@turf/helpers\";\nimport { orientationIndex } from \"./util.js\";\nimport { Node } from \"./Node.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\n\n/\n This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge\n /\nclass Edge {\n public label?: number;\n public symetric?: Edge;\n public from: Node;\n public to: Node;\n public next?: Edge;\n public ring?: EdgeRing;\n\n /\n Creates or get the symetric Edge.\n \n @returns {Edge} - Symetric Edge.\n /\n getSymetric() {\n if (!this.symetric) {\n this.symetric = new Edge(this.to, this.from);\n this.symetric.symetric = this;\n }\n\n return this.symetric;\n }\n\n /\n @param {Node} from - start node of the Edge\n * @param {Node} to - end node of the edge\n /\n constructor(from: Node, to: Node) {\n this.from = from; //< start\n this.to = to; //< End\n\n this.next = undefined; //< The edge to be computed after\n this.label = undefined; //< Used in order to detect Cut Edges (Bridges)\n this.symetric = undefined; //< The symetric edge of this\n this.ring = undefined; //< EdgeRing in which the Edge is\n\n this.from.addOuterEdge(this);\n this.to.addInnerEdge(this);\n }\n\n /\n Removes edge from from and to nodes.\n /\n deleteEdge() {\n this.from.removeOuterEdge(this);\n this.to.removeInnerEdge(this);\n }\n\n /\n Compares Edge equallity.\n \n An edge is equal to another, if the from and to nodes are the same.\n \n @param {Edge} edge - Another Edge\n * @returns {boolean} - True if Edges are equal, False otherwise\n /\n isEqual(edge: Edge) {\n return this.from.id === edge.from.id && this.to.id === edge.to.id;\n }\n\n toString() {\n return `Edge { ${this.from.id} -> ${this.to.id} }`;\n }\n\n /\n Returns a LineString representation of the Edge\n \n @returns {Feature<LineString>} - LineString representation of the Edge\n /\n toLineString() {\n return lineString([this.from.coordinates, this.to.coordinates]);\n }\n\n /\n Comparator of two edges.\n \n Implementation of geos::planargraph::DirectedEdge::compareTo.\n \n @param {Edge} edge - Another edge to compare with this one\n * @returns {number} -1 if this Edge has a greater angle with the positive x-axis than b,\n * 0 if the Edges are colinear,\n * 1 otherwise\n /\n compareTo(edge: Edge) {\n return orientationIndex(\n edge.from.coordinates,\n edge.to.coordinates,\n this.to.coordinates\n );\n }\n}\n\nexport { Edge };\nexport default Edge;\n","import { Polygon, Feature, Point, Position } from \"geojson\";\nimport {\n orientationIndex,\n envelopeIsEqual,\n envelopeContains,\n coordinatesEqual,\n} from \"./util.js\";\nimport { multiPoint, polygon, point } from \"@turf/helpers\";\nimport { envelope } from \"@turf/envelope\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Ring of edges which form a polygon.\n \n The ring may be either an outer shell or a hole.\n \n This class is inspired in GEOS's geos::operation::polygonize::EdgeRing\n /\nclass EdgeRing {\n private edges: Edge[];\n private polygon?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n private envelope?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n\n constructor() {\n this.edges = [];\n this.polygon = undefined; //< Caches Polygon representation\n this.envelope = undefined; //< Caches Envelope representation\n }\n\n /\n Add an edge to the ring, inserting it in the last position.\n \n @memberof EdgeRing\n * @param {Edge} edge - Edge to be inserted\n /\n push(edge: Edge) {\n this.edges.push(edge);\n this.polygon = this.envelope = undefined;\n }\n\n /\n Get Edge.\n \n @memberof EdgeRing\n * @param {number} i - Index\n * @returns {Edge} - Edge in the i position\n /\n get(i: number) {\n return this.edges[i];\n }\n\n /\n Getter of length property.\n \n @memberof EdgeRing\n * @returns {number} - Length of the edge ring.\n /\n get length() {\n return this.edges.length;\n }\n\n /\n Similar to Array.prototype.forEach for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.forEach\n /\n forEach(f: (edge: Edge, index: number, array: Edge[]) => void) {\n this.edges.forEach(f);\n }\n\n /\n Similar to Array.prototype.map for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.map\n * @returns {Array} - The mapped values in the function\n /\n map<T>(f: (edge: Edge, index: number, array: Edge[]) => T): T[] {\n return this.edges.map(f);\n }\n\n /\n Similar to Array.prototype.some for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.some\n * @returns {boolean} - True if an Edge check the condition\n /\n some(f: (edge: Edge, index: number, array: Edge[]) => boolean) {\n return this.edges.some(f);\n }\n\n /\n Check if the ring is valid in geomtry terms.\n \n A ring must have either 0 or 4 or more points. The first and the last must be\n * equal (in 2D)\n * geos::geom::LinearRing::validateConstruction\n \n @memberof EdgeRing\n * @returns {boolean} - Validity of the EdgeRing\n /\n isValid() {\n // TODO: stub\n return true;\n }\n\n /\n Tests whether this ring is a hole.\n \n A ring is a hole if it is oriented counter-clockwise.\n * Similar implementation of geos::algorithm::CGAlgorithms::isCCW\n \n @memberof EdgeRing\n * @returns {boolean} - true: if it is a hole\n /\n isHole() {\n // XXX: Assuming Ring is valid\n // Find highest point\n const hiIndex = this.edges.reduce((high, edge, i) => {\n if (edge.from.coordinates[1] > this.edges[high].from.coordinates[1])\n high = i;\n return high;\n }, 0),\n iPrev = (hiIndex === 0 ? this.length : hiIndex) - 1,\n iNext = (hiIndex + 1) % this.length,\n disc = orientationIndex(\n this.edges[iPrev].from.coordinates,\n this.edges[hiIndex].from.coordinates,\n this.edges[iNext].from.coordinates\n );\n\n if (disc === 0)\n return (\n this.edges[iPrev].from.coordinates[0] >\n this.edges[iNext].from.coordinates[0]\n );\n return disc > 0;\n }\n\n /\n Creates a MultiPoint representing the EdgeRing (discarts edges directions).\n \n @memberof EdgeRing\n * @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing\n /\n toMultiPoint() {\n return multiPoint(this.edges.map((edge) => edge.from.coordinates));\n }\n\n /\n Creates a Polygon representing the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - Polygon representation of the Edge Ring\n /\n toPolygon() {\n if (this.polygon) return this.polygon;\n const coordinates = this.edges.map((edge) => edge.from.coordinates);\n coordinates.push(this.edges[0].from.coordinates);\n return (this.polygon = polygon([coordinates]));\n }\n\n /\n Calculates the envelope of the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - envelope\n /\n getEnvelope() {\n if (this.envelope) return this.envelope;\n return (this.envelope = envelope(this.toPolygon()) as Feature<\n Polygon,\n { [name: string]: any }\n >);\n }\n\n /\n `geos::operation::polygonize::EdgeRing::findEdgeRingContaining`\n \n @param {EdgeRing} testEdgeRing - EdgeRing to look in the list\n * @param {EdgeRing[]} shellList - List of EdgeRing in which to search\n \n @returns {EdgeRing} - EdgeRing which contains the testEdgeRing\n /\n static findEdgeRingContaining(\n testEdgeRing: EdgeRing,\n shellList: EdgeRing[]\n ): EdgeRing \| undefined {\n const testEnvelope = testEdgeRing.getEnvelope();\n\n let minEnvelope: Feature<Polygon>, minShell: EdgeRing \| undefined;\n shellList.forEach((shell) => {\n const tryEnvelope = shell.getEnvelope();\n\n if (minShell) minEnvelope = minShell.getEnvelope();\n\n // the hole envelope cannot equal the shell envelope\n if (envelopeIsEqual(tryEnvelope, testEnvelope)) return;\n\n if (envelopeContains(tryEnvelope, testEnvelope)) {\n const testEdgeRingCoordinates = testEdgeRing.map(\n (edge) => edge.from.coordinates\n );\n\n let testPoint: Position \| undefined;\n for (const pt of testEdgeRingCoordinates) {\n if (\n !shell.some((edge) => coordinatesEqual(pt, edge.from.coordinates))\n ) {\n testPoint = pt;\n }\n }\n\n if (testPoint && shell.inside(point(testPoint))) {\n if (!minShell \|\| envelopeContains(minEnvelope, tryEnvelope))\n minShell = shell;\n }\n }\n });\n\n return minShell;\n }\n\n /\n Checks if the point is inside the edgeRing\n \n @param {Feature<Point>} pt - Point to check if it is inside the edgeRing\n * @returns {boolean} - True if it is inside, False otherwise\n /\n inside(pt: Feature<Point>) {\n return booleanPointInPolygon(pt, this.toPolygon());\n }\n}\n\nexport { EdgeRing };\nexport default EdgeRing;\n","import { Node } from \"./Node.js\";\nimport { Edge } from \"./Edge.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\nimport { flattenEach, coordReduce } from \"@turf/meta\";\nimport { featureOf } from \"@turf/invariant\";\nimport {\n FeatureCollection,\n LineString,\n MultiLineString,\n Feature,\n} from \"geojson\";\nimport { AllGeoJSON } from \"@turf/helpers\";\n\n/\n Validates the geoJson.\n \n @param {GeoJSON} geoJson - input geoJson.\n * @throws {Error} if geoJson is invalid.\n /\nfunction validateGeoJson(geoJson: AllGeoJSON) {\n if (!geoJson) throw new Error(\"No geojson passed\");\n\n if (\n geoJson.type !== \"FeatureCollection\" &&\n geoJson.type !== \"GeometryCollection\" &&\n geoJson.type !== \"MultiLineString\" &&\n geoJson.type !== \"LineString\" &&\n geoJson.type !== \"Feature\"\n )\n throw new Error(\n `Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`\n );\n}\n\n/\n Represents a planar graph of edges and nodes that can be used to compute a polygonization.\n \n Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,\n * it isn't a rewrite. As regards algorithm, this class implements the same logic, but it\n * isn't a javascript transcription of the C++ source.\n \n This graph is directed (both directions are created)\n /\nclass Graph {\n private nodes: { [id: string]: Node };\n private edges: Edge[];\n\n /\n Creates a graph from a GeoJSON.\n \n @param {FeatureCollection<LineString>} geoJson - it must comply with the restrictions detailed in the index\n * @returns {Graph} - The newly created graph\n * @throws {Error} if geoJson is invalid.\n /\n static fromGeoJson(\n geoJson:\n \| FeatureCollection<LineString \| MultiLineString>\n \| LineString\n \| MultiLineString\n \| Feature<LineString \| MultiLineString>\n ) {\n validateGeoJson(geoJson);\n\n const graph = new Graph();\n flattenEach(geoJson, (feature) => {\n featureOf(feature, \"LineString\", \"Graph::fromGeoJson\");\n // When a LineString if formed by many segments, split them\n coordReduce<number[]>(feature, (prev, cur) => {\n if (prev) {\n const start = graph.getNode(prev),\n end = graph.getNode(cur);\n\n graph.addEdge(start, end);\n }\n return cur;\n });\n });\n\n return graph;\n }\n\n /\n Creates or get a Node.\n \n @param {number[]} coordinates - Coordinates of the node\n * @returns {Node} - The created or stored node\n /\n getNode(coordinates: number[]) {\n const id = Node.buildId(coordinates);\n let node = this.nodes[id];\n if (!node) node = this.nodes[id] = new Node(coordinates);\n\n return node;\n }\n\n /\n Adds an Edge and its symetricall.\n \n Edges are added symetrically, i.e.: we also add its symetric\n \n @param {Node} from - Node which starts the Edge\n * @param {Node} to - Node which ends the Edge\n /\n addEdge(from: Node, to: Node) {\n const edge = new Edge(from, to),\n symetricEdge = edge.getSymetric();\n\n this.edges.push(edge);\n this.edges.push(symetricEdge);\n }\n\n constructor() {\n this.edges = []; //< {Edge[]} dirEdges\n\n // The key is the `id` of the Node (ie: coordinates.join(','))\n this.nodes = {};\n }\n\n /\n Removes Dangle Nodes (nodes with grade 1).\n /\n deleteDangles() {\n Object.keys(this.nodes)\n .map((id) => this.nodes[id])\n .forEach((node) => this._removeIfDangle(node));\n }\n\n /\n Check if node is dangle, if so, remove it.\n \n It calls itself recursively, removing a dangling node might cause another dangling node\n \n @param {Node} node - Node to check if it's a dangle\n /\n _removeIfDangle(node: Node) {\n // As edges are directed and symetrical, we count only innerEdges\n if (node.innerEdges.length <= 1) {\n const outerNodes = node.getOuterEdges().map((e) => e.to);\n this.removeNode(node);\n outerNodes.forEach((n) => this._removeIfDangle(n));\n }\n }\n\n /\n Delete cut-edges (bridge edges).\n \n The graph will be traversed, all the edges will be labeled according the ring\n * in which they are. (The label is a number incremented by 1). Edges with the same\n * label are cut-edges.\n /\n deleteCutEdges() {\n this._computeNextCWEdges();\n this._findLabeledEdgeRings();\n\n // Cut-edges (bridges) are edges where both edges have the same label\n this.edges.forEach((edge) => {\n if (edge.label === edge.symetric!.label) {\n this.removeEdge(edge.symetric!);\n this.removeEdge(edge);\n }\n });\n }\n\n /\n Set the `next` property of each Edge.\n \n The graph will be transversed in a CW form, so, we set the next of the symetrical edge as the previous one.\n * OuterEdges are sorted CCW.\n \n @param {Node} [node] - If no node is passed, the function calls itself for every node in the Graph\n /\n _computeNextCWEdges(node?: Node) {\n if (typeof node === \"undefined\") {\n Object.keys(this.nodes).forEach((id) =>\n this._computeNextCWEdges(this.nodes[id])\n );\n } else {\n node.getOuterEdges().forEach((edge, i) => {\n node.getOuterEdge(\n (i === 0 ? node.getOuterEdges().length : i) - 1\n ).symetric!.next = edge;\n });\n }\n }\n\n /\n Computes the next edge pointers going CCW around the given node, for the given edgering label.\n \n This algorithm has the effect of converting maximal edgerings into minimal edgerings\n \n XXX: method literally transcribed from `geos::operation::polygonize::PolygonizeGraph::computeNextCCWEdges`,\n * could be written in a more javascript way.\n \n @param {Node} node - Node\n * @param {number} label - Ring's label\n /\n _computeNextCCWEdges(node: Node, label: number) {\n const edges = node.getOuterEdges();\n let firstOutDE, prevInDE;\n\n for (let i = edges.length - 1; i >= 0; --i) {\n let de = edges[i],\n sym = de.symetric,\n outDE,\n inDE;\n\n if (de.label === label) outDE = de;\n\n if (sym!.label === label) inDE = sym;\n\n if (!outDE \|\| !inDE)\n // This edge is not in edgering\n continue;\n\n if (inDE) prevInDE = inDE;\n\n if (outDE) {\n if (prevInDE) {\n prevInDE.next = outDE;\n prevInDE = undefined;\n }\n\n if (!firstOutDE) firstOutDE = outDE;\n }\n }\n\n if (prevInDE) prevInDE.next = firstOutDE;\n }\n\n /\n Finds rings and labels edges according to which rings are.\n \n The label is a number which is increased for each ring.\n \n @returns {Edge[]} edges that start rings\n /\n _findLabeledEdgeRings() {\n const edgeRingStarts: Edge[] = [];\n let label = 0;\n this.edges.forEach((edge) => {\n if (edge.label! >= 0) return;\n\n edgeRingStarts.push(edge);\n\n let e = edge;\n do {\n e.label = label;\n e = e.next!;\n } while (!edge.isEqual(e));\n\n label++;\n });\n\n return edgeRingStarts;\n }\n\n /\n Computes the EdgeRings formed by the edges in this graph.\n \n @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.\n /\n getEdgeRings() {\n this._computeNextCWEdges();\n\n // Clear labels\n this.edges.forEach((edge) => {\n edge.label = undefined;\n });\n\n this._findLabeledEdgeRings().forEach((edge) => {\n // convertMaximalToMinimalEdgeRings\n this._findIntersectionNodes(edge).forEach((node) => {\n this._computeNextCCWEdges(node, edge.label!);\n });\n });\n\n const edgeRingList: EdgeRing[] = [];\n\n // find all edgerings\n this.edges.forEach((edge) => {\n if (edge.ring) return;\n edgeRingList.push(this._findEdgeRing(edge));\n });\n\n return edgeRingList;\n }\n\n /\n Find all nodes in a Maxima EdgeRing which are self-intersection nodes.\n \n @param {Node} startEdge - Start Edge of the Ring\n * @returns {Node[]} - intersection nodes\n /\n _findIntersectionNodes(startEdge: Edge) {\n const intersectionNodes = [];\n let edge = startEdge;\n do {\n // getDegree\n let degree = 0;\n edge.from.getOuterEdges().forEach((e) => {\n if (e.label === startEdge.label) ++degree;\n });\n\n if (degree > 1) intersectionNodes.push(edge.from);\n\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return intersectionNodes;\n }\n\n /\n Get the edge-ring which starts from the provided Edge.\n \n @param {Edge} startEdge - starting edge of the edge ring\n * @returns {EdgeRing} - EdgeRing which start Edge is the provided one.\n /\n _findEdgeRing(startEdge: Edge) {\n let edge = startEdge;\n const edgeRing = new EdgeRing();\n\n do {\n edgeRing.push(edge);\n edge.ring = edgeRing;\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return edgeRing;\n }\n\n /\n Removes a node from the Graph.\n \n It also removes edges asociated to that node\n * @param {Node} node - Node to be removed\n /\n removeNode(node: Node) {\n node.getOuterEdges().forEach((edge) => this.removeEdge(edge));\n node.innerEdges.forEach((edge) => this.removeEdge(edge));\n delete this.nodes[node.id];\n }\n\n /\n Remove edge from the graph and deletes the edge.\n \n @param {Edge} edge - Edge to be removed\n */\n removeEdge(edge: Edge) {\n this.edges = this.edges.filter((e) => !e.isEqual(edge));\n edge.deleteEdge();\n }\n}\n\nexport { Graph };\nexport default Graph;\n"]}

+2

-2

dist/esm/index.js

		@@ -631,7 +631,7 @@ // index.ts
		}
		var turf_polygonize_default = polygonize;
		var index_default = polygonize;
		export {
		turf_polygonize_default as default,
		index_default as default,
		polygonize
		};
		//# sourceMappingURL=index.js.map

+1

-1

dist/esm/index.js.map

		@@ -1,1 +0,1 @@
		{"version":3,"sources":["../../index.ts","../../lib/util.ts","../../lib/Node.ts","../../lib/Edge.ts","../../lib/EdgeRing.ts","../../lib/Graph.ts"],"sourcesContent":["import {\n Feature,\n FeatureCollection,\n LineString,\n MultiLineString,\n Polygon,\n} from \"geojson\";\nimport { featureCollection } from \"@turf/helpers\";\nimport { Graph } from \"./lib/Graph.js\";\nimport { EdgeRing } from \"./lib/EdgeRing.js\";\n\n/*\n Polygonizes {@link LineString\|(Multi)LineString(s)} into {@link Polygons}.\n \n Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).\n \n Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly\n * noded, i.e., they must only meet at their endpoints.\n \n The implementation correctly handles:\n \n - Dangles: edges which have one or both ends which are not incident on another edge endpoint.\n * - Cut Edges (bridges): edges that are connected at both ends but which do not form part of a polygon.\n \n @function\n * @param {FeatureCollection\|Geometry\|Feature<LineString\|MultiLineString>} geoJson Lines in order to polygonize\n * @returns {FeatureCollection<Polygon>} Polygons created\n * @throws {Error} if geoJson is invalid.\n /\nfunction polygonize<T extends LineString \| MultiLineString>(\n geoJson: Feature<T> \| FeatureCollection<T> \| T\n): FeatureCollection<Polygon> {\n const graph = Graph.fromGeoJson(geoJson);\n\n // 1. Remove dangle node\n graph.deleteDangles();\n\n // 2. Remove cut-edges (bridge edges)\n graph.deleteCutEdges();\n\n // 3. Get all holes and shells\n const holes: EdgeRing[] = [],\n shells: EdgeRing[] = [];\n\n graph\n .getEdgeRings()\n .filter((edgeRing) => edgeRing.isValid())\n .forEach((edgeRing) => {\n if (edgeRing.isHole()) holes.push(edgeRing);\n else shells.push(edgeRing);\n });\n\n // 4. Assign Holes to Shells\n holes.forEach((hole) => {\n if (EdgeRing.findEdgeRingContaining(hole, shells)) shells.push(hole);\n });\n\n // 5. EdgeRings to Polygons\n return featureCollection(shells.map((shell) => shell.toPolygon()));\n}\n\nexport { polygonize };\nexport default polygonize;\n","import { Feature, Polygon } from \"geojson\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { point } from \"@turf/helpers\";\n\n// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/sign#Polyfill\nfunction mathSign(x: number) {\n return ((x > 0) as unknown as number) - ((x < 0) as unknown as number) \|\| +x;\n}\n\n/\n Returns the direction of the point q relative to the vector p1 -> p2.\n \n Implementation of geos::algorithm::CGAlgorithm::orientationIndex()\n * (same as geos::algorithm::CGAlgorithm::computeOrientation())\n \n @param {number[]} p1 - the origin point of the vector\n * @param {number[]} p2 - the final point of the vector\n * @param {number[]} q - the point to compute the direction to\n \n @returns {number} - 1 if q is ccw (left) from p1->p2,\n * -1 if q is cw (right) from p1->p2,\n * 0 if q is colinear with p1->p2\n /\nexport function orientationIndex(p1: number[], p2: number[], q: number[]) {\n const dx1 = p2[0] - p1[0],\n dy1 = p2[1] - p1[1],\n dx2 = q[0] - p2[0],\n dy2 = q[1] - p2[1];\n\n return mathSign(dx1 dy2 - dx2 * dy1);\n}\n\n/*\n Checks if two envelopes are equal.\n \n The function assumes that the arguments are envelopes, i.e.: Rectangular polygon\n \n @param {Feature<Polygon>} env1 - Envelope\n * @param {Feature<Polygon>} env2 - Envelope\n * @returns {boolean} - True if the envelopes are equal\n /\nexport function envelopeIsEqual(\n env1: Feature<Polygon>,\n env2: Feature<Polygon>\n) {\n const envX1 = env1.geometry.coordinates[0].map((c) => c[0]),\n envY1 = env1.geometry.coordinates[0].map((c) => c[1]),\n envX2 = env2.geometry.coordinates[0].map((c) => c[0]),\n envY2 = env2.geometry.coordinates[0].map((c) => c[1]);\n\n return (\n Math.max.apply(null, envX1) === Math.max.apply(null, envX2) &&\n Math.max.apply(null, envY1) === Math.max.apply(null, envY2) &&\n Math.min.apply(null, envX1) === Math.min.apply(null, envX2) &&\n Math.min.apply(null, envY1) === Math.min.apply(null, envY2)\n );\n}\n\n/\n Check if a envelope is contained in other one.\n \n The function assumes that the arguments are envelopes, i.e.: Convex polygon\n * XXX: Envelopes are rectangular, checking if a point is inside a rectangule is something easy,\n * this could be further improved.\n \n @param {Feature<Polygon>} self - Envelope\n * @param {Feature<Polygon>} env - Envelope\n * @returns {boolean} - True if env is contained in self\n /\nexport function envelopeContains(\n self: Feature<Polygon>,\n env: Feature<Polygon>\n) {\n return env.geometry.coordinates[0].every((c) =>\n booleanPointInPolygon(point(c), self)\n );\n}\n\n/\n Checks if two coordinates are equal.\n \n @param {number[]} coord1 - First coordinate\n * @param {number[]} coord2 - Second coordinate\n * @returns {boolean} - True if coordinates are equal\n /\nexport function coordinatesEqual(coord1: number[], coord2: number[]) {\n return coord1[0] === coord2[0] && coord1[1] === coord2[1];\n}\n","import { orientationIndex } from \"./util.js\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Node\n /\nclass Node {\n static buildId(coordinates: number[]) {\n return coordinates.join(\",\");\n }\n\n public id: string;\n public coordinates: number[];\n public innerEdges: Edge[];\n private outerEdges: Edge[];\n private outerEdgesSorted: boolean;\n\n constructor(coordinates: number[]) {\n this.id = Node.buildId(coordinates);\n this.coordinates = coordinates; //< {Number[]}\n this.innerEdges = []; //< {Edge[]}\n\n // We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does\n this.outerEdges = []; //< {Edge[]}\n this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted\n }\n\n removeInnerEdge(edge: Edge) {\n this.innerEdges = this.innerEdges.filter((e) => e.from.id !== edge.from.id);\n }\n\n removeOuterEdge(edge: Edge) {\n this.outerEdges = this.outerEdges.filter((e) => e.to.id !== edge.to.id);\n }\n\n /\n Outer edges are stored CCW order.\n \n @memberof Node\n * @param {Edge} edge - Edge to add as an outerEdge.\n /\n addOuterEdge(edge: Edge) {\n this.outerEdges.push(edge);\n this.outerEdgesSorted = false;\n }\n\n /\n Sorts outer edges in CCW way.\n \n @memberof Node\n * @private\n /\n sortOuterEdges() {\n if (!this.outerEdgesSorted) {\n //this.outerEdges.sort((a, b) => a.compareTo(b));\n // Using this comparator in order to be deterministic\n this.outerEdges.sort((a, b) => {\n const aNode = a.to,\n bNode = b.to;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] >= 0 &&\n bNode.coordinates[0] - this.coordinates[0] < 0\n )\n return 1;\n if (\n aNode.coordinates[0] - this.coordinates[0] < 0 &&\n bNode.coordinates[0] - this.coordinates[0] >= 0\n )\n return -1;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] === 0 &&\n bNode.coordinates[0] - this.coordinates[0] === 0\n ) {\n if (\n aNode.coordinates[1] - this.coordinates[1] >= 0 \|\|\n bNode.coordinates[1] - this.coordinates[1] >= 0\n )\n return aNode.coordinates[1] - bNode.coordinates[1];\n return bNode.coordinates[1] - aNode.coordinates[1];\n }\n\n const det = orientationIndex(\n this.coordinates,\n aNode.coordinates,\n bNode.coordinates\n );\n if (det < 0) return 1;\n if (det > 0) return -1;\n\n const d1 =\n Math.pow(aNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(aNode.coordinates[1] - this.coordinates[1], 2),\n d2 =\n Math.pow(bNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(bNode.coordinates[1] - this.coordinates[1], 2);\n\n return d1 - d2;\n });\n this.outerEdgesSorted = true;\n }\n }\n\n /\n Retrieves outer edges.\n \n They are sorted if they aren't in the CCW order.\n \n @memberof Node\n * @returns {Edge[]} - List of outer edges sorted in a CCW order.\n /\n getOuterEdges() {\n this.sortOuterEdges();\n return this.outerEdges;\n }\n\n getOuterEdge(i: number) {\n this.sortOuterEdges();\n return this.outerEdges[i];\n }\n\n addInnerEdge(edge: Edge) {\n this.innerEdges.push(edge);\n }\n}\n\nexport { Node };\nexport default Node;\n","import { lineString } from \"@turf/helpers\";\nimport { orientationIndex } from \"./util.js\";\nimport { Node } from \"./Node.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\n\n/\n This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge\n /\nclass Edge {\n public label?: number;\n public symetric?: Edge;\n public from: Node;\n public to: Node;\n public next?: Edge;\n public ring?: EdgeRing;\n\n /\n Creates or get the symetric Edge.\n \n @returns {Edge} - Symetric Edge.\n /\n getSymetric() {\n if (!this.symetric) {\n this.symetric = new Edge(this.to, this.from);\n this.symetric.symetric = this;\n }\n\n return this.symetric;\n }\n\n /\n @param {Node} from - start node of the Edge\n * @param {Node} to - end node of the edge\n /\n constructor(from: Node, to: Node) {\n this.from = from; //< start\n this.to = to; //< End\n\n this.next = undefined; //< The edge to be computed after\n this.label = undefined; //< Used in order to detect Cut Edges (Bridges)\n this.symetric = undefined; //< The symetric edge of this\n this.ring = undefined; //< EdgeRing in which the Edge is\n\n this.from.addOuterEdge(this);\n this.to.addInnerEdge(this);\n }\n\n /\n Removes edge from from and to nodes.\n /\n deleteEdge() {\n this.from.removeOuterEdge(this);\n this.to.removeInnerEdge(this);\n }\n\n /\n Compares Edge equallity.\n \n An edge is equal to another, if the from and to nodes are the same.\n \n @param {Edge} edge - Another Edge\n * @returns {boolean} - True if Edges are equal, False otherwise\n /\n isEqual(edge: Edge) {\n return this.from.id === edge.from.id && this.to.id === edge.to.id;\n }\n\n toString() {\n return `Edge { ${this.from.id} -> ${this.to.id} }`;\n }\n\n /\n Returns a LineString representation of the Edge\n \n @returns {Feature<LineString>} - LineString representation of the Edge\n /\n toLineString() {\n return lineString([this.from.coordinates, this.to.coordinates]);\n }\n\n /\n Comparator of two edges.\n \n Implementation of geos::planargraph::DirectedEdge::compareTo.\n \n @param {Edge} edge - Another edge to compare with this one\n * @returns {number} -1 if this Edge has a greater angle with the positive x-axis than b,\n * 0 if the Edges are colinear,\n * 1 otherwise\n /\n compareTo(edge: Edge) {\n return orientationIndex(\n edge.from.coordinates,\n edge.to.coordinates,\n this.to.coordinates\n );\n }\n}\n\nexport { Edge };\nexport default Edge;\n","import { Polygon, Feature, Point, Position } from \"geojson\";\nimport {\n orientationIndex,\n envelopeIsEqual,\n envelopeContains,\n coordinatesEqual,\n} from \"./util.js\";\nimport { multiPoint, polygon, point } from \"@turf/helpers\";\nimport { envelope } from \"@turf/envelope\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Ring of edges which form a polygon.\n \n The ring may be either an outer shell or a hole.\n \n This class is inspired in GEOS's geos::operation::polygonize::EdgeRing\n /\nclass EdgeRing {\n private edges: Edge[];\n private polygon?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n private envelope?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n\n constructor() {\n this.edges = [];\n this.polygon = undefined; //< Caches Polygon representation\n this.envelope = undefined; //< Caches Envelope representation\n }\n\n /\n Add an edge to the ring, inserting it in the last position.\n \n @memberof EdgeRing\n * @param {Edge} edge - Edge to be inserted\n /\n push(edge: Edge) {\n this.edges.push(edge);\n this.polygon = this.envelope = undefined;\n }\n\n /\n Get Edge.\n \n @memberof EdgeRing\n * @param {number} i - Index\n * @returns {Edge} - Edge in the i position\n /\n get(i: number) {\n return this.edges[i];\n }\n\n /\n Getter of length property.\n \n @memberof EdgeRing\n * @returns {number} - Length of the edge ring.\n /\n get length() {\n return this.edges.length;\n }\n\n /\n Similar to Array.prototype.forEach for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.forEach\n /\n forEach(f: (edge: Edge, index: number, array: Edge[]) => void) {\n this.edges.forEach(f);\n }\n\n /\n Similar to Array.prototype.map for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.map\n * @returns {Array} - The mapped values in the function\n /\n map<T>(f: (edge: Edge, index: number, array: Edge[]) => T): T[] {\n return this.edges.map(f);\n }\n\n /\n Similar to Array.prototype.some for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.some\n * @returns {boolean} - True if an Edge check the condition\n /\n some(f: (edge: Edge, index: number, array: Edge[]) => boolean) {\n return this.edges.some(f);\n }\n\n /\n Check if the ring is valid in geomtry terms.\n \n A ring must have either 0 or 4 or more points. The first and the last must be\n * equal (in 2D)\n * geos::geom::LinearRing::validateConstruction\n \n @memberof EdgeRing\n * @returns {boolean} - Validity of the EdgeRing\n /\n isValid() {\n // TODO: stub\n return true;\n }\n\n /\n Tests whether this ring is a hole.\n \n A ring is a hole if it is oriented counter-clockwise.\n * Similar implementation of geos::algorithm::CGAlgorithms::isCCW\n \n @memberof EdgeRing\n * @returns {boolean} - true: if it is a hole\n /\n isHole() {\n // XXX: Assuming Ring is valid\n // Find highest point\n const hiIndex = this.edges.reduce((high, edge, i) => {\n if (edge.from.coordinates[1] > this.edges[high].from.coordinates[1])\n high = i;\n return high;\n }, 0),\n iPrev = (hiIndex === 0 ? this.length : hiIndex) - 1,\n iNext = (hiIndex + 1) % this.length,\n disc = orientationIndex(\n this.edges[iPrev].from.coordinates,\n this.edges[hiIndex].from.coordinates,\n this.edges[iNext].from.coordinates\n );\n\n if (disc === 0)\n return (\n this.edges[iPrev].from.coordinates[0] >\n this.edges[iNext].from.coordinates[0]\n );\n return disc > 0;\n }\n\n /\n Creates a MultiPoint representing the EdgeRing (discarts edges directions).\n \n @memberof EdgeRing\n * @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing\n /\n toMultiPoint() {\n return multiPoint(this.edges.map((edge) => edge.from.coordinates));\n }\n\n /\n Creates a Polygon representing the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - Polygon representation of the Edge Ring\n /\n toPolygon() {\n if (this.polygon) return this.polygon;\n const coordinates = this.edges.map((edge) => edge.from.coordinates);\n coordinates.push(this.edges[0].from.coordinates);\n return (this.polygon = polygon([coordinates]));\n }\n\n /\n Calculates the envelope of the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - envelope\n /\n getEnvelope() {\n if (this.envelope) return this.envelope;\n return (this.envelope = envelope(this.toPolygon()) as Feature<\n Polygon,\n { [name: string]: any }\n >);\n }\n\n /\n `geos::operation::polygonize::EdgeRing::findEdgeRingContaining`\n \n @param {EdgeRing} testEdgeRing - EdgeRing to look in the list\n * @param {EdgeRing[]} shellList - List of EdgeRing in which to search\n \n @returns {EdgeRing} - EdgeRing which contains the testEdgeRing\n /\n static findEdgeRingContaining(\n testEdgeRing: EdgeRing,\n shellList: EdgeRing[]\n ): EdgeRing \| undefined {\n const testEnvelope = testEdgeRing.getEnvelope();\n\n let minEnvelope: Feature<Polygon>, minShell: EdgeRing \| undefined;\n shellList.forEach((shell) => {\n const tryEnvelope = shell.getEnvelope();\n\n if (minShell) minEnvelope = minShell.getEnvelope();\n\n // the hole envelope cannot equal the shell envelope\n if (envelopeIsEqual(tryEnvelope, testEnvelope)) return;\n\n if (envelopeContains(tryEnvelope, testEnvelope)) {\n const testEdgeRingCoordinates = testEdgeRing.map(\n (edge) => edge.from.coordinates\n );\n\n let testPoint: Position \| undefined;\n for (const pt of testEdgeRingCoordinates) {\n if (\n !shell.some((edge) => coordinatesEqual(pt, edge.from.coordinates))\n ) {\n testPoint = pt;\n }\n }\n\n if (testPoint && shell.inside(point(testPoint))) {\n if (!minShell \|\| envelopeContains(minEnvelope, tryEnvelope))\n minShell = shell;\n }\n }\n });\n\n return minShell;\n }\n\n /\n Checks if the point is inside the edgeRing\n \n @param {Feature<Point>} pt - Point to check if it is inside the edgeRing\n * @returns {boolean} - True if it is inside, False otherwise\n /\n inside(pt: Feature<Point>) {\n return booleanPointInPolygon(pt, this.toPolygon());\n }\n}\n\nexport { EdgeRing };\nexport default EdgeRing;\n","import { Node } from \"./Node.js\";\nimport { Edge } from \"./Edge.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\nimport { flattenEach, coordReduce } from \"@turf/meta\";\nimport { featureOf } from \"@turf/invariant\";\nimport {\n FeatureCollection,\n LineString,\n MultiLineString,\n Feature,\n} from \"geojson\";\nimport { AllGeoJSON } from \"@turf/helpers\";\n\n/\n Validates the geoJson.\n \n @param {GeoJSON} geoJson - input geoJson.\n * @throws {Error} if geoJson is invalid.\n /\nfunction validateGeoJson(geoJson: AllGeoJSON) {\n if (!geoJson) throw new Error(\"No geojson passed\");\n\n if (\n geoJson.type !== \"FeatureCollection\" &&\n geoJson.type !== \"GeometryCollection\" &&\n geoJson.type !== \"MultiLineString\" &&\n geoJson.type !== \"LineString\" &&\n geoJson.type !== \"Feature\"\n )\n throw new Error(\n `Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`\n );\n}\n\n/\n Represents a planar graph of edges and nodes that can be used to compute a polygonization.\n \n Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,\n * it isn't a rewrite. As regards algorithm, this class implements the same logic, but it\n * isn't a javascript transcription of the C++ source.\n \n This graph is directed (both directions are created)\n /\nclass Graph {\n private nodes: { [id: string]: Node };\n private edges: Edge[];\n\n /\n Creates a graph from a GeoJSON.\n \n @param {FeatureCollection<LineString>} geoJson - it must comply with the restrictions detailed in the index\n * @returns {Graph} - The newly created graph\n * @throws {Error} if geoJson is invalid.\n /\n static fromGeoJson(\n geoJson:\n \| FeatureCollection<LineString \| MultiLineString>\n \| LineString\n \| MultiLineString\n \| Feature<LineString \| MultiLineString>\n ) {\n validateGeoJson(geoJson);\n\n const graph = new Graph();\n flattenEach(geoJson, (feature) => {\n featureOf(feature, \"LineString\", \"Graph::fromGeoJson\");\n // When a LineString if formed by many segments, split them\n coordReduce<number[]>(feature, (prev, cur) => {\n if (prev) {\n const start = graph.getNode(prev),\n end = graph.getNode(cur);\n\n graph.addEdge(start, end);\n }\n return cur;\n });\n });\n\n return graph;\n }\n\n /\n Creates or get a Node.\n \n @param {number[]} coordinates - Coordinates of the node\n * @returns {Node} - The created or stored node\n /\n getNode(coordinates: number[]) {\n const id = Node.buildId(coordinates);\n let node = this.nodes[id];\n if (!node) node = this.nodes[id] = new Node(coordinates);\n\n return node;\n }\n\n /\n Adds an Edge and its symetricall.\n \n Edges are added symetrically, i.e.: we also add its symetric\n \n @param {Node} from - Node which starts the Edge\n * @param {Node} to - Node which ends the Edge\n /\n addEdge(from: Node, to: Node) {\n const edge = new Edge(from, to),\n symetricEdge = edge.getSymetric();\n\n this.edges.push(edge);\n this.edges.push(symetricEdge);\n }\n\n constructor() {\n this.edges = []; //< {Edge[]} dirEdges\n\n // The key is the `id` of the Node (ie: coordinates.join(','))\n this.nodes = {};\n }\n\n /\n Removes Dangle Nodes (nodes with grade 1).\n /\n deleteDangles() {\n Object.keys(this.nodes)\n .map((id) => this.nodes[id])\n .forEach((node) => this._removeIfDangle(node));\n }\n\n /\n Check if node is dangle, if so, remove it.\n \n It calls itself recursively, removing a dangling node might cause another dangling node\n \n @param {Node} node - Node to check if it's a dangle\n /\n _removeIfDangle(node: Node) {\n // As edges are directed and symetrical, we count only innerEdges\n if (node.innerEdges.length <= 1) {\n const outerNodes = node.getOuterEdges().map((e) => e.to);\n this.removeNode(node);\n outerNodes.forEach((n) => this._removeIfDangle(n));\n }\n }\n\n /\n Delete cut-edges (bridge edges).\n \n The graph will be traversed, all the edges will be labeled according the ring\n * in which they are. (The label is a number incremented by 1). Edges with the same\n * label are cut-edges.\n /\n deleteCutEdges() {\n this._computeNextCWEdges();\n this._findLabeledEdgeRings();\n\n // Cut-edges (bridges) are edges where both edges have the same label\n this.edges.forEach((edge) => {\n if (edge.label === edge.symetric!.label) {\n this.removeEdge(edge.symetric!);\n this.removeEdge(edge);\n }\n });\n }\n\n /\n Set the `next` property of each Edge.\n \n The graph will be transversed in a CW form, so, we set the next of the symetrical edge as the previous one.\n * OuterEdges are sorted CCW.\n \n @param {Node} [node] - If no node is passed, the function calls itself for every node in the Graph\n /\n _computeNextCWEdges(node?: Node) {\n if (typeof node === \"undefined\") {\n Object.keys(this.nodes).forEach((id) =>\n this._computeNextCWEdges(this.nodes[id])\n );\n } else {\n node.getOuterEdges().forEach((edge, i) => {\n node.getOuterEdge(\n (i === 0 ? node.getOuterEdges().length : i) - 1\n ).symetric!.next = edge;\n });\n }\n }\n\n /\n Computes the next edge pointers going CCW around the given node, for the given edgering label.\n \n This algorithm has the effect of converting maximal edgerings into minimal edgerings\n \n XXX: method literally transcribed from `geos::operation::polygonize::PolygonizeGraph::computeNextCCWEdges`,\n * could be written in a more javascript way.\n \n @param {Node} node - Node\n * @param {number} label - Ring's label\n /\n _computeNextCCWEdges(node: Node, label: number) {\n const edges = node.getOuterEdges();\n let firstOutDE, prevInDE;\n\n for (let i = edges.length - 1; i >= 0; --i) {\n let de = edges[i],\n sym = de.symetric,\n outDE,\n inDE;\n\n if (de.label === label) outDE = de;\n\n if (sym!.label === label) inDE = sym;\n\n if (!outDE \|\| !inDE)\n // This edge is not in edgering\n continue;\n\n if (inDE) prevInDE = inDE;\n\n if (outDE) {\n if (prevInDE) {\n prevInDE.next = outDE;\n prevInDE = undefined;\n }\n\n if (!firstOutDE) firstOutDE = outDE;\n }\n }\n\n if (prevInDE) prevInDE.next = firstOutDE;\n }\n\n /\n Finds rings and labels edges according to which rings are.\n \n The label is a number which is increased for each ring.\n \n @returns {Edge[]} edges that start rings\n /\n _findLabeledEdgeRings() {\n const edgeRingStarts: Edge[] = [];\n let label = 0;\n this.edges.forEach((edge) => {\n if (edge.label! >= 0) return;\n\n edgeRingStarts.push(edge);\n\n let e = edge;\n do {\n e.label = label;\n e = e.next!;\n } while (!edge.isEqual(e));\n\n label++;\n });\n\n return edgeRingStarts;\n }\n\n /\n Computes the EdgeRings formed by the edges in this graph.\n \n @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.\n /\n getEdgeRings() {\n this._computeNextCWEdges();\n\n // Clear labels\n this.edges.forEach((edge) => {\n edge.label = undefined;\n });\n\n this._findLabeledEdgeRings().forEach((edge) => {\n // convertMaximalToMinimalEdgeRings\n this._findIntersectionNodes(edge).forEach((node) => {\n this._computeNextCCWEdges(node, edge.label!);\n });\n });\n\n const edgeRingList: EdgeRing[] = [];\n\n // find all edgerings\n this.edges.forEach((edge) => {\n if (edge.ring) return;\n edgeRingList.push(this._findEdgeRing(edge));\n });\n\n return edgeRingList;\n }\n\n /\n Find all nodes in a Maxima EdgeRing which are self-intersection nodes.\n \n @param {Node} startEdge - Start Edge of the Ring\n * @returns {Node[]} - intersection nodes\n /\n _findIntersectionNodes(startEdge: Edge) {\n const intersectionNodes = [];\n let edge = startEdge;\n do {\n // getDegree\n let degree = 0;\n edge.from.getOuterEdges().forEach((e) => {\n if (e.label === startEdge.label) ++degree;\n });\n\n if (degree > 1) intersectionNodes.push(edge.from);\n\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return intersectionNodes;\n }\n\n /\n Get the edge-ring which starts from the provided Edge.\n \n @param {Edge} startEdge - starting edge of the edge ring\n * @returns {EdgeRing} - EdgeRing which start Edge is the provided one.\n /\n _findEdgeRing(startEdge: Edge) {\n let edge = startEdge;\n const edgeRing = new EdgeRing();\n\n do {\n edgeRing.push(edge);\n edge.ring = edgeRing;\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return edgeRing;\n }\n\n /\n Removes a node from the Graph.\n \n It also removes edges asociated to that node\n * @param {Node} node - Node to be removed\n /\n removeNode(node: Node) {\n node.getOuterEdges().forEach((edge) => this.removeEdge(edge));\n node.innerEdges.forEach((edge) => this.removeEdge(edge));\n delete this.nodes[node.id];\n }\n\n /\n Remove edge from the graph and deletes the edge.\n \n @param {Edge} edge - Edge to be removed\n */\n removeEdge(edge: Edge) {\n this.edges = this.edges.filter((e) => !e.isEqual(edge));\n edge.deleteEdge();\n }\n}\n\nexport { Graph };\nexport default Graph;\n"],"mappings":";AAOA,SAAS,yBAAyB;;;ACNlC,SAAS,6BAA6B;AACtC,SAAS,aAAa;AAGtB,SAAS,SAAS,GAAW;AAC3B,UAAS,IAAI,MAA6B,IAAI,MAA4B,CAAC;AAC7E;AAgBO,SAAS,iBAAiB,IAAc,IAAc,GAAa;AACxE,QAAM,MAAM,GAAG,CAAC,IAAI,GAAG,CAAC,GACtB,MAAM,GAAG,CAAC,IAAI,GAAG,CAAC,GAClB,MAAM,EAAE,CAAC,IAAI,GAAG,CAAC,GACjB,MAAM,EAAE,CAAC,IAAI,GAAG,CAAC;AAEnB,SAAO,SAAS,MAAM,MAAM,MAAM,GAAG;AACvC;AAWO,SAAS,gBACd,MACA,MACA;AACA,QAAM,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC,GACxD,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC,GACpD,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC,GACpD,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC;AAEtD,SACE,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK,KAC1D,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK,KAC1D,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK,KAC1D,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK;AAE9D;AAaO,SAAS,iBACd,MACA,KACA;AACA,SAAO,IAAI,SAAS,YAAY,CAAC,EAAE;AAAA,IAAM,CAAC,MACxC,sBAAsB,MAAM,CAAC,GAAG,IAAI;AAAA,EACtC;AACF;AASO,SAAS,iBAAiB,QAAkB,QAAkB;AACnE,SAAO,OAAO,CAAC,MAAM,OAAO,CAAC,KAAK,OAAO,CAAC,MAAM,OAAO,CAAC;AAC1D;;;ACjFA,IAAM,OAAN,MAAM,MAAK;AAAA,EACT,OAAO,QAAQ,aAAuB;AACpC,WAAO,YAAY,KAAK,GAAG;AAAA,EAC7B;AAAA,EAQA,YAAY,aAAuB;AACjC,SAAK,KAAK,MAAK,QAAQ,WAAW;AAClC,SAAK,cAAc;AACnB,SAAK,aAAa,CAAC;AAGnB,SAAK,aAAa,CAAC;AACnB,SAAK,mBAAmB;AAAA,EAC1B;AAAA,EAEA,gBAAgB,MAAY;AAC1B,SAAK,aAAa,KAAK,WAAW,OAAO,CAAC,MAAM,EAAE,KAAK,OAAO,KAAK,KAAK,EAAE;AAAA,EAC5E;AAAA,EAEA,gBAAgB,MAAY;AAC1B,SAAK,aAAa,KAAK,WAAW,OAAO,CAAC,MAAM,EAAE,GAAG,OAAO,KAAK,GAAG,EAAE;AAAA,EACxE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,aAAa,MAAY;AACvB,SAAK,WAAW,KAAK,IAAI;AACzB,SAAK,mBAAmB;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,iBAAiB;AACf,QAAI,CAAC,KAAK,kBAAkB;AAG1B,WAAK,WAAW,KAAK,CAAC,GAAG,MAAM;AAC7B,cAAM,QAAQ,EAAE,IACd,QAAQ,EAAE;AAEZ,YACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK,KAC9C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,IAAI;AAE7C,iBAAO;AACT,YACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,IAAI,KAC7C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK;AAE9C,iBAAO;AAET,YACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,MAAM,KAC/C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,MAAM,GAC/C;AACA,cACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK,KAC9C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK;AAE9C,mBAAO,MAAM,YAAY,CAAC,IAAI,MAAM,YAAY,CAAC;AACnD,iBAAO,MAAM,YAAY,CAAC,IAAI,MAAM,YAAY,CAAC;AAAA,QACnD;AAEA,cAAM,MAAM;AAAA,UACV,KAAK;AAAA,UACL,MAAM;AAAA,UACN,MAAM;AAAA,QACR;AACA,YAAI,MAAM,EAAG,QAAO;AACpB,YAAI,MAAM,EAAG,QAAO;AAEpB,cAAM,KACF,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC,IACtD,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC,GACxD,KACE,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC,IACtD,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC;AAE1D,eAAO,KAAK;AAAA,MACd,CAAC;AACD,WAAK,mBAAmB;AAAA,IAC1B;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,gBAAgB;AACd,SAAK,eAAe;AACpB,WAAO,KAAK;AAAA,EACd;AAAA,EAEA,aAAa,GAAW;AACtB,SAAK,eAAe;AACpB,WAAO,KAAK,WAAW,CAAC;AAAA,EAC1B;AAAA,EAEA,aAAa,MAAY;AACvB,SAAK,WAAW,KAAK,IAAI;AAAA,EAC3B;AACF;;;AC7HA,SAAS,kBAAkB;AAQ3B,IAAM,OAAN,MAAM,MAAK;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaT,cAAc;AACZ,QAAI,CAAC,KAAK,UAAU;AAClB,WAAK,WAAW,IAAI,MAAK,KAAK,IAAI,KAAK,IAAI;AAC3C,WAAK,SAAS,WAAW;AAAA,IAC3B;AAEA,WAAO,KAAK;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,YAAY,MAAY,IAAU;AAChC,SAAK,OAAO;AACZ,SAAK,KAAK;AAEV,SAAK,OAAO;AACZ,SAAK,QAAQ;AACb,SAAK,WAAW;AAChB,SAAK,OAAO;AAEZ,SAAK,KAAK,aAAa,IAAI;AAC3B,SAAK,GAAG,aAAa,IAAI;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA,EAKA,aAAa;AACX,SAAK,KAAK,gBAAgB,IAAI;AAC9B,SAAK,GAAG,gBAAgB,IAAI;AAAA,EAC9B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,QAAQ,MAAY;AAClB,WAAO,KAAK,KAAK,OAAO,KAAK,KAAK,MAAM,KAAK,GAAG,OAAO,KAAK,GAAG;AAAA,EACjE;AAAA,EAEA,WAAW;AACT,WAAO,UAAU,KAAK,KAAK,EAAE,OAAO,KAAK,GAAG,EAAE;AAAA,EAChD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,eAAe;AACb,WAAO,WAAW,CAAC,KAAK,KAAK,aAAa,KAAK,GAAG,WAAW,CAAC;AAAA,EAChE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,UAAU,MAAY;AACpB,WAAO;AAAA,MACL,KAAK,KAAK;AAAA,MACV,KAAK,GAAG;AAAA,MACR,KAAK,GAAG;AAAA,IACV;AAAA,EACF;AACF;;;AC1FA,SAAS,YAAY,SAAS,SAAAA,cAAa;AAC3C,SAAS,gBAAgB;AACzB,SAAS,yBAAAC,8BAA6B;AAUtC,IAAM,WAAN,MAAe;AAAA,EAeb,cAAc;AACZ,SAAK,QAAQ,CAAC;AACd,SAAK,UAAU;AACf,SAAK,WAAW;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,KAAK,MAAY;AACf,SAAK,MAAM,KAAK,IAAI;AACpB,SAAK,UAAU,KAAK,WAAW;AAAA,EACjC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAI,GAAW;AACb,WAAO,KAAK,MAAM,CAAC;AAAA,EACrB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,SAAS;AACX,WAAO,KAAK,MAAM;AAAA,EACpB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,QAAQ,GAAuD;AAC7D,SAAK,MAAM,QAAQ,CAAC;AAAA,EACtB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAO,GAAyD;AAC9D,WAAO,KAAK,MAAM,IAAI,CAAC;AAAA,EACzB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,KAAK,GAA0D;AAC7D,WAAO,KAAK,MAAM,KAAK,CAAC;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,UAAU;AAER,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,SAAS;AAGP,UAAM,UAAU,KAAK,MAAM,OAAO,CAAC,MAAM,MAAM,MAAM;AACjD,UAAI,KAAK,KAAK,YAAY,CAAC,IAAI,KAAK,MAAM,IAAI,EAAE,KAAK,YAAY,CAAC;AAChE,eAAO;AACT,aAAO;AAAA,IACT,GAAG,CAAC,GACJ,SAAS,YAAY,IAAI,KAAK,SAAS,WAAW,GAClD,SAAS,UAAU,KAAK,KAAK,QAC7B,OAAO;AAAA,MACL,KAAK,MAAM,KAAK,EAAE,KAAK;AAAA,MACvB,KAAK,MAAM,OAAO,EAAE,KAAK;AAAA,MACzB,KAAK,MAAM,KAAK,EAAE,KAAK;AAAA,IACzB;AAEF,QAAI,SAAS;AACX,aACE,KAAK,MAAM,KAAK,EAAE,KAAK,YAAY,CAAC,IACpC,KAAK,MAAM,KAAK,EAAE,KAAK,YAAY,CAAC;AAExC,WAAO,OAAO;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,eAAe;AACb,WAAO,WAAW,KAAK,MAAM,IAAI,CAAC,SAAS,KAAK,KAAK,WAAW,CAAC;AAAA,EACnE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,YAAY;AACV,QAAI,KAAK,QAAS,QAAO,KAAK;AAC9B,UAAM,cAAc,KAAK,MAAM,IAAI,CAAC,SAAS,KAAK,KAAK,WAAW;AAClE,gBAAY,KAAK,KAAK,MAAM,CAAC,EAAE,KAAK,WAAW;AAC/C,WAAQ,KAAK,UAAU,QAAQ,CAAC,WAAW,CAAC;AAAA,EAC9C;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,cAAc;AACZ,QAAI,KAAK,SAAU,QAAO,KAAK;AAC/B,WAAQ,KAAK,WAAW,SAAS,KAAK,UAAU,CAAC;AAAA,EAInD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAO,uBACL,cACA,WACsB;AACtB,UAAM,eAAe,aAAa,YAAY;AAE9C,QAAI,aAA+B;AACnC,cAAU,QAAQ,CAAC,UAAU;AAC3B,YAAM,cAAc,MAAM,YAAY;AAEtC,UAAI,SAAU,eAAc,SAAS,YAAY;AAGjD,UAAI,gBAAgB,aAAa,YAAY,EAAG;AAEhD,UAAI,iBAAiB,aAAa,YAAY,GAAG;AAC/C,cAAM,0BAA0B,aAAa;AAAA,UAC3C,CAAC,SAAS,KAAK,KAAK;AAAA,QACtB;AAEA,YAAI;AACJ,mBAAW,MAAM,yBAAyB;AACxC,cACE,CAAC,MAAM,KAAK,CAAC,SAAS,iBAAiB,IAAI,KAAK,KAAK,WAAW,CAAC,GACjE;AACA,wBAAY;AAAA,UACd;AAAA,QACF;AAEA,YAAI,aAAa,MAAM,OAAOD,OAAM,SAAS,CAAC,GAAG;AAC/C,cAAI,CAAC,YAAY,iBAAiB,aAAa,WAAW;AACxD,uBAAW;AAAA,QACf;AAAA,MACF;AAAA,IACF,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAO,IAAoB;AACzB,WAAOC,uBAAsB,IAAI,KAAK,UAAU,CAAC;AAAA,EACnD;AACF;;;AClPA,SAAS,aAAa,mBAAmB;AACzC,SAAS,iBAAiB;AAe1B,SAAS,gBAAgB,SAAqB;AAC5C,MAAI,CAAC,QAAS,OAAM,IAAI,MAAM,mBAAmB;AAEjD,MACE,QAAQ,SAAS,uBACjB,QAAQ,SAAS,wBACjB,QAAQ,SAAS,qBACjB,QAAQ,SAAS,gBACjB,QAAQ,SAAS;AAEjB,UAAM,IAAI;AAAA,MACR,uBAAuB,QAAQ,IAAI;AAAA,IACrC;AACJ;AAWA,IAAM,QAAN,MAAM,OAAM;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWV,OAAO,YACL,SAKA;AACA,oBAAgB,OAAO;AAEvB,UAAM,QAAQ,IAAI,OAAM;AACxB,gBAAY,SAAS,CAAC,YAAY;AAChC,gBAAU,SAAS,cAAc,oBAAoB;AAErD,kBAAsB,SAAS,CAAC,MAAM,QAAQ;AAC5C,YAAI,MAAM;AACR,gBAAM,QAAQ,MAAM,QAAQ,IAAI,GAC9B,MAAM,MAAM,QAAQ,GAAG;AAEzB,gBAAM,QAAQ,OAAO,GAAG;AAAA,QAC1B;AACA,eAAO;AAAA,MACT,CAAC;AAAA,IACH,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,QAAQ,aAAuB;AAC7B,UAAM,KAAK,KAAK,QAAQ,WAAW;AACnC,QAAI,OAAO,KAAK,MAAM,EAAE;AACxB,QAAI,CAAC,KAAM,QAAO,KAAK,MAAM,EAAE,IAAI,IAAI,KAAK,WAAW;AAEvD,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,QAAQ,MAAY,IAAU;AAC5B,UAAM,OAAO,IAAI,KAAK,MAAM,EAAE,GAC5B,eAAe,KAAK,YAAY;AAElC,SAAK,MAAM,KAAK,IAAI;AACpB,SAAK,MAAM,KAAK,YAAY;AAAA,EAC9B;AAAA,EAEA,cAAc;AACZ,SAAK,QAAQ,CAAC;AAGd,SAAK,QAAQ,CAAC;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA,EAKA,gBAAgB;AACd,WAAO,KAAK,KAAK,KAAK,EACnB,IAAI,CAAC,OAAO,KAAK,MAAM,EAAE,CAAC,EAC1B,QAAQ,CAAC,SAAS,KAAK,gBAAgB,IAAI,CAAC;AAAA,EACjD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,gBAAgB,MAAY;AAE1B,QAAI,KAAK,WAAW,UAAU,GAAG;AAC/B,YAAM,aAAa,KAAK,cAAc,EAAE,IAAI,CAAC,MAAM,EAAE,EAAE;AACvD,WAAK,WAAW,IAAI;AACpB,iBAAW,QAAQ,CAAC,MAAM,KAAK,gBAAgB,CAAC,CAAC;AAAA,IACnD;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,iBAAiB;AACf,SAAK,oBAAoB;AACzB,SAAK,sBAAsB;AAG3B,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,UAAI,KAAK,UAAU,KAAK,SAAU,OAAO;AACvC,aAAK,WAAW,KAAK,QAAS;AAC9B,aAAK,WAAW,IAAI;AAAA,MACtB;AAAA,IACF,CAAC;AAAA,EACH;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,oBAAoB,MAAa;AAC/B,QAAI,OAAO,SAAS,aAAa;AAC/B,aAAO,KAAK,KAAK,KAAK,EAAE;AAAA,QAAQ,CAAC,OAC/B,KAAK,oBAAoB,KAAK,MAAM,EAAE,CAAC;AAAA,MACzC;AAAA,IACF,OAAO;AACL,WAAK,cAAc,EAAE,QAAQ,CAAC,MAAM,MAAM;AACxC,aAAK;AAAA,WACF,MAAM,IAAI,KAAK,cAAc,EAAE,SAAS,KAAK;AAAA,QAChD,EAAE,SAAU,OAAO;AAAA,MACrB,CAAC;AAAA,IACH;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,qBAAqB,MAAY,OAAe;AAC9C,UAAM,QAAQ,KAAK,cAAc;AACjC,QAAI,YAAY;AAEhB,aAAS,IAAI,MAAM,SAAS,GAAG,KAAK,GAAG,EAAE,GAAG;AAC1C,UAAI,KAAK,MAAM,CAAC,GACd,MAAM,GAAG,UACT,OACA;AAEF,UAAI,GAAG,UAAU,MAAO,SAAQ;AAEhC,UAAI,IAAK,UAAU,MAAO,QAAO;AAEjC,UAAI,CAAC,SAAS,CAAC;AAEb;AAEF,UAAI,KAAM,YAAW;AAErB,UAAI,OAAO;AACT,YAAI,UAAU;AACZ,mBAAS,OAAO;AAChB,qBAAW;AAAA,QACb;AAEA,YAAI,CAAC,WAAY,cAAa;AAAA,MAChC;AAAA,IACF;AAEA,QAAI,SAAU,UAAS,OAAO;AAAA,EAChC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,wBAAwB;AACtB,UAAM,iBAAyB,CAAC;AAChC,QAAI,QAAQ;AACZ,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,UAAI,KAAK,SAAU,EAAG;AAEtB,qBAAe,KAAK,IAAI;AAExB,UAAI,IAAI;AACR,SAAG;AACD,UAAE,QAAQ;AACV,YAAI,EAAE;AAAA,MACR,SAAS,CAAC,KAAK,QAAQ,CAAC;AAExB;AAAA,IACF,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,eAAe;AACb,SAAK,oBAAoB;AAGzB,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,WAAK,QAAQ;AAAA,IACf,CAAC;AAED,SAAK,sBAAsB,EAAE,QAAQ,CAAC,SAAS;AAE7C,WAAK,uBAAuB,IAAI,EAAE,QAAQ,CAAC,SAAS;AAClD,aAAK,qBAAqB,MAAM,KAAK,KAAM;AAAA,MAC7C,CAAC;AAAA,IACH,CAAC;AAED,UAAM,eAA2B,CAAC;AAGlC,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,UAAI,KAAK,KAAM;AACf,mBAAa,KAAK,KAAK,cAAc,IAAI,CAAC;AAAA,IAC5C,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,uBAAuB,WAAiB;AACtC,UAAM,oBAAoB,CAAC;AAC3B,QAAI,OAAO;AACX,OAAG;AAED,UAAI,SAAS;AACb,WAAK,KAAK,cAAc,EAAE,QAAQ,CAAC,MAAM;AACvC,YAAI,EAAE,UAAU,UAAU,MAAO,GAAE;AAAA,MACrC,CAAC;AAED,UAAI,SAAS,EAAG,mBAAkB,KAAK,KAAK,IAAI;AAEhD,aAAO,KAAK;AAAA,IACd,SAAS,CAAC,UAAU,QAAQ,IAAI;AAEhC,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,cAAc,WAAiB;AAC7B,QAAI,OAAO;AACX,UAAM,WAAW,IAAI,SAAS;AAE9B,OAAG;AACD,eAAS,KAAK,IAAI;AAClB,WAAK,OAAO;AACZ,aAAO,KAAK;AAAA,IACd,SAAS,CAAC,UAAU,QAAQ,IAAI;AAEhC,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,WAAW,MAAY;AACrB,SAAK,cAAc,EAAE,QAAQ,CAAC,SAAS,KAAK,WAAW,IAAI,CAAC;AAC5D,SAAK,WAAW,QAAQ,CAAC,SAAS,KAAK,WAAW,IAAI,CAAC;AACvD,WAAO,KAAK,MAAM,KAAK,EAAE;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,WAAW,MAAY;AACrB,SAAK,QAAQ,KAAK,MAAM,OAAO,CAAC,MAAM,CAAC,EAAE,QAAQ,IAAI,CAAC;AACtD,SAAK,WAAW;AAAA,EAClB;AACF;;;ALlUA,SAAS,WACP,SAC4B;AAC5B,QAAM,QAAQ,MAAM,YAAY,OAAO;AAGvC,QAAM,cAAc;AAGpB,QAAM,eAAe;AAGrB,QAAM,QAAoB,CAAC,GACzB,SAAqB,CAAC;AAExB,QACG,aAAa,EACb,OAAO,CAAC,aAAa,SAAS,QAAQ,CAAC,EACvC,QAAQ,CAAC,aAAa;AACrB,QAAI,SAAS,OAAO,EAAG,OAAM,KAAK,QAAQ;AAAA,QACrC,QAAO,KAAK,QAAQ;AAAA,EAC3B,CAAC;AAGH,QAAM,QAAQ,CAAC,SAAS;AACtB,QAAI,SAAS,uBAAuB,MAAM,MAAM,EAAG,QAAO,KAAK,IAAI;AAAA,EACrE,CAAC;AAGD,SAAO,kBAAkB,OAAO,IAAI,CAAC,UAAU,MAAM,UAAU,CAAC,CAAC;AACnE;AAGA,IAAO,0BAAQ;","names":["point","booleanPointInPolygon"]}
		{"version":3,"sources":["../../index.ts","../../lib/util.ts","../../lib/Node.ts","../../lib/Edge.ts","../../lib/EdgeRing.ts","../../lib/Graph.ts"],"sourcesContent":["import {\n Feature,\n FeatureCollection,\n LineString,\n MultiLineString,\n Polygon,\n} from \"geojson\";\nimport { featureCollection } from \"@turf/helpers\";\nimport { Graph } from \"./lib/Graph.js\";\nimport { EdgeRing } from \"./lib/EdgeRing.js\";\n\n/*\n Polygonizes {@link LineString\|(Multi)LineString(s)} into {@link Polygons}.\n \n Implementation of GEOSPolygonize function (`geos::operation::polygonize::Polygonizer`).\n \n Polygonizes a set of lines that represents edges in a planar graph. Edges must be correctly\n * noded, i.e., they must only meet at their endpoints.\n \n The implementation correctly handles:\n \n - Dangles: edges which have one or both ends which are not incident on another edge endpoint.\n * - Cut Edges (bridges): edges that are connected at both ends but which do not form part of a polygon.\n \n @function\n * @param {FeatureCollection\|Geometry\|Feature<LineString\|MultiLineString>} geoJson Lines in order to polygonize\n * @returns {FeatureCollection<Polygon>} Polygons created\n * @throws {Error} if geoJson is invalid.\n /\nfunction polygonize<T extends LineString \| MultiLineString>(\n geoJson: Feature<T> \| FeatureCollection<T> \| T\n): FeatureCollection<Polygon> {\n const graph = Graph.fromGeoJson(geoJson);\n\n // 1. Remove dangle node\n graph.deleteDangles();\n\n // 2. Remove cut-edges (bridge edges)\n graph.deleteCutEdges();\n\n // 3. Get all holes and shells\n const holes: EdgeRing[] = [],\n shells: EdgeRing[] = [];\n\n graph\n .getEdgeRings()\n .filter((edgeRing) => edgeRing.isValid())\n .forEach((edgeRing) => {\n if (edgeRing.isHole()) holes.push(edgeRing);\n else shells.push(edgeRing);\n });\n\n // 4. Assign Holes to Shells\n holes.forEach((hole) => {\n if (EdgeRing.findEdgeRingContaining(hole, shells)) shells.push(hole);\n });\n\n // 5. EdgeRings to Polygons\n return featureCollection(shells.map((shell) => shell.toPolygon()));\n}\n\nexport { polygonize };\nexport default polygonize;\n","import { Feature, Polygon } from \"geojson\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { point } from \"@turf/helpers\";\n\n// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/sign#Polyfill\nfunction mathSign(x: number) {\n return ((x > 0) as unknown as number) - ((x < 0) as unknown as number) \|\| +x;\n}\n\n/\n Returns the direction of the point q relative to the vector p1 -> p2.\n \n Implementation of geos::algorithm::CGAlgorithm::orientationIndex()\n * (same as geos::algorithm::CGAlgorithm::computeOrientation())\n \n @param {number[]} p1 - the origin point of the vector\n * @param {number[]} p2 - the final point of the vector\n * @param {number[]} q - the point to compute the direction to\n \n @returns {number} - 1 if q is ccw (left) from p1->p2,\n * -1 if q is cw (right) from p1->p2,\n * 0 if q is colinear with p1->p2\n /\nexport function orientationIndex(p1: number[], p2: number[], q: number[]) {\n const dx1 = p2[0] - p1[0],\n dy1 = p2[1] - p1[1],\n dx2 = q[0] - p2[0],\n dy2 = q[1] - p2[1];\n\n return mathSign(dx1 dy2 - dx2 * dy1);\n}\n\n/*\n Checks if two envelopes are equal.\n \n The function assumes that the arguments are envelopes, i.e.: Rectangular polygon\n \n @param {Feature<Polygon>} env1 - Envelope\n * @param {Feature<Polygon>} env2 - Envelope\n * @returns {boolean} - True if the envelopes are equal\n /\nexport function envelopeIsEqual(\n env1: Feature<Polygon>,\n env2: Feature<Polygon>\n) {\n const envX1 = env1.geometry.coordinates[0].map((c) => c[0]),\n envY1 = env1.geometry.coordinates[0].map((c) => c[1]),\n envX2 = env2.geometry.coordinates[0].map((c) => c[0]),\n envY2 = env2.geometry.coordinates[0].map((c) => c[1]);\n\n return (\n Math.max.apply(null, envX1) === Math.max.apply(null, envX2) &&\n Math.max.apply(null, envY1) === Math.max.apply(null, envY2) &&\n Math.min.apply(null, envX1) === Math.min.apply(null, envX2) &&\n Math.min.apply(null, envY1) === Math.min.apply(null, envY2)\n );\n}\n\n/\n Check if a envelope is contained in other one.\n \n The function assumes that the arguments are envelopes, i.e.: Convex polygon\n * XXX: Envelopes are rectangular, checking if a point is inside a rectangule is something easy,\n * this could be further improved.\n \n @param {Feature<Polygon>} self - Envelope\n * @param {Feature<Polygon>} env - Envelope\n * @returns {boolean} - True if env is contained in self\n /\nexport function envelopeContains(\n self: Feature<Polygon>,\n env: Feature<Polygon>\n) {\n return env.geometry.coordinates[0].every((c) =>\n booleanPointInPolygon(point(c), self)\n );\n}\n\n/\n Checks if two coordinates are equal.\n \n @param {number[]} coord1 - First coordinate\n * @param {number[]} coord2 - Second coordinate\n * @returns {boolean} - True if coordinates are equal\n /\nexport function coordinatesEqual(coord1: number[], coord2: number[]) {\n return coord1[0] === coord2[0] && coord1[1] === coord2[1];\n}\n","import { orientationIndex } from \"./util.js\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Node\n /\nclass Node {\n static buildId(coordinates: number[]) {\n return coordinates.join(\",\");\n }\n\n public id: string;\n public coordinates: number[];\n public innerEdges: Edge[];\n private outerEdges: Edge[];\n private outerEdgesSorted: boolean;\n\n constructor(coordinates: number[]) {\n this.id = Node.buildId(coordinates);\n this.coordinates = coordinates; //< {Number[]}\n this.innerEdges = []; //< {Edge[]}\n\n // We wil store to (out) edges in an CCW order as geos::planargraph::DirectedEdgeStar does\n this.outerEdges = []; //< {Edge[]}\n this.outerEdgesSorted = false; //< {Boolean} flag that stores if the outer Edges had been sorted\n }\n\n removeInnerEdge(edge: Edge) {\n this.innerEdges = this.innerEdges.filter((e) => e.from.id !== edge.from.id);\n }\n\n removeOuterEdge(edge: Edge) {\n this.outerEdges = this.outerEdges.filter((e) => e.to.id !== edge.to.id);\n }\n\n /\n Outer edges are stored CCW order.\n \n @memberof Node\n * @param {Edge} edge - Edge to add as an outerEdge.\n /\n addOuterEdge(edge: Edge) {\n this.outerEdges.push(edge);\n this.outerEdgesSorted = false;\n }\n\n /\n Sorts outer edges in CCW way.\n \n @memberof Node\n * @private\n /\n sortOuterEdges() {\n if (!this.outerEdgesSorted) {\n //this.outerEdges.sort((a, b) => a.compareTo(b));\n // Using this comparator in order to be deterministic\n this.outerEdges.sort((a, b) => {\n const aNode = a.to,\n bNode = b.to;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] >= 0 &&\n bNode.coordinates[0] - this.coordinates[0] < 0\n )\n return 1;\n if (\n aNode.coordinates[0] - this.coordinates[0] < 0 &&\n bNode.coordinates[0] - this.coordinates[0] >= 0\n )\n return -1;\n\n if (\n aNode.coordinates[0] - this.coordinates[0] === 0 &&\n bNode.coordinates[0] - this.coordinates[0] === 0\n ) {\n if (\n aNode.coordinates[1] - this.coordinates[1] >= 0 \|\|\n bNode.coordinates[1] - this.coordinates[1] >= 0\n )\n return aNode.coordinates[1] - bNode.coordinates[1];\n return bNode.coordinates[1] - aNode.coordinates[1];\n }\n\n const det = orientationIndex(\n this.coordinates,\n aNode.coordinates,\n bNode.coordinates\n );\n if (det < 0) return 1;\n if (det > 0) return -1;\n\n const d1 =\n Math.pow(aNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(aNode.coordinates[1] - this.coordinates[1], 2),\n d2 =\n Math.pow(bNode.coordinates[0] - this.coordinates[0], 2) +\n Math.pow(bNode.coordinates[1] - this.coordinates[1], 2);\n\n return d1 - d2;\n });\n this.outerEdgesSorted = true;\n }\n }\n\n /\n Retrieves outer edges.\n \n They are sorted if they aren't in the CCW order.\n \n @memberof Node\n * @returns {Edge[]} - List of outer edges sorted in a CCW order.\n /\n getOuterEdges() {\n this.sortOuterEdges();\n return this.outerEdges;\n }\n\n getOuterEdge(i: number) {\n this.sortOuterEdges();\n return this.outerEdges[i];\n }\n\n addInnerEdge(edge: Edge) {\n this.innerEdges.push(edge);\n }\n}\n\nexport { Node };\nexport default Node;\n","import { lineString } from \"@turf/helpers\";\nimport { orientationIndex } from \"./util.js\";\nimport { Node } from \"./Node.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\n\n/\n This class is inspired by GEOS's geos::operation::polygonize::PolygonizeDirectedEdge\n /\nclass Edge {\n public label?: number;\n public symetric?: Edge;\n public from: Node;\n public to: Node;\n public next?: Edge;\n public ring?: EdgeRing;\n\n /\n Creates or get the symetric Edge.\n \n @returns {Edge} - Symetric Edge.\n /\n getSymetric() {\n if (!this.symetric) {\n this.symetric = new Edge(this.to, this.from);\n this.symetric.symetric = this;\n }\n\n return this.symetric;\n }\n\n /\n @param {Node} from - start node of the Edge\n * @param {Node} to - end node of the edge\n /\n constructor(from: Node, to: Node) {\n this.from = from; //< start\n this.to = to; //< End\n\n this.next = undefined; //< The edge to be computed after\n this.label = undefined; //< Used in order to detect Cut Edges (Bridges)\n this.symetric = undefined; //< The symetric edge of this\n this.ring = undefined; //< EdgeRing in which the Edge is\n\n this.from.addOuterEdge(this);\n this.to.addInnerEdge(this);\n }\n\n /\n Removes edge from from and to nodes.\n /\n deleteEdge() {\n this.from.removeOuterEdge(this);\n this.to.removeInnerEdge(this);\n }\n\n /\n Compares Edge equallity.\n \n An edge is equal to another, if the from and to nodes are the same.\n \n @param {Edge} edge - Another Edge\n * @returns {boolean} - True if Edges are equal, False otherwise\n /\n isEqual(edge: Edge) {\n return this.from.id === edge.from.id && this.to.id === edge.to.id;\n }\n\n toString() {\n return `Edge { ${this.from.id} -> ${this.to.id} }`;\n }\n\n /\n Returns a LineString representation of the Edge\n \n @returns {Feature<LineString>} - LineString representation of the Edge\n /\n toLineString() {\n return lineString([this.from.coordinates, this.to.coordinates]);\n }\n\n /\n Comparator of two edges.\n \n Implementation of geos::planargraph::DirectedEdge::compareTo.\n \n @param {Edge} edge - Another edge to compare with this one\n * @returns {number} -1 if this Edge has a greater angle with the positive x-axis than b,\n * 0 if the Edges are colinear,\n * 1 otherwise\n /\n compareTo(edge: Edge) {\n return orientationIndex(\n edge.from.coordinates,\n edge.to.coordinates,\n this.to.coordinates\n );\n }\n}\n\nexport { Edge };\nexport default Edge;\n","import { Polygon, Feature, Point, Position } from \"geojson\";\nimport {\n orientationIndex,\n envelopeIsEqual,\n envelopeContains,\n coordinatesEqual,\n} from \"./util.js\";\nimport { multiPoint, polygon, point } from \"@turf/helpers\";\nimport { envelope } from \"@turf/envelope\";\nimport { booleanPointInPolygon } from \"@turf/boolean-point-in-polygon\";\nimport { Edge } from \"./Edge.js\";\n\n/\n Ring of edges which form a polygon.\n \n The ring may be either an outer shell or a hole.\n \n This class is inspired in GEOS's geos::operation::polygonize::EdgeRing\n /\nclass EdgeRing {\n private edges: Edge[];\n private polygon?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n private envelope?: Feature<\n Polygon,\n {\n [name: string]: any;\n }\n >;\n\n constructor() {\n this.edges = [];\n this.polygon = undefined; //< Caches Polygon representation\n this.envelope = undefined; //< Caches Envelope representation\n }\n\n /\n Add an edge to the ring, inserting it in the last position.\n \n @memberof EdgeRing\n * @param {Edge} edge - Edge to be inserted\n /\n push(edge: Edge) {\n this.edges.push(edge);\n this.polygon = this.envelope = undefined;\n }\n\n /\n Get Edge.\n \n @memberof EdgeRing\n * @param {number} i - Index\n * @returns {Edge} - Edge in the i position\n /\n get(i: number) {\n return this.edges[i];\n }\n\n /\n Getter of length property.\n \n @memberof EdgeRing\n * @returns {number} - Length of the edge ring.\n /\n get length() {\n return this.edges.length;\n }\n\n /\n Similar to Array.prototype.forEach for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.forEach\n /\n forEach(f: (edge: Edge, index: number, array: Edge[]) => void) {\n this.edges.forEach(f);\n }\n\n /\n Similar to Array.prototype.map for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.map\n * @returns {Array} - The mapped values in the function\n /\n map<T>(f: (edge: Edge, index: number, array: Edge[]) => T): T[] {\n return this.edges.map(f);\n }\n\n /\n Similar to Array.prototype.some for the list of Edges in the EdgeRing.\n \n @memberof EdgeRing\n * @param {Function} f - The same function to be passed to Array.prototype.some\n * @returns {boolean} - True if an Edge check the condition\n /\n some(f: (edge: Edge, index: number, array: Edge[]) => boolean) {\n return this.edges.some(f);\n }\n\n /\n Check if the ring is valid in geomtry terms.\n \n A ring must have either 0 or 4 or more points. The first and the last must be\n * equal (in 2D)\n * geos::geom::LinearRing::validateConstruction\n \n @memberof EdgeRing\n * @returns {boolean} - Validity of the EdgeRing\n /\n isValid() {\n // TODO: stub\n return true;\n }\n\n /\n Tests whether this ring is a hole.\n \n A ring is a hole if it is oriented counter-clockwise.\n * Similar implementation of geos::algorithm::CGAlgorithms::isCCW\n \n @memberof EdgeRing\n * @returns {boolean} - true: if it is a hole\n /\n isHole() {\n // XXX: Assuming Ring is valid\n // Find highest point\n const hiIndex = this.edges.reduce((high, edge, i) => {\n if (edge.from.coordinates[1] > this.edges[high].from.coordinates[1])\n high = i;\n return high;\n }, 0),\n iPrev = (hiIndex === 0 ? this.length : hiIndex) - 1,\n iNext = (hiIndex + 1) % this.length,\n disc = orientationIndex(\n this.edges[iPrev].from.coordinates,\n this.edges[hiIndex].from.coordinates,\n this.edges[iNext].from.coordinates\n );\n\n if (disc === 0)\n return (\n this.edges[iPrev].from.coordinates[0] >\n this.edges[iNext].from.coordinates[0]\n );\n return disc > 0;\n }\n\n /\n Creates a MultiPoint representing the EdgeRing (discarts edges directions).\n \n @memberof EdgeRing\n * @returns {Feature<MultiPoint>} - Multipoint representation of the EdgeRing\n /\n toMultiPoint() {\n return multiPoint(this.edges.map((edge) => edge.from.coordinates));\n }\n\n /\n Creates a Polygon representing the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - Polygon representation of the Edge Ring\n /\n toPolygon() {\n if (this.polygon) return this.polygon;\n const coordinates = this.edges.map((edge) => edge.from.coordinates);\n coordinates.push(this.edges[0].from.coordinates);\n return (this.polygon = polygon([coordinates]));\n }\n\n /\n Calculates the envelope of the EdgeRing.\n \n @memberof EdgeRing\n * @returns {Feature<Polygon>} - envelope\n /\n getEnvelope() {\n if (this.envelope) return this.envelope;\n return (this.envelope = envelope(this.toPolygon()) as Feature<\n Polygon,\n { [name: string]: any }\n >);\n }\n\n /\n `geos::operation::polygonize::EdgeRing::findEdgeRingContaining`\n \n @param {EdgeRing} testEdgeRing - EdgeRing to look in the list\n * @param {EdgeRing[]} shellList - List of EdgeRing in which to search\n \n @returns {EdgeRing} - EdgeRing which contains the testEdgeRing\n /\n static findEdgeRingContaining(\n testEdgeRing: EdgeRing,\n shellList: EdgeRing[]\n ): EdgeRing \| undefined {\n const testEnvelope = testEdgeRing.getEnvelope();\n\n let minEnvelope: Feature<Polygon>, minShell: EdgeRing \| undefined;\n shellList.forEach((shell) => {\n const tryEnvelope = shell.getEnvelope();\n\n if (minShell) minEnvelope = minShell.getEnvelope();\n\n // the hole envelope cannot equal the shell envelope\n if (envelopeIsEqual(tryEnvelope, testEnvelope)) return;\n\n if (envelopeContains(tryEnvelope, testEnvelope)) {\n const testEdgeRingCoordinates = testEdgeRing.map(\n (edge) => edge.from.coordinates\n );\n\n let testPoint: Position \| undefined;\n for (const pt of testEdgeRingCoordinates) {\n if (\n !shell.some((edge) => coordinatesEqual(pt, edge.from.coordinates))\n ) {\n testPoint = pt;\n }\n }\n\n if (testPoint && shell.inside(point(testPoint))) {\n if (!minShell \|\| envelopeContains(minEnvelope, tryEnvelope))\n minShell = shell;\n }\n }\n });\n\n return minShell;\n }\n\n /\n Checks if the point is inside the edgeRing\n \n @param {Feature<Point>} pt - Point to check if it is inside the edgeRing\n * @returns {boolean} - True if it is inside, False otherwise\n /\n inside(pt: Feature<Point>) {\n return booleanPointInPolygon(pt, this.toPolygon());\n }\n}\n\nexport { EdgeRing };\nexport default EdgeRing;\n","import { Node } from \"./Node.js\";\nimport { Edge } from \"./Edge.js\";\nimport { EdgeRing } from \"./EdgeRing.js\";\nimport { flattenEach, coordReduce } from \"@turf/meta\";\nimport { featureOf } from \"@turf/invariant\";\nimport {\n FeatureCollection,\n LineString,\n MultiLineString,\n Feature,\n} from \"geojson\";\nimport { AllGeoJSON } from \"@turf/helpers\";\n\n/\n Validates the geoJson.\n \n @param {GeoJSON} geoJson - input geoJson.\n * @throws {Error} if geoJson is invalid.\n /\nfunction validateGeoJson(geoJson: AllGeoJSON) {\n if (!geoJson) throw new Error(\"No geojson passed\");\n\n if (\n geoJson.type !== \"FeatureCollection\" &&\n geoJson.type !== \"GeometryCollection\" &&\n geoJson.type !== \"MultiLineString\" &&\n geoJson.type !== \"LineString\" &&\n geoJson.type !== \"Feature\"\n )\n throw new Error(\n `Invalid input type '${geoJson.type}'. Geojson must be FeatureCollection, GeometryCollection, LineString, MultiLineString or Feature`\n );\n}\n\n/\n Represents a planar graph of edges and nodes that can be used to compute a polygonization.\n \n Although, this class is inspired by GEOS's `geos::operation::polygonize::PolygonizeGraph`,\n * it isn't a rewrite. As regards algorithm, this class implements the same logic, but it\n * isn't a javascript transcription of the C++ source.\n \n This graph is directed (both directions are created)\n /\nclass Graph {\n private nodes: { [id: string]: Node };\n private edges: Edge[];\n\n /\n Creates a graph from a GeoJSON.\n \n @param {FeatureCollection<LineString>} geoJson - it must comply with the restrictions detailed in the index\n * @returns {Graph} - The newly created graph\n * @throws {Error} if geoJson is invalid.\n /\n static fromGeoJson(\n geoJson:\n \| FeatureCollection<LineString \| MultiLineString>\n \| LineString\n \| MultiLineString\n \| Feature<LineString \| MultiLineString>\n ) {\n validateGeoJson(geoJson);\n\n const graph = new Graph();\n flattenEach(geoJson, (feature) => {\n featureOf(feature, \"LineString\", \"Graph::fromGeoJson\");\n // When a LineString if formed by many segments, split them\n coordReduce<number[]>(feature, (prev, cur) => {\n if (prev) {\n const start = graph.getNode(prev),\n end = graph.getNode(cur);\n\n graph.addEdge(start, end);\n }\n return cur;\n });\n });\n\n return graph;\n }\n\n /\n Creates or get a Node.\n \n @param {number[]} coordinates - Coordinates of the node\n * @returns {Node} - The created or stored node\n /\n getNode(coordinates: number[]) {\n const id = Node.buildId(coordinates);\n let node = this.nodes[id];\n if (!node) node = this.nodes[id] = new Node(coordinates);\n\n return node;\n }\n\n /\n Adds an Edge and its symetricall.\n \n Edges are added symetrically, i.e.: we also add its symetric\n \n @param {Node} from - Node which starts the Edge\n * @param {Node} to - Node which ends the Edge\n /\n addEdge(from: Node, to: Node) {\n const edge = new Edge(from, to),\n symetricEdge = edge.getSymetric();\n\n this.edges.push(edge);\n this.edges.push(symetricEdge);\n }\n\n constructor() {\n this.edges = []; //< {Edge[]} dirEdges\n\n // The key is the `id` of the Node (ie: coordinates.join(','))\n this.nodes = {};\n }\n\n /\n Removes Dangle Nodes (nodes with grade 1).\n /\n deleteDangles() {\n Object.keys(this.nodes)\n .map((id) => this.nodes[id])\n .forEach((node) => this._removeIfDangle(node));\n }\n\n /\n Check if node is dangle, if so, remove it.\n \n It calls itself recursively, removing a dangling node might cause another dangling node\n \n @param {Node} node - Node to check if it's a dangle\n /\n _removeIfDangle(node: Node) {\n // As edges are directed and symetrical, we count only innerEdges\n if (node.innerEdges.length <= 1) {\n const outerNodes = node.getOuterEdges().map((e) => e.to);\n this.removeNode(node);\n outerNodes.forEach((n) => this._removeIfDangle(n));\n }\n }\n\n /\n Delete cut-edges (bridge edges).\n \n The graph will be traversed, all the edges will be labeled according the ring\n * in which they are. (The label is a number incremented by 1). Edges with the same\n * label are cut-edges.\n /\n deleteCutEdges() {\n this._computeNextCWEdges();\n this._findLabeledEdgeRings();\n\n // Cut-edges (bridges) are edges where both edges have the same label\n this.edges.forEach((edge) => {\n if (edge.label === edge.symetric!.label) {\n this.removeEdge(edge.symetric!);\n this.removeEdge(edge);\n }\n });\n }\n\n /\n Set the `next` property of each Edge.\n \n The graph will be transversed in a CW form, so, we set the next of the symetrical edge as the previous one.\n * OuterEdges are sorted CCW.\n \n @param {Node} [node] - If no node is passed, the function calls itself for every node in the Graph\n /\n _computeNextCWEdges(node?: Node) {\n if (typeof node === \"undefined\") {\n Object.keys(this.nodes).forEach((id) =>\n this._computeNextCWEdges(this.nodes[id])\n );\n } else {\n node.getOuterEdges().forEach((edge, i) => {\n node.getOuterEdge(\n (i === 0 ? node.getOuterEdges().length : i) - 1\n ).symetric!.next = edge;\n });\n }\n }\n\n /\n Computes the next edge pointers going CCW around the given node, for the given edgering label.\n \n This algorithm has the effect of converting maximal edgerings into minimal edgerings\n \n XXX: method literally transcribed from `geos::operation::polygonize::PolygonizeGraph::computeNextCCWEdges`,\n * could be written in a more javascript way.\n \n @param {Node} node - Node\n * @param {number} label - Ring's label\n /\n _computeNextCCWEdges(node: Node, label: number) {\n const edges = node.getOuterEdges();\n let firstOutDE, prevInDE;\n\n for (let i = edges.length - 1; i >= 0; --i) {\n let de = edges[i],\n sym = de.symetric,\n outDE,\n inDE;\n\n if (de.label === label) outDE = de;\n\n if (sym!.label === label) inDE = sym;\n\n if (!outDE \|\| !inDE)\n // This edge is not in edgering\n continue;\n\n if (inDE) prevInDE = inDE;\n\n if (outDE) {\n if (prevInDE) {\n prevInDE.next = outDE;\n prevInDE = undefined;\n }\n\n if (!firstOutDE) firstOutDE = outDE;\n }\n }\n\n if (prevInDE) prevInDE.next = firstOutDE;\n }\n\n /\n Finds rings and labels edges according to which rings are.\n \n The label is a number which is increased for each ring.\n \n @returns {Edge[]} edges that start rings\n /\n _findLabeledEdgeRings() {\n const edgeRingStarts: Edge[] = [];\n let label = 0;\n this.edges.forEach((edge) => {\n if (edge.label! >= 0) return;\n\n edgeRingStarts.push(edge);\n\n let e = edge;\n do {\n e.label = label;\n e = e.next!;\n } while (!edge.isEqual(e));\n\n label++;\n });\n\n return edgeRingStarts;\n }\n\n /\n Computes the EdgeRings formed by the edges in this graph.\n \n @returns {EdgeRing[]} - A list of all the EdgeRings in the graph.\n /\n getEdgeRings() {\n this._computeNextCWEdges();\n\n // Clear labels\n this.edges.forEach((edge) => {\n edge.label = undefined;\n });\n\n this._findLabeledEdgeRings().forEach((edge) => {\n // convertMaximalToMinimalEdgeRings\n this._findIntersectionNodes(edge).forEach((node) => {\n this._computeNextCCWEdges(node, edge.label!);\n });\n });\n\n const edgeRingList: EdgeRing[] = [];\n\n // find all edgerings\n this.edges.forEach((edge) => {\n if (edge.ring) return;\n edgeRingList.push(this._findEdgeRing(edge));\n });\n\n return edgeRingList;\n }\n\n /\n Find all nodes in a Maxima EdgeRing which are self-intersection nodes.\n \n @param {Node} startEdge - Start Edge of the Ring\n * @returns {Node[]} - intersection nodes\n /\n _findIntersectionNodes(startEdge: Edge) {\n const intersectionNodes = [];\n let edge = startEdge;\n do {\n // getDegree\n let degree = 0;\n edge.from.getOuterEdges().forEach((e) => {\n if (e.label === startEdge.label) ++degree;\n });\n\n if (degree > 1) intersectionNodes.push(edge.from);\n\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return intersectionNodes;\n }\n\n /\n Get the edge-ring which starts from the provided Edge.\n \n @param {Edge} startEdge - starting edge of the edge ring\n * @returns {EdgeRing} - EdgeRing which start Edge is the provided one.\n /\n _findEdgeRing(startEdge: Edge) {\n let edge = startEdge;\n const edgeRing = new EdgeRing();\n\n do {\n edgeRing.push(edge);\n edge.ring = edgeRing;\n edge = edge.next!;\n } while (!startEdge.isEqual(edge));\n\n return edgeRing;\n }\n\n /\n Removes a node from the Graph.\n \n It also removes edges asociated to that node\n * @param {Node} node - Node to be removed\n /\n removeNode(node: Node) {\n node.getOuterEdges().forEach((edge) => this.removeEdge(edge));\n node.innerEdges.forEach((edge) => this.removeEdge(edge));\n delete this.nodes[node.id];\n }\n\n /\n Remove edge from the graph and deletes the edge.\n \n @param {Edge} edge - Edge to be removed\n */\n removeEdge(edge: Edge) {\n this.edges = this.edges.filter((e) => !e.isEqual(edge));\n edge.deleteEdge();\n }\n}\n\nexport { Graph };\nexport default Graph;\n"],"mappings":";AAOA,SAAS,yBAAyB;;;ACNlC,SAAS,6BAA6B;AACtC,SAAS,aAAa;AAGtB,SAAS,SAAS,GAAW;AAC3B,UAAS,IAAI,MAA6B,IAAI,MAA4B,CAAC;AAC7E;AAgBO,SAAS,iBAAiB,IAAc,IAAc,GAAa;AACxE,QAAM,MAAM,GAAG,CAAC,IAAI,GAAG,CAAC,GACtB,MAAM,GAAG,CAAC,IAAI,GAAG,CAAC,GAClB,MAAM,EAAE,CAAC,IAAI,GAAG,CAAC,GACjB,MAAM,EAAE,CAAC,IAAI,GAAG,CAAC;AAEnB,SAAO,SAAS,MAAM,MAAM,MAAM,GAAG;AACvC;AAWO,SAAS,gBACd,MACA,MACA;AACA,QAAM,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC,GACxD,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC,GACpD,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC,GACpD,QAAQ,KAAK,SAAS,YAAY,CAAC,EAAE,IAAI,CAAC,MAAM,EAAE,CAAC,CAAC;AAEtD,SACE,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK,KAC1D,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK,KAC1D,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK,KAC1D,KAAK,IAAI,MAAM,MAAM,KAAK,MAAM,KAAK,IAAI,MAAM,MAAM,KAAK;AAE9D;AAaO,SAAS,iBACd,MACA,KACA;AACA,SAAO,IAAI,SAAS,YAAY,CAAC,EAAE;AAAA,IAAM,CAAC,MACxC,sBAAsB,MAAM,CAAC,GAAG,IAAI;AAAA,EACtC;AACF;AASO,SAAS,iBAAiB,QAAkB,QAAkB;AACnE,SAAO,OAAO,CAAC,MAAM,OAAO,CAAC,KAAK,OAAO,CAAC,MAAM,OAAO,CAAC;AAC1D;;;ACjFA,IAAM,OAAN,MAAM,MAAK;AAAA,EACT,OAAO,QAAQ,aAAuB;AACpC,WAAO,YAAY,KAAK,GAAG;AAAA,EAC7B;AAAA,EAQA,YAAY,aAAuB;AACjC,SAAK,KAAK,MAAK,QAAQ,WAAW;AAClC,SAAK,cAAc;AACnB,SAAK,aAAa,CAAC;AAGnB,SAAK,aAAa,CAAC;AACnB,SAAK,mBAAmB;AAAA,EAC1B;AAAA,EAEA,gBAAgB,MAAY;AAC1B,SAAK,aAAa,KAAK,WAAW,OAAO,CAAC,MAAM,EAAE,KAAK,OAAO,KAAK,KAAK,EAAE;AAAA,EAC5E;AAAA,EAEA,gBAAgB,MAAY;AAC1B,SAAK,aAAa,KAAK,WAAW,OAAO,CAAC,MAAM,EAAE,GAAG,OAAO,KAAK,GAAG,EAAE;AAAA,EACxE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,aAAa,MAAY;AACvB,SAAK,WAAW,KAAK,IAAI;AACzB,SAAK,mBAAmB;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,iBAAiB;AACf,QAAI,CAAC,KAAK,kBAAkB;AAG1B,WAAK,WAAW,KAAK,CAAC,GAAG,MAAM;AAC7B,cAAM,QAAQ,EAAE,IACd,QAAQ,EAAE;AAEZ,YACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK,KAC9C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,IAAI;AAE7C,iBAAO;AACT,YACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,IAAI,KAC7C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK;AAE9C,iBAAO;AAET,YACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,MAAM,KAC/C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,MAAM,GAC/C;AACA,cACE,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK,KAC9C,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,KAAK;AAE9C,mBAAO,MAAM,YAAY,CAAC,IAAI,MAAM,YAAY,CAAC;AACnD,iBAAO,MAAM,YAAY,CAAC,IAAI,MAAM,YAAY,CAAC;AAAA,QACnD;AAEA,cAAM,MAAM;AAAA,UACV,KAAK;AAAA,UACL,MAAM;AAAA,UACN,MAAM;AAAA,QACR;AACA,YAAI,MAAM,EAAG,QAAO;AACpB,YAAI,MAAM,EAAG,QAAO;AAEpB,cAAM,KACF,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC,IACtD,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC,GACxD,KACE,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC,IACtD,KAAK,IAAI,MAAM,YAAY,CAAC,IAAI,KAAK,YAAY,CAAC,GAAG,CAAC;AAE1D,eAAO,KAAK;AAAA,MACd,CAAC;AACD,WAAK,mBAAmB;AAAA,IAC1B;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,gBAAgB;AACd,SAAK,eAAe;AACpB,WAAO,KAAK;AAAA,EACd;AAAA,EAEA,aAAa,GAAW;AACtB,SAAK,eAAe;AACpB,WAAO,KAAK,WAAW,CAAC;AAAA,EAC1B;AAAA,EAEA,aAAa,MAAY;AACvB,SAAK,WAAW,KAAK,IAAI;AAAA,EAC3B;AACF;;;AC7HA,SAAS,kBAAkB;AAQ3B,IAAM,OAAN,MAAM,MAAK;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaT,cAAc;AACZ,QAAI,CAAC,KAAK,UAAU;AAClB,WAAK,WAAW,IAAI,MAAK,KAAK,IAAI,KAAK,IAAI;AAC3C,WAAK,SAAS,WAAW;AAAA,IAC3B;AAEA,WAAO,KAAK;AAAA,EACd;AAAA;AAAA;AAAA;AAAA;AAAA,EAMA,YAAY,MAAY,IAAU;AAChC,SAAK,OAAO;AACZ,SAAK,KAAK;AAEV,SAAK,OAAO;AACZ,SAAK,QAAQ;AACb,SAAK,WAAW;AAChB,SAAK,OAAO;AAEZ,SAAK,KAAK,aAAa,IAAI;AAC3B,SAAK,GAAG,aAAa,IAAI;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA,EAKA,aAAa;AACX,SAAK,KAAK,gBAAgB,IAAI;AAC9B,SAAK,GAAG,gBAAgB,IAAI;AAAA,EAC9B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,QAAQ,MAAY;AAClB,WAAO,KAAK,KAAK,OAAO,KAAK,KAAK,MAAM,KAAK,GAAG,OAAO,KAAK,GAAG;AAAA,EACjE;AAAA,EAEA,WAAW;AACT,WAAO,UAAU,KAAK,KAAK,EAAE,OAAO,KAAK,GAAG,EAAE;AAAA,EAChD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,eAAe;AACb,WAAO,WAAW,CAAC,KAAK,KAAK,aAAa,KAAK,GAAG,WAAW,CAAC;AAAA,EAChE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,UAAU,MAAY;AACpB,WAAO;AAAA,MACL,KAAK,KAAK;AAAA,MACV,KAAK,GAAG;AAAA,MACR,KAAK,GAAG;AAAA,IACV;AAAA,EACF;AACF;;;AC1FA,SAAS,YAAY,SAAS,SAAAA,cAAa;AAC3C,SAAS,gBAAgB;AACzB,SAAS,yBAAAC,8BAA6B;AAUtC,IAAM,WAAN,MAAe;AAAA,EAeb,cAAc;AACZ,SAAK,QAAQ,CAAC;AACd,SAAK,UAAU;AACf,SAAK,WAAW;AAAA,EAClB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,KAAK,MAAY;AACf,SAAK,MAAM,KAAK,IAAI;AACpB,SAAK,UAAU,KAAK,WAAW;AAAA,EACjC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAI,GAAW;AACb,WAAO,KAAK,MAAM,CAAC;AAAA,EACrB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,IAAI,SAAS;AACX,WAAO,KAAK,MAAM;AAAA,EACpB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,QAAQ,GAAuD;AAC7D,SAAK,MAAM,QAAQ,CAAC;AAAA,EACtB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,IAAO,GAAyD;AAC9D,WAAO,KAAK,MAAM,IAAI,CAAC;AAAA,EACzB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,KAAK,GAA0D;AAC7D,WAAO,KAAK,MAAM,KAAK,CAAC;AAAA,EAC1B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAYA,UAAU;AAER,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWA,SAAS;AAGP,UAAM,UAAU,KAAK,MAAM,OAAO,CAAC,MAAM,MAAM,MAAM;AACjD,UAAI,KAAK,KAAK,YAAY,CAAC,IAAI,KAAK,MAAM,IAAI,EAAE,KAAK,YAAY,CAAC;AAChE,eAAO;AACT,aAAO;AAAA,IACT,GAAG,CAAC,GACJ,SAAS,YAAY,IAAI,KAAK,SAAS,WAAW,GAClD,SAAS,UAAU,KAAK,KAAK,QAC7B,OAAO;AAAA,MACL,KAAK,MAAM,KAAK,EAAE,KAAK;AAAA,MACvB,KAAK,MAAM,OAAO,EAAE,KAAK;AAAA,MACzB,KAAK,MAAM,KAAK,EAAE,KAAK;AAAA,IACzB;AAEF,QAAI,SAAS;AACX,aACE,KAAK,MAAM,KAAK,EAAE,KAAK,YAAY,CAAC,IACpC,KAAK,MAAM,KAAK,EAAE,KAAK,YAAY,CAAC;AAExC,WAAO,OAAO;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,eAAe;AACb,WAAO,WAAW,KAAK,MAAM,IAAI,CAAC,SAAS,KAAK,KAAK,WAAW,CAAC;AAAA,EACnE;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,YAAY;AACV,QAAI,KAAK,QAAS,QAAO,KAAK;AAC9B,UAAM,cAAc,KAAK,MAAM,IAAI,CAAC,SAAS,KAAK,KAAK,WAAW;AAClE,gBAAY,KAAK,KAAK,MAAM,CAAC,EAAE,KAAK,WAAW;AAC/C,WAAQ,KAAK,UAAU,QAAQ,CAAC,WAAW,CAAC;AAAA,EAC9C;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,cAAc;AACZ,QAAI,KAAK,SAAU,QAAO,KAAK;AAC/B,WAAQ,KAAK,WAAW,SAAS,KAAK,UAAU,CAAC;AAAA,EAInD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,OAAO,uBACL,cACA,WACsB;AACtB,UAAM,eAAe,aAAa,YAAY;AAE9C,QAAI,aAA+B;AACnC,cAAU,QAAQ,CAAC,UAAU;AAC3B,YAAM,cAAc,MAAM,YAAY;AAEtC,UAAI,SAAU,eAAc,SAAS,YAAY;AAGjD,UAAI,gBAAgB,aAAa,YAAY,EAAG;AAEhD,UAAI,iBAAiB,aAAa,YAAY,GAAG;AAC/C,cAAM,0BAA0B,aAAa;AAAA,UAC3C,CAAC,SAAS,KAAK,KAAK;AAAA,QACtB;AAEA,YAAI;AACJ,mBAAW,MAAM,yBAAyB;AACxC,cACE,CAAC,MAAM,KAAK,CAAC,SAAS,iBAAiB,IAAI,KAAK,KAAK,WAAW,CAAC,GACjE;AACA,wBAAY;AAAA,UACd;AAAA,QACF;AAEA,YAAI,aAAa,MAAM,OAAOD,OAAM,SAAS,CAAC,GAAG;AAC/C,cAAI,CAAC,YAAY,iBAAiB,aAAa,WAAW;AACxD,uBAAW;AAAA,QACf;AAAA,MACF;AAAA,IACF,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,OAAO,IAAoB;AACzB,WAAOC,uBAAsB,IAAI,KAAK,UAAU,CAAC;AAAA,EACnD;AACF;;;AClPA,SAAS,aAAa,mBAAmB;AACzC,SAAS,iBAAiB;AAe1B,SAAS,gBAAgB,SAAqB;AAC5C,MAAI,CAAC,QAAS,OAAM,IAAI,MAAM,mBAAmB;AAEjD,MACE,QAAQ,SAAS,uBACjB,QAAQ,SAAS,wBACjB,QAAQ,SAAS,qBACjB,QAAQ,SAAS,gBACjB,QAAQ,SAAS;AAEjB,UAAM,IAAI;AAAA,MACR,uBAAuB,QAAQ,IAAI;AAAA,IACrC;AACJ;AAWA,IAAM,QAAN,MAAM,OAAM;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAWV,OAAO,YACL,SAKA;AACA,oBAAgB,OAAO;AAEvB,UAAM,QAAQ,IAAI,OAAM;AACxB,gBAAY,SAAS,CAAC,YAAY;AAChC,gBAAU,SAAS,cAAc,oBAAoB;AAErD,kBAAsB,SAAS,CAAC,MAAM,QAAQ;AAC5C,YAAI,MAAM;AACR,gBAAM,QAAQ,MAAM,QAAQ,IAAI,GAC9B,MAAM,MAAM,QAAQ,GAAG;AAEzB,gBAAM,QAAQ,OAAO,GAAG;AAAA,QAC1B;AACA,eAAO;AAAA,MACT,CAAC;AAAA,IACH,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,QAAQ,aAAuB;AAC7B,UAAM,KAAK,KAAK,QAAQ,WAAW;AACnC,QAAI,OAAO,KAAK,MAAM,EAAE;AACxB,QAAI,CAAC,KAAM,QAAO,KAAK,MAAM,EAAE,IAAI,IAAI,KAAK,WAAW;AAEvD,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,QAAQ,MAAY,IAAU;AAC5B,UAAM,OAAO,IAAI,KAAK,MAAM,EAAE,GAC5B,eAAe,KAAK,YAAY;AAElC,SAAK,MAAM,KAAK,IAAI;AACpB,SAAK,MAAM,KAAK,YAAY;AAAA,EAC9B;AAAA,EAEA,cAAc;AACZ,SAAK,QAAQ,CAAC;AAGd,SAAK,QAAQ,CAAC;AAAA,EAChB;AAAA;AAAA;AAAA;AAAA,EAKA,gBAAgB;AACd,WAAO,KAAK,KAAK,KAAK,EACnB,IAAI,CAAC,OAAO,KAAK,MAAM,EAAE,CAAC,EAC1B,QAAQ,CAAC,SAAS,KAAK,gBAAgB,IAAI,CAAC;AAAA,EACjD;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,gBAAgB,MAAY;AAE1B,QAAI,KAAK,WAAW,UAAU,GAAG;AAC/B,YAAM,aAAa,KAAK,cAAc,EAAE,IAAI,CAAC,MAAM,EAAE,EAAE;AACvD,WAAK,WAAW,IAAI;AACpB,iBAAW,QAAQ,CAAC,MAAM,KAAK,gBAAgB,CAAC,CAAC;AAAA,IACnD;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,iBAAiB;AACf,SAAK,oBAAoB;AACzB,SAAK,sBAAsB;AAG3B,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,UAAI,KAAK,UAAU,KAAK,SAAU,OAAO;AACvC,aAAK,WAAW,KAAK,QAAS;AAC9B,aAAK,WAAW,IAAI;AAAA,MACtB;AAAA,IACF,CAAC;AAAA,EACH;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAUA,oBAAoB,MAAa;AAC/B,QAAI,OAAO,SAAS,aAAa;AAC/B,aAAO,KAAK,KAAK,KAAK,EAAE;AAAA,QAAQ,CAAC,OAC/B,KAAK,oBAAoB,KAAK,MAAM,EAAE,CAAC;AAAA,MACzC;AAAA,IACF,OAAO;AACL,WAAK,cAAc,EAAE,QAAQ,CAAC,MAAM,MAAM;AACxC,aAAK;AAAA,WACF,MAAM,IAAI,KAAK,cAAc,EAAE,SAAS,KAAK;AAAA,QAChD,EAAE,SAAU,OAAO;AAAA,MACrB,CAAC;AAAA,IACH;AAAA,EACF;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAaA,qBAAqB,MAAY,OAAe;AAC9C,UAAM,QAAQ,KAAK,cAAc;AACjC,QAAI,YAAY;AAEhB,aAAS,IAAI,MAAM,SAAS,GAAG,KAAK,GAAG,EAAE,GAAG;AAC1C,UAAI,KAAK,MAAM,CAAC,GACd,MAAM,GAAG,UACT,OACA;AAEF,UAAI,GAAG,UAAU,MAAO,SAAQ;AAEhC,UAAI,IAAK,UAAU,MAAO,QAAO;AAEjC,UAAI,CAAC,SAAS,CAAC;AAEb;AAEF,UAAI,KAAM,YAAW;AAErB,UAAI,OAAO;AACT,YAAI,UAAU;AACZ,mBAAS,OAAO;AAChB,qBAAW;AAAA,QACb;AAEA,YAAI,CAAC,WAAY,cAAa;AAAA,MAChC;AAAA,IACF;AAEA,QAAI,SAAU,UAAS,OAAO;AAAA,EAChC;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EASA,wBAAwB;AACtB,UAAM,iBAAyB,CAAC;AAChC,QAAI,QAAQ;AACZ,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,UAAI,KAAK,SAAU,EAAG;AAEtB,qBAAe,KAAK,IAAI;AAExB,UAAI,IAAI;AACR,SAAG;AACD,UAAE,QAAQ;AACV,YAAI,EAAE;AAAA,MACR,SAAS,CAAC,KAAK,QAAQ,CAAC;AAExB;AAAA,IACF,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,eAAe;AACb,SAAK,oBAAoB;AAGzB,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,WAAK,QAAQ;AAAA,IACf,CAAC;AAED,SAAK,sBAAsB,EAAE,QAAQ,CAAC,SAAS;AAE7C,WAAK,uBAAuB,IAAI,EAAE,QAAQ,CAAC,SAAS;AAClD,aAAK,qBAAqB,MAAM,KAAK,KAAM;AAAA,MAC7C,CAAC;AAAA,IACH,CAAC;AAED,UAAM,eAA2B,CAAC;AAGlC,SAAK,MAAM,QAAQ,CAAC,SAAS;AAC3B,UAAI,KAAK,KAAM;AACf,mBAAa,KAAK,KAAK,cAAc,IAAI,CAAC;AAAA,IAC5C,CAAC;AAED,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,uBAAuB,WAAiB;AACtC,UAAM,oBAAoB,CAAC;AAC3B,QAAI,OAAO;AACX,OAAG;AAED,UAAI,SAAS;AACb,WAAK,KAAK,cAAc,EAAE,QAAQ,CAAC,MAAM;AACvC,YAAI,EAAE,UAAU,UAAU,MAAO,GAAE;AAAA,MACrC,CAAC;AAED,UAAI,SAAS,EAAG,mBAAkB,KAAK,KAAK,IAAI;AAEhD,aAAO,KAAK;AAAA,IACd,SAAS,CAAC,UAAU,QAAQ,IAAI;AAEhC,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,cAAc,WAAiB;AAC7B,QAAI,OAAO;AACX,UAAM,WAAW,IAAI,SAAS;AAE9B,OAAG;AACD,eAAS,KAAK,IAAI;AAClB,WAAK,OAAO;AACZ,aAAO,KAAK;AAAA,IACd,SAAS,CAAC,UAAU,QAAQ,IAAI;AAEhC,WAAO;AAAA,EACT;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAQA,WAAW,MAAY;AACrB,SAAK,cAAc,EAAE,QAAQ,CAAC,SAAS,KAAK,WAAW,IAAI,CAAC;AAC5D,SAAK,WAAW,QAAQ,CAAC,SAAS,KAAK,WAAW,IAAI,CAAC;AACvD,WAAO,KAAK,MAAM,KAAK,EAAE;AAAA,EAC3B;AAAA;AAAA;AAAA;AAAA;AAAA;AAAA,EAOA,WAAW,MAAY;AACrB,SAAK,QAAQ,KAAK,MAAM,OAAO,CAAC,MAAM,CAAC,EAAE,QAAQ,IAAI,CAAC;AACtD,SAAK,WAAW;AAAA,EAClB;AACF;;;ALlUA,SAAS,WACP,SAC4B;AAC5B,QAAM,QAAQ,MAAM,YAAY,OAAO;AAGvC,QAAM,cAAc;AAGpB,QAAM,eAAe;AAGrB,QAAM,QAAoB,CAAC,GACzB,SAAqB,CAAC;AAExB,QACG,aAAa,EACb,OAAO,CAAC,aAAa,SAAS,QAAQ,CAAC,EACvC,QAAQ,CAAC,aAAa;AACrB,QAAI,SAAS,OAAO,EAAG,OAAM,KAAK,QAAQ;AAAA,QACrC,QAAO,KAAK,QAAQ;AAAA,EAC3B,CAAC;AAGH,QAAM,QAAQ,CAAC,SAAS;AACtB,QAAI,SAAS,uBAAuB,MAAM,MAAM,EAAG,QAAO,KAAK,IAAI;AAAA,EACrE,CAAC;AAGD,SAAO,kBAAkB,OAAO,IAAI,CAAC,UAAU,MAAM,UAAU,CAAC,CAAC;AACnE;AAGA,IAAO,gBAAQ;","names":["point","booleanPointInPolygon"]}

+13

-13

package.json

		{
		"name": "@turf/polygonize",
		"version": "7.2.0",
		"description": "turf polygonize module",
		"version": "7.3.0",
		"description": "Polygonizes a set of lines that represents edges in a planar graph.",
		"author": "Turf Authors",
		@@ -60,3 +60,3 @@ "contributors": [
		"@types/benchmark": "^2.1.5",
		"@types/tape": "^4.13.4",
		"@types/tape": "^5.8.1",
		"benchmark": "^2.1.4",
		@@ -66,17 +66,17 @@ "load-json-file": "^7.0.1",
		"tape": "^5.9.0",
		"tsup": "^8.3.5",
		"tsx": "^4.19.2",
		"typescript": "^5.5.4",
		"write-json-file": "^5.0.0"
		"tsup": "^8.4.0",
		"tsx": "^4.19.4",
		"typescript": "^5.8.3",
		"write-json-file": "^6.0.0"
		},
		"dependencies": {
		"@turf/boolean-point-in-polygon": "^7.2.0",
		"@turf/envelope": "^7.2.0",
		"@turf/helpers": "^7.2.0",
		"@turf/invariant": "^7.2.0",
		"@turf/meta": "^7.2.0",
		"@turf/boolean-point-in-polygon": "7.3.0",
		"@turf/envelope": "7.3.0",
		"@turf/helpers": "7.3.0",
		"@turf/invariant": "7.3.0",
		"@turf/meta": "7.3.0",
		"@types/geojson": "^7946.0.10",
		"tslib": "^2.8.1"
		},
		"gitHead": "7b0f0374c4668cd569f8904c71e2ae7d941be867"
		"gitHead": "9f58a103e8f9a587ab640307ed03ba5233913ddd"
		}

@turf/polygonize - npm Package Compare versions

Worsened metrics

Dependency changes