<commit_before>var PolyBool = require('polybooljs');
var geo_map = require('../map');

/**
 * A list of flat polygon lists.
 *
 * @typedef {Array.<Array.<Array.<geo.geoPositionFlat>>>} geo.polygonList
 */

/**
 * A polygon in any of a variety of formats.
 *
 * This can be any object with a ``toPolygonList`` and ``fromPolygonList``
 * method.
 *
 * @typedef {geo.polygonFlat|Array.<geo.polygonFlat>|Array.<Array.<geo.polygonFlat>>|geo.polygonObject|Array.<geo.polygonObject>|Array.<geo.geoPositionFlat>|Array.<Array.<geo.geoPositionFlat>>|geo.polygonList|object} geo.polygonAny
 */

/**
 * Object specification for polygon operation options.
 *
 * @typedef {object} geo.util.polyop.spec
 * @property {geo.polygonAny} [poly1] The first polygon set to operate on.
 * @property {geo.polygonAny} [poly2] The second polygon set to operate on.
 * @property {number} [epsilon1] A precision value to use when computing the
 *   operation.  If not specified, this is computed from the range of values in
 *   ``poly1``.  It is used for processing ``poly1`` and the general operation.
 * @property {number} [epsilon1] A precision value to use when processing
 *   ``poly2``.  If not specified, this is computed from the range of values in
 *   ``poly2``.
 * @property {string|object} [style] If specified, the preferred output style.
 *   This can be (flat|object)[-list[list[-outer[-list]]]].  If an object,
 *   the object must have a method ``fromPolygonList``.
 * @property {string|geo.transform} [ingcs] The default coordinate
 *   system of the source polygon coordinates.  If not specified , this is
 *   taken from the feature first or the map second if either is available.
 * @property {string|geo.transform} [gcs] The default coordinate system to use
 *   for the actual operations.  This is where the epsilon and rdp values are
 *   applied.  If not specified , this is taken from the map second if
 *   available.
 * @property {geo.map} [map] Used for ``ingcs`` and ``gcs`` if needed.
 * @property {string} [innerOperation="union"] one of union, intersect, xor.
 *   Used to combine individual polygons in each of ``poly1`` and ``poly2``
 *   before the main operation is carried out.
 * @property {object} [correspond] If present, information about the
 *   correspondence of the input and output polygons is added to this object.
 *   This is of the form {poly1: [idx...], poly2: [idx...], exact1: [idx...],
 *   exact2: [idx...]}, where the [idx...] array is the length of the input
 *  polygon array and each entry is either undefined or contains a list of
 *   indices of corresponding output polygons.  Exact means that all of the
 *   points in the input polygon are in the output polygon.  Multiple inputs
 *   can refer to the same output.
 * @property {number} [tolerance] A tolerance value to pass to features,
 *   annotations, or other object-based polygon generators to specify how
 *   closely non-polygons are converted to polygons.  This is in the feature's
 *   gcs coordinate system.
 * @property {number} [pixelTolerance] A tolerance value to pass to features,
 *   annotations, or other object-based polygon generators to specify how
 *   closely non-polygons are converted to polygons.  This is interpreted in
 *   the feature's map's display coordinates.
 */

const AlternateOpNames = {
  '+': 'union',
  '|': 'union',
  add: 'union',
  '-': 'difference',
  sub: 'difference',
  subtract: 'difference',
  minus: 'difference',
  '*': 'intersect',
  '&': 'intersect',
  mul: 'intersect',
  multiply: 'intersect',
  x: 'xor',
  '^': 'xor'
};

/**
 * Convert a segment list to a polygon list.
 *
 * @param {object[]} seglist A PolyBool segment list.
 * @returns {geo.polygonList} A polygon list.
 */
function seglistToPolygonList(seglist) {
  // This single line doesn't arrange holes correctly
  // return seglist.map((s) => PolyBool.polygon(s).regions);
  const polys = [];
  seglist.forEach((s) => {
    const geojson = PolyBool.polygonToGeoJSON(PolyBool.polygon(s));
    if (geojson.type === 'MultiPolygon') {
      geojson.coordinates.forEach((p) => {
        polys.push(p.map((h) => h.slice(0, h.length - 1)));
      });
    } else if (geojson.type === 'Polygon') {
      polys.push(geojson.coordinates.map((h) => h.slice(0, h.length - 1)));
    }
  });
  return polys;
}

/**
 * Perform an boolean operation on a seglist from polygons.
 *
 * @param {string} op One of 'union', 'intersect', or other value PolyBool
 *      supports.
 * @param {number} epsilon Precision for calculations.  In degrees, 1e-9 is
 *      around 0.11 mm in ground distance.
 * @param {object} seglist A seglist array as used by the polybool library.
 * @returns {object} A seglist array.
 */
function polygonOperationSeglist(op, epsilon, seglist) {
  op = 'select' + op.charAt(0).toUpperCase() + op.slice(1);
  PolyBool.epsilon(epsilon);

  while (seglist.length > 1) {
    const newlist = [];
    const half = Math.ceil(seglist.length / 2);
    for (let i = 0; i < half; i += 1) {
      let segments = seglist[i];
      if (i + half < seglist.length) {
        let nextseg = seglist[i + half];<commit_msg>perf: Speed up converting polybool segments to polygons<commit_after>var PolyBool = require('polybooljs');
var geo_map = require('../map');
var util = require('../util/common');

/**
 * A list of flat polygon lists.
 *
 * @typedef {Array.<Array.<Array.<geo.geoPositionFlat>>>} geo.polygonList
 */

/**
 * A polygon in any of a variety of formats.
 *
 * This can be any object with a ``toPolygonList`` and ``fromPolygonList``
 * method.
 *
 * @typedef {geo.polygonFlat|Array.<geo.polygonFlat>|Array.<Array.<geo.polygonFlat>>|geo.polygonObject|Array.<geo.polygonObject>|Array.<geo.geoPositionFlat>|Array.<Array.<geo.geoPositionFlat>>|geo.polygonList|object} geo.polygonAny
 */

/**
 * Object specification for polygon operation options.
 *
 * @typedef {object} geo.util.polyop.spec
 * @property {geo.polygonAny} [poly1] The first polygon set to operate on.
 * @property {geo.polygonAny} [poly2] The second polygon set to operate on.
 * @property {number} [epsilon1] A precision value to use when computing the
 *   operation.  If not specified, this is computed from the range of values in
 *   ``poly1``.  It is used for processing ``poly1`` and the general operation.
 * @property {number} [epsilon1] A precision value to use when processing
 *   ``poly2``.  If not specified, this is computed from the range of values in
 *   ``poly2``.
 * @property {string|object} [style] If specified, the preferred output style.
 *   This can be (flat|object)[-list[list[-outer[-list]]]].  If an object,
 *   the object must have a method ``fromPolygonList``.
 * @property {string|geo.transform} [ingcs] The default coordinate
 *   system of the source polygon coordinates.  If not specified , this is
 *   taken from the feature first or the map second if either is available.
 * @property {string|geo.transform} [gcs] The default coordinate system to use
 *   for the actual operations.  This is where the epsilon and rdp values are
 *   applied.  If not specified , this is taken from the map second if
 *   available.
 * @property {geo.map} [map] Used for ``ingcs`` and ``gcs`` if needed.
 * @property {string} [innerOperation="union"] one of union, intersect, xor.
 *   Used to combine individual polygons in each of ``poly1`` and ``poly2``
 *   before the main operation is carried out.
 * @property {object} [correspond] If present, information about the
 *   correspondence of the input and output polygons is added to this object.
 *   This is of the form {poly1: [idx...], poly2: [idx...], exact1: [idx...],
 *   exact2: [idx...]}, where the [idx...] array is the length of the input
 *  polygon array and each entry is either undefined or contains a list of
 *   indices of corresponding output polygons.  Exact means that all of the
 *   points in the input polygon are in the output polygon.  Multiple inputs
 *   can refer to the same output.
 * @property {number} [tolerance] A tolerance value to pass to features,
 *   annotations, or other object-based polygon generators to specify how
 *   closely non-polygons are converted to polygons.  This is in the feature's
 *   gcs coordinate system.
 * @property {number} [pixelTolerance] A tolerance value to pass to features,
 *   annotations, or other object-based polygon generators to specify how
 *   closely non-polygons are converted to polygons.  This is interpreted in
 *   the feature's map's display coordinates.
 */

const AlternateOpNames = {
  '+': 'union',
  '|': 'union',
  add: 'union',
  '-': 'difference',
  sub: 'difference',
  subtract: 'difference',
  minus: 'difference',
  '*': 'intersect',
  '&': 'intersect',
  mul: 'intersect',
  multiply: 'intersect',
  x: 'xor',
  '^': 'xor'
};

/**
 * Convert a segment list to a polygon list.
 *
 * @param {object[]} seglist A PolyBool segment list.
 * @returns {geo.polygonList|undefined} A polygon list.
 */
function seglistToPolygonList(seglist) {
  // This single line doesn't arrange holes correctly
  // return seglist.map((s) => PolyBool.polygon(s).regions);
  /* This uses PolyBools' operations (mostly), but is much slower than needed
   * since it goes through geojson.
  const polys = [];
  seglist.forEach((s) => {
    const geojson = PolyBool.polygonToGeoJSON(PolyBool.polygon(s));
    if (geojson.type === 'MultiPolygon') {
      geojson.coordinates.forEach((p) => {
        polys.push(p.map((h) => h.slice(0, h.length - 1)));
      });
    } else if (geojson.type === 'Polygon') {
      polys.push(geojson.coordinates.map((h) => h.slice(0, h.length - 1)));
    }
  });
  return polys;
   */
  const polys = []; // end result
  const borders = []; // polygons in format needed for util.pointInPolygon
  const regions = []; // polygons in end result format
  const parents = []; // list of parents of each polygon
  seglist.forEach((s) => PolyBool.polygon(s).regions.forEach((r) => {
    const border = r.map((pt) => ({x: pt[0], y: pt[1]}));
    if (border.length < 3) {
      return;
    }
    parents.push([]);
    borders.forEach((b, i) => {
      if (util.pointInPolygon(border[0], b)) {
        parents[borders.length].push(i);
      } else if (util.pointInPolygon(b[0], border)) {
        parents[i].push(borders.length);
      }
    });
    regions.push(r);
    borders.push(border);
  }));
  /* find nested polygons */
  const dest = Array(regions.length);
  let used = 0;
  while (used < regions.length) {
    for (let i = 0; i < regions.length; i += 1) {
      if (dest[i] === undefined && !parents[i].length) {
        dest[i] = polys.length;
        /* reverse the outer polygons for consistency with how PolyBool
         * generates geojson */
        polys.push([regions[i].reverse()]);
        used += 1;
      }
    }
    for (let i = 0; i < regions.length; i += 1) {
      if (dest[i] === undefined && parents[i].length === 1 && dest[parents[i][0]] !== undefined) {
        polys[dest[parents[i][0]]].push(regions[i]);
        dest[i] = dest[parents[i][0]];
        used += 1;
      }
    }
    for (let i = 0; i < regions.length; i += 1) {
      parents[i] = parents[i].filter((d) => dest[d] === undefined);
    }
  }
  return polys.length ? polys : [[]];
}

/**
 * Perform an boolean operation on a seglist from polygons.
 *
 * @param {string} op One of 'union', 'intersect', or other value PolyBool
 *      supports.
 * @param {number} epsilon Precision for calculations.  In degrees, 1e-9 is
 *      around 0.11 mm in ground distance.
 * @param {object} seglist A seglist array as used by the polybool library.
 * @returns {object} A seglist array.
 */
function polygonOperationSeglist(op, epsilon, seglist) {
  op = 'select' + op.charAt(0).toUpperCase() + op.slice(1);
  PolyBool.epsilon(epsilon);

  while (seglist.length > 1) {
    const newlist = [];
    const half = Math.ceil(seglist.length / 2);
    for (let i = 0; i < half; i += 1) {
      let segments = seglist[i];
      if (i + half < seglist.length) {
        let nextseg = seglist[i + half];
{'fraction_non_alphanumeric': 0.13779331003494757, 'fraction_numerical': 0.006323847561990348, 'mean_word_length': 3.4252577319587627, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4291104', 'n_tokens_mistral': 3837, 'n_tokens_neox': 3715, 'n_words': 1296}