agmission/Development/server/helpers/gridline_util.js

const
  utils = require('./utils'),
  // debug = require('debug')('agm:gridline_util'),
  Zone = require('./geometry/zone').Zone,
  ZoneType = require('./geometry/zone').Type,
  Bound = require('./geometry/rectbound').Bound,
  geoUtil = require('./geo_util'),
  polyUtil = require('./poly_util'),
  jobUtil = require('./job_util'),
  mathUtil = require('./math_helper'),
  bufUtil = require('./line_buffer'),
  cloneDeep = require('clone-deep'),
  _ = require("lodash"),
  { Errors } = require('./constants');

// UTM and LatLon LatLonEllipsoidal for accuracy, for convert ll and utm
let Utm, LatLonUTM;
// LatLonSpherical for calculating distances, bearings, destinations, etc on great circle paths and rhumb lines.
let LatLonSP;

let { rotateDEG, translate, transform, inverse, applyToPoint, applyToPoints } = require('transformation-matrix');
const { AppInputError } = require('./app_error');

const deg2rad = 0.01745329251994328;
const rad2deg = 57.29577951308238;  // degrees                

const MIN_SWATH_WIDTH = 1;          // meter
const MIN_SEGMENT_LENGTH = 10;      // meters
const BEST_HEADING_INC = 10;        // degrees
const BST_HDG = -999;               // best heading


function latlngToUTMCoors(coors, refZone) {
  if (!coors || !coors.length)
    return null;

  if (!refZone)
    refZone = { zone: undefined, hemisphere: undefined };

  let lnlat, utm, latlonObj = new LatLonUTM(0, 0), _coors = [];
  for (let k = 0; k < coors.length; k++) {
    lnlat = coors[k];
    latlonObj.lat = lnlat[1]; latlonObj.lon = lnlat[0];

    try {
      utm = latlonObj.toUtm(refZone.zone, refZone.hemisphere);
    } catch (error) { // Handle the invalid UTM zone after converted case
      _coors = [];
      break;
    }

    if (undefined == refZone.zone) {
      refZone.zone = utm.zone;
      refZone.hemisphere = utm.hemisphere;
    }

    _coors.push({ x: utm.easting, y: utm.northing });
  }
  if (!_coors.length)
    return null;
  else
    return { utmCoors: _coors };
}

/**
 * Generate Gridlines for area(s) in LatLon.
 * @param {*} job the given job
 * @param {*} sprayIds sprayArea Id
 * @param {*} halfSwathOffset should offset 1/2 swath
 * @param {*} x UTM coordinate of the master point x
 * @param {*} y UTM coordinate of the master point x
 * @param {*} heading heading of the guide lines
 * @param {*} abLine AB Line
 * @param {*} options generate option { regenerate: true/false };
 * normally use useGroup for interactive with user with selected areas as one group to generate lines with the same heading
 */
async function getLinesLatLng(job, sprayIds, halfSwathOffset = true, x, y, heading = 0, abLine, options = { useGroup: false, regenerate: true }) {

  const swath = utils.toMeter(job.swathWidth, job.measureUnit);
  if (swath < 4.99) AppInputError.throw(Errors.INVALID_SWATH_WIDTH);

  // Dynamically load ES geodesy modules. No need when all in ESM codes later.
  const llsMod = await import('@mickeyjohn/geodesy/latlon-spherical.js');
  LatLonSP = llsMod.default;
  const utmMod = await import('@mickeyjohn/geodesy/utm.js');
  Utm = utmMod.default;
  LatLonUTM = utmMod.LatLon;

  sprayIds = sprayIds || [];

  let utmSprayZones = [], utmXclZones = [], latlng = new LatLonUTM(0, 0);
  // Get the copy of arrays to work on to avoid direct mutation to jobs's data (JavaScript)
  let sprayZones = job.sprayAreas.slice(0), xclZones = job.excludedAreas.slice(0), bufs = job.bufs.slice(0);
  let masterPoint, genHeading;
  let linesResult = [], genResult, sprZones;
  let bbox = geoUtil.updateAreasBBoxLL(sprayZones);
  let refZone = geoUtil.calcRefZonebyBbox(bbox) || { zone: undefined, hemisphere: undefined };

  // Convert line buffers to xcl zones then also include them within the next process
  if (bufs && bufs.length) {
    for (let i = 0; i < bufs.length; i++) {
      const polyCoors = bufUtil.lineBuffer(bufs[i].geometry.coordinates, utils.toMeter(bufs[i].properties.width, job.measureUnit));
      if (!utils.isEmptyArray(polyCoors)) {
        xclZones.push(jobUtil.createXclArea({ name: `XCL${i + 1}`, coors: polyCoors }));
      }
    }
  }

  utmXclZones = await convertAreasCoorstoUTM(xclZones, ZoneType.XCL, refZone);

  let regenIds = [];

  /* Generate lines for selected areas and ones with no lines yet. Handle areas or area with same name groups separatedly.
   * Use in Agmission web client's GUI
   */
  if (options.useGroup) {

    /* Group areas by ones with the same name to generate lines by each of these groups */
    let selByName = {};   // selected area names hash list
    let restByName = {};  // the rest area names hash list
    if (!utils.isEmptyArray(sprayIds)) {
      let selAreas = [], j = sprayZones.length - 1;
      while (j >= 0) {
        if (sprayZones[j]._id && sprayIds.includes(sprayZones[j]._id.toHexString()))
          selAreas.push(sprayZones.splice(j, 1)[0]);
        j--;
      }
      if (selAreas.length)
        selByName = _.groupBy(selAreas, it => it.properties.name.toLowerCase());
    }
    restByName = _.groupBy(sprayZones, it => it.properties.name.toLowerCase());

    let selItems = Object.values(selByName);
    if (selItems.length) {
      for (let i = 0; i < selItems.length; i++) {
        selItems[i] = await convertAreasCoorstoUTM(selItems[i], ZoneType.NORMAL, refZone);
      }
      const selSprayZones = [].concat.apply([], selItems);
      // Scan for intersected xcls only for the next step
      let selXcls = getOverlapXcls(utmXclZones, geoUtil.getAreasBBox(selSprayZones));

      const hdgResult = await getHeading([].concat.apply([], selItems), selXcls, swath, halfSwathOffset, abLine, heading, refZone, (heading === BST_HDG && selSprayZones.length === 1));
      genHeading = hdgResult.heading;
      masterPoint = hdgResult.masterPoint;

      if (heading === BST_HDG && selSprayZones.length === 1) {
        linesResult.push({ isNew: true, areaId: selItems[0][0].id, lines: hdgResult.lineList, heading: genHeading, masterPoint: masterPoint });
        regenIds.push(selItems[0][0].id);
      } else {
        for (let i = 0; i < selItems.length; i++) {
          sprZones = selItems[i];
          const cloneSprayZones = cloneDeep(sprZones.length > 1 ? [].concat.apply([], sprZones) : sprZones, true);
          genResult = await getLinesUTM(cloneSprayZones, selXcls, swath, halfSwathOffset, masterPoint.x, masterPoint.y, genHeading);
          const newLine = { isNew: true, areaId: sprZones[0].id, lines: genResult.lineList, heading: genHeading, masterPoint: masterPoint };
          const ids = sprZones.map(s => s.id);
          if (ids.length > 1) newLine["mems"] = ids;

          linesResult.push(newLine);
          regenIds = regenIds.concat(ids);
        }
      }
    }

    const restItems = Object.values(restByName);
    let checkResult, areaWLines;
    // Generate lines with best heading for each of for the rest areas if not has lines yet
    for (let i = 0; i < restItems.length; i++) {
      sprZones = restItems[i];
      if (!options.regenerate) {
        checkResult = needRegenLines(sprZones); // TODO: revise this function        
        if (checkResult.value == false) { // no lines changed for the single area => reuse
          areaWLines = checkResult.areaWLines;
          linesResult.push({ isNew: false, areaId: areaWLines._id.toHexString(), heading: areaWLines.heading, lines: areaWLines.lines, mems: areaWLines.mems });
          continue;
        }
      }
      sprZones = await convertAreasCoorstoUTM(restItems[i], ZoneType.NORMAL, refZone);
      // Scan for intersected xcls only for the next step
      selXcls = getOverlapXcls(utmXclZones, geoUtil.getAreasBBox(sprZones));

      masterPoint = sprZones[0].points[0];
      let newLine, rootId = (checkResult && checkResult.areaWLines) ? checkResult.areaWLines._id.toHexString() : sprZones[0].id;
      if (selItems.length || (!selItems.length && heading === BST_HDG)) {
        const hdgResult = await getHeading(sprZones, selXcls, swath, halfSwathOffset, null, BST_HDG, refZone, true);
        newLine = { isNew: true, areaId: rootId, lines: hdgResult.lineList, heading: hdgResult.heading, masterPoint: masterPoint };
      }
      else {
        const hdgResult = await getHeading(sprZones, selXcls, swath, halfSwathOffset, abLine, heading, refZone);
        genHeading = hdgResult.heading;

        let cloneSprayZones = cloneDeep(sprZones, true);
        genResult = await getLinesUTM(cloneSprayZones, selXcls, swath, halfSwathOffset, masterPoint.x, masterPoint.y, genHeading);
        newLine = { isNew: true, areaId: rootId, lines: genResult.lineList, heading: genHeading, masterPoint: masterPoint };
      }
      const ids = sprZones.map(s => s.id);
      if (ids.length > 1) newLine["mems"] = ids;
      linesResult.push(newLine);
      regenIds = regenIds.concat(ids);
    }
  }
  else { /* Generate lines for all areas. Use for export/download job only */
    utmSprayZones = await convertAreasCoorstoUTM(sprayZones, ZoneType.NORMAL, refZone);

    // Get the heading for all areas
    const hdgResult = await getHeading(utmSprayZones, [], swath, halfSwathOffset, abLine, heading, refZone);
    genHeading = hdgResult.heading;
    masterPoint = hdgResult.masterPoint;
    // Generate lines for all areas
    genResult = await getLinesUTM(cloneDeep(utmSprayZones, true), utmXclZones, swath, halfSwathOffset, masterPoint.x, masterPoint.y, genHeading);
    linesResult.push({ isNew: true, areaId: utmSprayZones[0].id, lines: genResult.lineList, heading: genHeading, masterPoint: masterPoint });
  }

  // Convert new lines from Utm to Latlong
  let backUtm = Utm.newInstance(refZone.zone, refZone.hemisphere, 0, 0);
  let latlngHeading = 0, areaLine;
  for (let i = 0; i < linesResult.length; i++) {
    areaLine = linesResult[i];
    if (!areaLine.isNew) continue;

    let xy;
    for (let j = 0; j < areaLine.lines.length; j++) {
      for (let k = 0; k < areaLine.lines[j].breakPoints.length; k++) {
        xy = areaLine.lines[j].breakPoints[k];
        backUtm.easting = xy.x; backUtm.northing = xy.y;
        latlng = backUtm.toLatLon();
        areaLine.lines[j].breakPoints[k] = [latlng.lat, latlng.lon];
      }
      areaLine.lines[j] = areaLine.lines[j].breakPoints;
      delete areaLine.lines[j].breakPoints;
    }
    if (areaLine.lines.length) {
      latlngHeading = utmToLatlonHeading(refZone.zone, refZone.hemisphere, areaLine.masterPoint.x, areaLine.masterPoint.y, areaLine.heading);
      latlngHeading = geoUtil.to360Range(latlngHeading);
      areaLine["latlngHeading"] = utils.fixedTo(latlngHeading, 1);
    }
    else {
      areaLine["latlngHeading"] = 0;
    }

    backUtm.easting = areaLine.masterPoint.x, backUtm.northing = areaLine.masterPoint.y;
    latlng = backUtm.toLatLon();
    areaLine["masterPoint"] = [latlng.lat, latlng.lon];
    // debug(`${areaLine.areaId}, LLHeading: ${areaLine.latlngHeading}°, UTM Heading: ${areaLine.heading}°, Lines: ${areaLine.lines.length}`);
  }

  return ({ lines: linesResult, regenIds: regenIds });
}

function getOverlapXcls(utmXclZones, wBbox) {
  const selXcls = [];
  let zoneBbox;
  for (let i = 0; i < utmXclZones.length; i++) {
    zoneBbox = utmXclZones[i].bbox;
    if (polyUtil.doOverlap({ x: wBbox[0], y: wBbox[3] }, { x: wBbox[2], y: wBbox[1] }, { x: zoneBbox[0], y: zoneBbox[3] }, { x: zoneBbox[2], y: zoneBbox[1] }))
      selXcls.push(utmXclZones[i]);
  }
  return selXcls;
}

async function convertAreasCoorstoUTM(areas, zoneType, refZone) {
  let utmZones = [];

  if (utils.isEmptyArray(areas))
    return utmZones;

  for (let i = 0; i < areas.length; i++) {
    const coors = areas[i].geometry.coordinates[0];
    if (coors.length < 3) continue;

    const convertRes = latlngToUTMCoors(coors, refZone);
    if (!convertRes) AppInputError.throw();

    if (zoneType == ZoneType.NORMAL) {
      const hasLines = !utils.isEmptyArray(areas[i].lines);
      utmZones.push(new Zone(areas[i]._id.toHexString(), areas[i].properties.name, ZoneType.NORMAL, convertRes.utmCoors, hasLines));
    } else {
      utmZones.push(new Zone(areas[i].properties.name, areas[i].properties.name, ZoneType.XCL, convertRes.utmCoors, false));
    }
  }

  return utmZones;
}

/**
 * Check whether the area or group has generated lines or not.
 * @param {*} sprZones LatLon areas
 */
function needRegenLines(sprZones) {
  if (utils.isEmptyArray(sprZones))
    return { value: false };

  const checkResult = { value: false, areaWLines: sprZones[0] };

  if (sprZones.length === 1) {
    checkResult.value = utils.isEmptyArray(sprZones[0].lines);
  } else {
    const rootItems = [];
    const ids = [];

    let areaId;
    for (let i = 0; i < sprZones.length; i++) {
      areaId = sprZones[i]._id.toHexString();
      if (sprZones[i].lines && !utils.isEmptyArray(sprZones[i].mems))
        rootItems.push(sprZones[i]);
      ids.push(areaId);
    }
    if (rootItems.length !== 1) {
      checkResult.value = true;
    } else if (utils.arraysEqual(ids, rootItems[0].mems, true)) {
      checkResult.value = false;
      checkResult.areaWLines = rootItems[0];
    }
  }
  return checkResult;
}

/**
 * Returns the heading for the given zones and parameters. Also return the lines in the case of best heading.
 * @param {*} sprayZones 
 * @param {*} xclZones 
 * @param {number} swath 
 * @param {boolean} halfSwathOffset 
 * @param {*} abLine 
 * @param {number} heading 
 * @param {*} refZone { zone: [zone number], hemisphere: ['N'|'S'] }
 * @param {boolean} returnLines  
 */
async function getHeading(sprayZones, xclZones, swath, halfSwathOffset, abLine, heading, refZone = { zone: undefined, hemisphere: undefined }, returnLines = false) {
  let genHeading = 0, masterPoint, bestHeadingResult, _xclZones = [];

  if (heading === BST_HDG) { // Find Best Heading 
    let longestLineZoneIndex = 0, longestEdgeIndex = 0;
    let longestEdgeLength, edgeLength, longestEdgeHeading;
    let a, b, zone;
    bestHeadingResult = { heading: 0, leftmostPoint: null, lineList: [] };
    _xclZones = cloneDeep(xclZones, 1);

    // Select the zone that has the longest line
    longestEdgeLength = -1;
    for (let i = 0; i < sprayZones.length; i++) {
      zone = sprayZones[i];
      for (let j = 0; j < zone.points.length; j++) {
        a = zone.points[j];
        b = (j === (zone.points.length - 1)) ? zone.points[0] : zone.points[j + 1];
        edgeLength = mathUtil.segmentLengthP(a, b);
        if (edgeLength > longestEdgeLength) {
          longestEdgeLength = edgeLength;
          longestLineZoneIndex = i;
          longestEdgeIndex = j;
        }
      }
    }

    // Find the heading on the selected zone that produces minimum number of lines
    zone = sprayZones[longestLineZoneIndex];
    a = zone.points[longestEdgeIndex];
    b = (longestEdgeIndex === (zone.points.length - 1)) ? zone.points[0] : zone.points[(longestEdgeIndex + 1)];
    longestEdgeHeading = geoUtil.utmBearing(a.x, a.y, b.x, b.y);

    let minNumLines = Number.MAX_SAFE_INTEGER + 1, scanHeading;
    for (let alpha = 0; alpha <= 180; alpha += BEST_HEADING_INC) {
      scanHeading = longestEdgeHeading + alpha;
      if (scanHeading > 360)
        scanHeading = scanHeading - 360;

      let cloneUtmSprayZones = cloneDeep(sprayZones, true);
      let cloneXclZones = !utils.isEmptyArray(_xclZones) ? cloneDeep(_xclZones, true) : [];
      let result = await getLinesUTM(cloneUtmSprayZones, cloneXclZones, swath, halfSwathOffset, cloneUtmSprayZones[0].points[0].x, cloneUtmSprayZones[0].points[0].y, scanHeading);
      // console.log("BHeading: ", Math.trunc(scanHeading), "Lines: ", result.lineList.length);
      if (result.lineList.length > 0 && result.lineList.length < minNumLines) {
        bestHeadingResult.heading = scanHeading;
        bestHeadingResult.leftmostPoint = result.leftmostPoint;
        if (returnLines)
          bestHeadingResult.lineList = result.lineList;
        minNumLines = result.lineList.length;
      }
    }
    masterPoint = bestHeadingResult.leftmostPoint;
  }
  else {
    if (abLine) {
      let utmA, utmB;
      const aSP = new LatLonSP(abLine.a.lat, abLine.a.lng);
      const bSP = new LatLonSP(abLine.b.lat, abLine.b.lng);
      const midSP = aSP.midpointTo(bSP);
      const llHeading = aSP.finalBearingTo(bSP);

      // Use the same method in Guia, Guia Pt to have the same Heading (not the direct heading caculation from  AB)
      const a = midSP.destinationPoint(-500, llHeading);
      const b = midSP.destinationPoint(500, llHeading);
      utmA = new LatLonUTM(a.lat, a.lng).toUtm(refZone.zone, refZone.hemisphere);
      utmB = new LatLonUTM(b.lat, b.lng).toUtm(refZone.zone, refZone.hemisphere);

      heading = geoUtil.utmBearing(utmA.easting, utmA.northing, utmB.easting, utmB.northing);

      // Requirement: If using AB Line method, the Masterpoint must be the midpoint
      const midPUtm = new LatLonUTM(midSP.lat, midSP.lon).toUtm(refZone.zone, refZone.hemisphere);
      masterPoint = { x: midPUtm.easting, y: midPUtm.northing };
    }
    else {
      masterPoint = sprayZones[0].points[0];
    }
  }
  genHeading = utils.fixedTo((bestHeadingResult ? bestHeadingResult.heading : heading), 1);

  return { heading: genHeading, masterPoint: masterPoint, lineList: bestHeadingResult ? bestHeadingResult.lineList : [] };
}

/**
 * Generate grid lines given zones in UTM coordinates.
 * @param {*} sprayZones 
 * @param {*} xclZones 
 * @param {*} halfSwathOffset whether to offset guide lines half swath inside area
 * @param {*} x UTM coordinate of the master point x
 * @param {*} y UTM coordinate of the master point y
 * @param {*} heading heading of the guide lines
 */
async function getLinesUTM(sprayZones, xclZones, swath, halfSwathOffset, x, y, heading) {
  let result = { leftmostPoint: null, lineList: [] };
  let _xclZones = cloneDeep(xclZones, 1);
  /* Double check to ensure the MasterPoint is valid
   * if it is invalid, correct it as the 1st corner of the first sprayzone
   */
  let lineList = [];
  let zoneList = utils.appendArray(sprayZones, _xclZones);
  let bounds = new Bound();
  for (let i = 0; i < zoneList.length; i++)
    bounds.updateR(zoneList[i].bounds);

  if (!bounds.contains(x, y) && mathUtil.segmentLength(bounds.center().x, bounds.center().y, x, y) > (1000 * halfSwathOffset)) {
    x = sprayZones[0].points[0].x;
    y = sprayZones[0].points[0].y;
  }
  // console.log(bounds.center());

  // Check minimum swath width
  swath = Math.max(MIN_SWATH_WIDTH, swath);

  const transform1 = halfSwathOffset ?
    transform(
      translate(-swath / 2, 0),
      rotateDEG(heading),
      translate(-x, -y),
    )
    : transform(
      rotateDEG(heading),
      translate(-x, -y),
    );

  const transform2 = inverse(transform1);

  // Transform all zones to make use in next steps
  for (let i = 0; i < zoneList.length; i++) {
    zoneList[i].points = applyToPoints(transform1, zoneList[i].points);
    zoneList[i].updateBounds();
  }

  // *** All steps below assume the polygons are already transformed ***
  // find the leftmost point
  let leftmostPoint;
  for (let i = 0; i < sprayZones.length; i++) {
    let zone = sprayZones[i];
    for (let j = 0; j < zone.points.length; j++) {
      if (!leftmostPoint)
        leftmostPoint = zone.points[j];
      else {
        if (zone.points[j].x < leftmostPoint.x)
          leftmostPoint = zone.points[j];
      }
    }
  }

  // compute jump points    
  let linesWithJumpPoints = findJumpPoints(halfSwathOffset, swath, zoneList);

  if (linesWithJumpPoints.length > 0) {
    // compute break points
    let line, ok = false, m;
    for (let i = 0; i < linesWithJumpPoints.length; i++) {
      line = findBreakPoints(linesWithJumpPoints[i]);
      ok = (line.breakPoints.length && line.breakPoints.length % 2 === 0);
      // if (line.breakPoints.length === 2)  // Single segment: only take one with length >= MIN_SEGMENT_LENGTH
      //   ok = (mathUtil.segmentLengthP(line.breakPoints[0], line.breakPoints[1]) >= MIN_SEGMENT_LENGTH);
      if (ok) {
        m = line.breakPoints.length - 1;
        while (m >= 1) {  // remove any too short segment
          if (mathUtil.segmentLengthP(line.breakPoints[m - 1], line.breakPoints[m]) < MIN_SEGMENT_LENGTH) {
            line.breakPoints.splice(m - 1, 2);
          }
          m -= 2;
        }
        // Transform break points back to original coordinate system
        if (line.breakPoints.length) {
          line.breakPoints = applyToPoints(transform2, line.breakPoints);
          lineList.push(line);
        }
      }
    }
  }

  if (leftmostPoint)
    result.leftmostPoint = applyToPoint(transform2, leftmostPoint);
  result.lineList = lineList;

  return result;
}

/**
 * Compute the jump points used to find break points forming grid lines
 * @param {*} swath the swathwidth between scan lines
 * @param {*} zoneList list of zone polygons to find jump points
 * @note The polygons must be transformed North-up and translated to the origin.  
 */
function findJumpPoints(halfSwathOffset, swath, zoneList) {
  let nlines, zone;
  let lineList = [], scanLines = [];

  let wholeRect = new Bound();
  for (let i = 0; i < zoneList.length; i++) {
    // Scan within sprayzones bounding ensure correct first line position in the case with xcls overlapped from out to inside from the scanning side    
    if (zoneList[i].type === ZoneType.NORMAL)
      wholeRect.updateR(zoneList[i].bounds);
  }

  let xMin = wholeRect.xmin, xMax = wholeRect.xmax;
  let curX = xMin;
  curX += halfSwathOffset ? swath / 2 : 0;
  scanLines.push({ x: curX, y: 0 });
  do {
    curX += swath;
    scanLines.push({ x: curX, y: 0 });
  }
  while (curX <= xMax - swath);

  // Now in scanLines are the x coordinates of the vertical scan lines,
  // calculate the intersection points of the above lines with zone polygons.
  nlines = scanLines.length;

  for (let i = 0; i < nlines; i++) {
    let p1 = { x: 0, y: 0 }, p2 = { x: 0, y: 0 };
    let line = {
      intersectSprayZones: [],
      intersectXclZones: [],
      breakPoints: []
    };

    for (let j = 0; j < zoneList.length; j++) {
      zone = zoneList[j];
      if (zone.points.length < 3) continue;

      let hasIntersectPoint = false;
      xMin = zone.bounds.xmin;
      xMax = zone.bounds.xmax;

      // TODO: May use Active Edge and Edge Table for further performance improvement with large and multiple areas
      let v = { x: scanLines[i].x, y: 0 };
      if (xMin <= v.x && v.x <= xMax) {
        for (let m = 0, n = 1; m < zone.points.length; m++, n++) {
          if (n === zone.points.length)
            n = 0;

          p1 = zone.points[m];
          p2 = zone.points[n];

          if (Math.abs(p1.x - p2.x) < 1e-4) { // vertical edge => skip because no intersect with vertical scan lines                        
          }
          else {  // if oblic edge
            if ((p1.x - v.x) * (p2.x - v.x) < 1e-4) {  // if cross the edge              
              v.y = p1.y + (p2.y - p1.y) * (v.x - p1.x) / (p2.x - p1.x);
              const newPoint = { x: v.x, y: v.y, type: zone.type === ZoneType.NORMAL ? 0 : 1 };
              line.breakPoints.push(newPoint);
              hasIntersectPoint = true;
            }
          }
        }
      }

      if (hasIntersectPoint) {
        if (zone.type === ZoneType.NORMAL)
          line.intersectSprayZones.push(zone);
        else
          line.intersectXclZones.push(zone);
      }
    }

    if (line.breakPoints.length)
      lineList.push(line);
  }

  // For each intersect point, we generate 2 jump points 0.1m up and down from the intersect point.
  // The jump points will be used to determine break points later.
  for (let i = 0; i < lineList.length; i++) {
    let jumpPoints = [];
    for (let j = 0; j < lineList[i].breakPoints.length; j++) {
      let v = lineList[i].breakPoints[j];
      let vDown = { x: v.x, y: v.y - 0.1, type: v.type };
      jumpPoints.push(vDown);
      let vUp = { x: v.x, y: v.y + 0.1, type: v.type };
      jumpPoints.push(vUp);
    }

    // Sort (use Bubble Sort) the jump points by y (ascending)
    let n = jumpPoints.length;
    mathUtil.bubbleSort(jumpPoints, n);

    if (jumpPoints.length > 1) {
      lineList[i].breakPoints = jumpPoints;
    }
  }

  return lineList;
}

/**
 * Find the break points of a line based on jump points
 * @param {*} line list if lines with jump points
 * @return a line containing calculated break points
 */
function findBreakPoints(line) {
  let breakPoints = [];
  let line2 = {
    breakPoints: [],
  };

  let findInside = true; // start with finding the first entry point

  for (let i = 0; i < line.breakPoints.length; i++) {
    const jumpPoint = line.breakPoints[i];
    let insideArea = checkPointInZone(jumpPoint.x, jumpPoint.y, ZoneType.NORMAL, line.intersectSprayZones);

    if (insideArea) {
      if (line.intersectXclZones.length > 0 && checkPointInZone(jumpPoint.x, jumpPoint.y, ZoneType.XCL, line.intersectXclZones))
        insideArea = false;
    }

    if (insideArea === findInside) { // found a break point
      breakPoints.push(jumpPoint);
      findInside = !findInside;   // if an entry point found, the next break point must be an exit point and vice versa
    }
  }

  // Number of break points must be even.
  // If it is odd, the last point should be removed.
  if ((breakPoints.length > 0) && (breakPoints.length % 2))
    breakPoints.splice(-1, 1);  //remove last item

  line2.breakPoints = breakPoints;

  // Single segment: only take one with length >= MIN_SEGMENT_LENGTH
  if (line.breakPoints.length === 2) {
    if (mathUtil.segmentLengthP(line.breakPoints[0], line.breakPoints[1]) < MIN_SEGMENT_LENGTH)
      line2.breakPoints = [];
  }

  return line2;
}

/**
 * Check if the given point is inside a zone of current area
 * @param {*} zoneType type of zone (normal or exclusion)
 * @param {*} zoneList list of zones to check 
 * @return true if inside zone
 */
function checkPointInZone(x, y, zoneType, zoneList) {
  for (let i = 0; i < zoneList.length; i++) {
    let zone = zoneList[i];
    if (zone && (zone.type === zoneType)) {
      if (geoUtil.pointInOrOnPolygon(zone.points, x, y))
        return true;
    }
  }
  return false;
}

/*
 * Convert Lat/Lon heading to UTM heading 
 * @param {*} lat 
 * @param {*} lon 
 * @param {*} ll_heading Lat/Lon heading to convert

function latlonToUtmHeading (lat, lon, ll_heading) {
  let utm_heading = ll_heading;
  let dradius = 0.01; // degree ~= 1000 meters
  let utm_x1, utm_y1, utm_x2, utm_y2;

  const head = ll_heading * deg2rad;
  const lon1 = lon - Math.sin(head) * dradius;
  const lat1 = lat - Math.cos(head) * dradius;
  const lon2 = lon + Math.sin(head) * dradius;
  const lat2 = lat + Math.cos(head) * dradius;

  let latlng = new LatLon(lat1, lon1), utm;
  utm = latlng.toUtm();
  utm_x1 = utm.easting, utm_y1 = utm.northing;
  latlng.lat = lat2, latlng.lon = lon2;
  utm = latlng.toUtm();
  utm_x2 = utm.easting, utm_y2 = utm.northing;

  utm_heading = Math.atan2(utm_x2 - utm_x1, utm_y2 - utm_y1) * rad2deg;

  return utm_heading;
}
 */

/**
 * Convert UTM heading to Lat/Lon heading
 * @param {*} zone UTM zone number
 * @param {*} hemisphere 1: North hemisphere, 2: South hemisphere
 * @param {*} utm_x 
 * @param {*} utm_y 
 * @param {*} utm_heading UTM heading to convert
 */
function utmToLatlonHeading(zone, hemisphere, utm_x, utm_y, utm_heading) {
  let ll_heading = utm_heading;
  let lon1, lat1, lon2, lat2, utm_x1, utm_y1, utm_x2, utm_y2, head;
  let dradius = 500;  // 500 meters

  head = utm_heading * deg2rad;
  utm_x1 = utm_x - Math.sin(head) * dradius;
  utm_y1 = utm_y - Math.cos(head) * dradius;
  utm_x2 = utm_x + Math.sin(head) * dradius;
  utm_y2 = utm_y + Math.cos(head) * dradius;

  let utm = Utm.newInstance(zone, hemisphere, 0, 0);
  utm.easting = utm_x1, utm.northing = utm_y1;
  let latlng = utm.toLatLon();
  lat1 = latlng.lat, lon1 = latlng.lon;
  utm.easting = utm_x2, utm.northing = utm_y2;
  latlng = utm.toLatLon();
  lat2 = latlng.lat, lon2 = latlng.lon;

  ll_heading = Math.atan2(lon2 - lon1, lat2 - lat1) * rad2deg;

  return ll_heading;
}

module.exports = {
  getLinesLatLng, BST_HDG
}