package nxm.sys.libg;

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Arrays;

import nxm.sys.inc.InternalUseOnly;
import nxm.sys.lib.Position;
import nxm.sys.libg.IntersectingLine.Corner;
import nxm.sys.libg.IntersectingLine.IntersectLocation;
import nxm.sys.libm.Tolerance;

/** A class for static geometric utility methods<br>
 *  Initial methods are related to getting the intersect of a polygon with a
 *  rectangle
 *
 *  @author Jeanette McCall
 *  @since NeXtMidas 3.9.1
 *
 */
public class GeometricUtil {

  /** margin around view box for points added to form enclosed shape, to make sure
      outer edges are not visible */
  @InternalUseOnly
  public static int DEFAULT_MARGIN = 10;
  private static int viewBoxMargin = DEFAULT_MARGIN;

  /** This constructor was automatically provided by Java,
   *  but it is unneeded as all the methods are static methods.
   *  @deprecated now that Javadocs are required, it is temporarily
   *              being explicitely provided but deprecated
   */
  @Deprecated
  public GeometricUtil () {}

  /** Forms the line segment groups that represent the polygon's traversal
   *  across the view area.
   *
   *  @param polyXCords x coordinates of polygon
   *  @param polyYCords y coordinates of polygon
   *  @param npts       number of valid polygon points
   *  @param off        starting offset into polygon buffer
   *  @param rectangle  view box
   *  @return line segment groups that represent the polygon's traversal
   *  across the view area.
   */
  @InternalUseOnly
  public static LineSegmentGroup[] polygonRectangleIntersect (double[] polyXCords, double[] polyYCords, int npts, int off,
      Rectangle2D.Double rectangle) {
    LineSegmentGroup[] intersectShapes = null;

    //*************************************************************************************
    //    Quick checks before trying to form a shape
    //*************************************************************************************

    // check if bounding box of polygon overlaps rectangle
    // if there is no overlap, then there are no intersect shapes
    Rectangle2D.Double polygonBoundingBox = calculateBounds(polyXCords,polyYCords,npts,off);
    boolean potentialOverlap = polygonBoundingBox.intersects(rectangle);
    if (!potentialOverlap) return intersectShapes;

    // if just one point just see if it is contained
    if ((npts == 1) && rectangle.contains(polyXCords[off], polyXCords[off])) {
      return new LineSegmentGroup[] {new LineSegmentGroup(new int[] {(int) polyXCords[off]}, new int[] {(int) polyYCords[off]}, IntersectLocation.ENCLOSED, IntersectLocation.ENCLOSED)};
    }

    //*************************************************************************************
    //    Form any intersect shapes
    //*************************************************************************************

    // This is an ArrayList<ArrayList> so multiple connecting segments can be held as 1 group
    ArrayList<ArrayList<Integer>> xPixels = new ArrayList<>();
    ArrayList<ArrayList<Integer>> yPixels = new ArrayList<>();
    ArrayList<IntersectLocation> entries = new ArrayList<>();
    ArrayList<IntersectLocation> exits = new ArrayList<>();


    IntersectingLine visibleSegment = null;
    Line2D.Double originalSegment = null;
    int lineSegmentGrp = 0;
    int maxIndex = Math.min(off + npts, Math.min(polyXCords.length, polyYCords.length)) - 1;
    int lastIndex = maxIndex;
    boolean startNewSegmentGroup = true;
    int x2LastVisSegment = 0;
    int y2LastVisSegment = 0;
    boolean haveLastVisSegment = false;
    boolean lastPointWasEnclosed = false;
    Point2D.Double visibleBoxMinXY = new Point2D.Double(rectangle.getX(), rectangle.getY());
    Point2D.Double visibleBoxMaxXY = new Point2D.Double(rectangle.getX()+rectangle.width, rectangle.getY()+rectangle.getHeight());
    //** Handle special case where first polygon point is contained in the rectangle **
    if (rectangle.contains(polyXCords[off], polyYCords[off])) {
      // need to connect this backwards until go out of range of visible area
      xPixels.add(new ArrayList<>());
      yPixels.add(new ArrayList<>());
      startNewSegmentGroup = false; // we have started this group
      lastPointWasEnclosed = true;  // the point at "off" is the "last" pt and it is contained in the view area
      if (Tolerance.equalsWithTolerance(polyXCords[off], polyXCords[lastIndex ], 1e-15)  &&
          Tolerance.equalsWithTolerance(polyYCords[off], polyYCords[lastIndex ], 1e-15)) {
        lastIndex --;
      }
      while (rectangle.contains(polyXCords[lastIndex ], polyYCords[lastIndex ]) && (lastIndex  > off)) {
        // add all visible points connected to the first point
        xPixels.get(lineSegmentGrp).add(0, (int)polyXCords[lastIndex ]);
        yPixels.get(lineSegmentGrp).add(0, (int)polyYCords[lastIndex ]);
        lastIndex --;
      }
      // grab one more to get the line segment that leaves the visible area
      if (lastIndex  > off) {
        // need either visible segment of off point and maxIndex point (no other interior points found)
        // x[max], y[max], x[off], y[off]
        if (lastIndex == maxIndex) {
          // no other interior point found going backwards through points
          // so, connect last point with first point and find visible segment
          originalSegment = new Line2D.Double(polyXCords[maxIndex], polyYCords[maxIndex], polyXCords[off], polyYCords[off]);
        }
        else {
          // Otherwise, we need to connect the point to which lastIndex is now pointing to
          // the last point we found that was in the visible range
          originalSegment = new Line2D.Double(polyXCords[lastIndex], polyYCords[lastIndex],
              polyXCords[lastIndex+1], polyYCords[lastIndex+1]);
        }
        // get the visible portion of this line segment that goes beyond the view bounds
        visibleSegment = adjustToVisibleLine(originalSegment, visibleBoxMinXY, visibleBoxMaxXY);
        // add the first point in the line segment - the other was in the visible range and already added
        xPixels.get(lineSegmentGrp).add(0,(int)visibleSegment.line.x1);
        yPixels.get(lineSegmentGrp).add(0,(int)visibleSegment.line.y1);
        entries.add(visibleSegment.locations[0]);
      }
    }

    //** check each new line segment (line between new point and last point)
    for (int i = off; i < lastIndex; i++) {
      // add first point of each visible line segment and save off second point
      // (the second point will be added either because it is also the starting point of a
      // follow-on line segment or at the end of no follow-on line segments are found)
      originalSegment = new Line2D.Double(polyXCords[i], polyYCords[i], polyXCords[i+1], polyYCords[i+1]);
      visibleSegment = adjustToVisibleLine(originalSegment, visibleBoxMinXY, visibleBoxMaxXY);

      if (visibleSegment !=null) {
        // we have found a visible line segment
        // if needed start a new line segment group
        // add the first point in the line segment and save the second point
        if (startNewSegmentGroup) {
          xPixels.add(new ArrayList<>());
          yPixels.add(new ArrayList<>());
          entries.add(visibleSegment.locations[0]);
          startNewSegmentGroup = false;
        }
        xPixels.get(lineSegmentGrp).add((int)visibleSegment.line.x1);
        yPixels.get(lineSegmentGrp).add((int)visibleSegment.line.y1);
        x2LastVisSegment = (int)visibleSegment.line.x2;
        y2LastVisSegment = (int)visibleSegment.line.y2;
        haveLastVisSegment = true;
        lastPointWasEnclosed = visibleSegment.getLocations()[1] == IntersectLocation.ENCLOSED;
      }
      if (!startNewSegmentGroup && haveLastVisSegment && !lastPointWasEnclosed) {
        // we have just completed a line segment group
        xPixels.get(lineSegmentGrp).add(x2LastVisSegment);
        yPixels.get(lineSegmentGrp).add(y2LastVisSegment);
        exits.add(visibleSegment.locations[1]);
        lineSegmentGrp++;
        startNewSegmentGroup = true;
      }
    }

    // Convert visible segment groups ArrayLists to int arrays, if we found visible line segments
    LineSegmentGroup[] lineSegmentGroups = null;
    if (xPixels.size() > 0) {
      lineSegmentGroups = new LineSegmentGroup[xPixels.size()];
      for (int pixGrp = 0; pixGrp < xPixels.size(); pixGrp++) {
        ArrayList<Integer> xPixGrp = xPixels.get(pixGrp);
        ArrayList<Integer> yPixGrp = yPixels.get(pixGrp);
        lineSegmentGroups[pixGrp] = new LineSegmentGroup(xPixels.get(pixGrp).size(), yPixels.get(pixGrp).size());
        for (int i = 0; i < lineSegmentGroups[pixGrp].xcoords.length; i++) {
          lineSegmentGroups[pixGrp].xcoords[i] = xPixGrp.get(i);
          lineSegmentGroups[pixGrp].ycoords[i] = yPixGrp.get(i);
          lineSegmentGroups[pixGrp].entry= entries.get(pixGrp);
          lineSegmentGroups[pixGrp].exit = exits.get(pixGrp);
        }
      }
    }

    return lineSegmentGroups;
  }

  /** For case where there were no intersecting lines of the polygon across the view
   *  area, tests if the view are is completely enclosed in the polygon or completely
   *  outside of the polygon
   *
   *  @param polyXCords x coordinates of polygon
   *  @param polyYCords y coordinates of polygon
   *  @param npts       number of valid points in polygon arrays
   *  @param off        offset of first valid point in polygon array
   *  @param rectangle  view box rectangle
   *  @return either null if view area not enclosed or 1 line segment group representing view area
   */
  @InternalUseOnly
  public static LineSegmentGroup[] allOrNone (double[] polyXCords, double[] polyYCords, int npts, int off,
      Rectangle2D.Double rectangle) {

    LineSegmentGroup[] lineSegmentGroups = null;
    if (insidePolygon(rectangle.getX(), rectangle.getY(), polyXCords, polyYCords, npts, off)) {
      lineSegmentGroups = new LineSegmentGroup[1];
      LineSegmentGroup lsg = new LineSegmentGroup(5, 5);

      int xMin = (int)(rectangle.getX() - viewBoxMargin);
      int yMin = (int)(rectangle.getY() - viewBoxMargin);
      int xMax = (int)(rectangle.getX() + rectangle.getWidth() + viewBoxMargin);
      int yMax = (int)(rectangle.getY() + rectangle.getHeight() + viewBoxMargin);

      // lower left
      lsg.xcoords[0] = xMin;
      lsg.ycoords[0] = yMin;
      // top left
      lsg.xcoords[1] = xMin;
      lsg.ycoords[1] = yMax;
      // top right
      lsg.xcoords[2] = xMax;
      lsg.ycoords[2] = yMax;
      // lower right
      lsg.xcoords[3] = xMax;
      lsg.ycoords[3] = yMin;
      // lower left - back to the first point to close the shape
      lsg.xcoords[4] = xMin;
      lsg.ycoords[4] = yMin;

      lineSegmentGroups[0] = lsg;
    }

    return lineSegmentGroups;

  }

  /** Get the visible portion of the line along with information on its intersection
   *  with the bounding 2D box representing the visible area<br>
   *  Note: This is used so that lines to be drawn can be represented as pixels that
   *  are within the range of int values (i.e. do not saturate)
   *
   *  @param line            original line
   *  @param visibleBoxMinXY visible box min coordinates
   *  @param visibleBoxMaxXY visible box max coordinates
   *  @return intersecting line
   *  @since NeXtMidas 3.9.1 for NXM-3131
   */
  static IntersectingLine adjustToVisibleLine (Line2D.Double line, Point2D visibleBoxMinXY, Point2D visibleBoxMaxXY){
    if (!(Double.isFinite(line.x1) && Double.isFinite(line.x2) && Double.isFinite(line.y1) && Double.isFinite(line.y2))) {
      return null;
    }
    IntersectingLine visibleLine = null;
    Point2D.Double    firstIntersect     = null;
    Point2D.Double    secondIntersect    = null;
    IntersectLocation firstIntersectLoc  = null;
    IntersectLocation secondIntersectLoc = null;

    double visibleX1 = visibleBoxMinXY.getX();
    double visibleY1 = visibleBoxMinXY.getY();
    double visibleX2 = visibleBoxMaxXY.getX();
    double visibleY2 = visibleBoxMaxXY.getY();


    // Check if all of line is outside bounding box (viewable area)
    if ((line.getX2() < visibleX1) && (line.getX1() < visibleX1)) return visibleLine;
    if ((line.getX2() > visibleX2) && (line.getX1() > visibleX2)) return visibleLine;
    if ((line.getY2() < visibleY1) && (line.getY1() < visibleY1)) return visibleLine;
    if ((line.getY2() > visibleY2) && (line.getY1() > visibleY2)) return visibleLine;

    // check if a line endpoint is within bounding box
    // check endpoint lineFirstPos
    if ((line.getX1() > visibleX1) && (line.getX1() < visibleX2) &&
        (line.getY1() > visibleY1) && (line.getY1() < visibleY2)) {
       firstIntersect = new Point2D.Double(line.getX1(), line.getY1());
       firstIntersectLoc = IntersectLocation.ENCLOSED;
    }
    if ((line.getX2() > visibleX1) && (line.getX2() < visibleX2) &&
        (line.getY2() > visibleY1) && (line.getY2() < visibleY2)) {
      secondIntersect = new Point2D.Double(line.getX2(), line.getY2());
      secondIntersectLoc = IntersectLocation.ENCLOSED;
      if (firstIntersect != null)  return new IntersectingLine(
          firstIntersect, firstIntersectLoc, secondIntersect, secondIntersectLoc);
    }

    //********************************************************************
    // Get any intersections with the bounding box
    //********************************************************************
    Point2D.Double possibleIntersect;
    double xAxisDistanceLinePt1ToBoxBoundary;
    double xAxisDistanceLinePt2ToBoxBoundary;
    double yAxisDistanceLinePt1ToBoxBoundary;
    double yAxisDistanceLinePt2ToBoxBoundary;

    // *** check for intersections along box position 2 2 axes ***

    // Check for y intersect along Box xMin axis
    xAxisDistanceLinePt1ToBoxBoundary = line.getX1() - visibleX1; // distance to Box min x
    xAxisDistanceLinePt2ToBoxBoundary = line.getX2() - visibleX1; // distance to Box min x
    possibleIntersect = getIntersectionBD(line, xAxisDistanceLinePt1ToBoxBoundary, xAxisDistanceLinePt2ToBoxBoundary);
    // check if possible y intersect is within range of box y bounds
    if ((possibleIntersect != null) && ((possibleIntersect.y >= visibleBoxMinXY.getY()) &&
        (possibleIntersect.y <= visibleBoxMaxXY.getY()))) {
      if ((secondIntersect != null) || ((firstIntersect == null) & (xAxisDistanceLinePt1ToBoxBoundary >= 0))) {
        firstIntersect = possibleIntersect;
        firstIntersectLoc = IntersectLocation.X1_BORDER;
      }
      else {
        secondIntersect = possibleIntersect;
        secondIntersectLoc = IntersectLocation.X1_BORDER;
      }
      if ((firstIntersect != null) && (secondIntersect != null)) {
        return new IntersectingLine(firstIntersect, firstIntersectLoc, secondIntersect, secondIntersectLoc);
      }
    }

    // Check for x intersect along Box yMin axis
    yAxisDistanceLinePt1ToBoxBoundary = line.getY1() - visibleY1; // distance to Box min y
    yAxisDistanceLinePt2ToBoxBoundary = line.getY2() - visibleY1; // distance to Box min Y
    possibleIntersect = getIntersectionBD(line, yAxisDistanceLinePt1ToBoxBoundary, yAxisDistanceLinePt2ToBoxBoundary);
    // check if possible x intersect is within range of box x bounds
    if ((possibleIntersect != null) && ((possibleIntersect.x >= visibleBoxMinXY.getX()) &&
        (possibleIntersect.x <= visibleBoxMaxXY.getX()))) {
      if ((secondIntersect != null) || ((firstIntersect == null) & (yAxisDistanceLinePt1ToBoxBoundary >= 0))) {
        firstIntersect = possibleIntersect;
        firstIntersectLoc = IntersectLocation.Y1_BORDER;
      }
      else {
        secondIntersect = possibleIntersect;
        secondIntersectLoc = IntersectLocation.Y1_BORDER;
      }
      if ((firstIntersect != null) && (secondIntersect != null)) {
        return new IntersectingLine(firstIntersect, firstIntersectLoc, secondIntersect, secondIntersectLoc);
      }
    }


    // check for intersections along box position 2 2 axes

    //Check for y intersect along Box xMax axis
    xAxisDistanceLinePt1ToBoxBoundary = line.getX1() - visibleX2; // distance to Box max x
    xAxisDistanceLinePt2ToBoxBoundary = line.getX2() - visibleX2; // distance to Box max x
    possibleIntersect = getIntersectionBD(line, xAxisDistanceLinePt1ToBoxBoundary, xAxisDistanceLinePt2ToBoxBoundary);
    // check if possible y intersect is within range of box y bounds
    if ((possibleIntersect != null) && ((possibleIntersect.y >= visibleBoxMinXY.getY()) &&
        (possibleIntersect.y <= visibleBoxMaxXY.getY()))) {
      if ((secondIntersect != null) || ((firstIntersect == null) & (xAxisDistanceLinePt1ToBoxBoundary <= 0))) {
        firstIntersect = possibleIntersect;
        firstIntersectLoc = IntersectLocation.X2_BORDER;
      }
      else {
        secondIntersect = possibleIntersect;
        secondIntersectLoc = IntersectLocation.X2_BORDER;
      }
      if ((firstIntersect != null) && (secondIntersect != null)) {
        return new IntersectingLine(firstIntersect, firstIntersectLoc, secondIntersect, secondIntersectLoc);
      }
    }
    // if we do not have both visible endpoints check y
    possibleIntersect = getIntersectionBD(line, line.getY1() - visibleY2, line.getY2() - visibleY2);
    // check if possible x intersect is within range of box x bounds
    if ((possibleIntersect != null) && ((possibleIntersect.x >= visibleBoxMinXY.getX()) &&
        (possibleIntersect.x <= visibleBoxMaxXY.getX()))) {
      if ((secondIntersect != null) || ((firstIntersect == null) & (yAxisDistanceLinePt1ToBoxBoundary <= 0))) {
        firstIntersect = possibleIntersect;
        firstIntersectLoc = IntersectLocation.Y2_BORDER;
      }
      else {
        secondIntersect = possibleIntersect;
        secondIntersectLoc = IntersectLocation.Y2_BORDER;
      }
      if ((firstIntersect != null) && (secondIntersect != null)) {
        return new IntersectingLine(firstIntersect, firstIntersectLoc, secondIntersect, secondIntersectLoc);
      }
    }

    return visibleLine;
  }

  /** Gets a potential intersection coordinate between the given line and one axis of the
   *  viewing box
   *
   *  @param line 2D line that might intersect or even be fully contained within the specified box
   *  @param axisDistanceLinePt1ToBoxBoundary distance along axis from 1st line point to box line being checked
   *  @param axisDistanceLinePt2ToBoxBoundary distance along axis from 2nd line point to box line being checked
   *  @return potential intersection with box bounding line
   */
  private static Point2D.Double getIntersectionBD (Line2D.Double line, double axisDistanceLinePt1ToBoxBoundary,
      double axisDistanceLinePt2ToBoxBoundary) {
    // if the line is totally to one side of the box line being evaluated => no intersection
    if ((axisDistanceLinePt1ToBoxBoundary * axisDistanceLinePt2ToBoxBoundary) >= 0.0f) return null;
    // if the line is parallel to the box line being evaluated => no intersection
    if (axisDistanceLinePt1ToBoxBoundary == axisDistanceLinePt2ToBoxBoundary) return null;

    // Get the 2D distance line point 1 to line point 2
    BigDecimal lineX1BD = new BigDecimal(line.x1);
    BigDecimal lineY1BD = new BigDecimal(line.y1);
    BigDecimal p2MinusP1XBD = new BigDecimal(line.x2).subtract(lineX1BD);
    BigDecimal p2MinusP1YBD = new BigDecimal(line.y2).subtract(lineY1BD);

    // Get the ratio (line point 1 to intersect) / (line point 1 to line point 2)
    // Note: This equation is a little confusing because the divisor has parts that cancel out
    MathContext mc = new MathContext(64, RoundingMode.HALF_UP);
    BigDecimal mutFactorBD = new BigDecimal(-axisDistanceLinePt1ToBoxBoundary).
        divide(new BigDecimal(axisDistanceLinePt2ToBoxBoundary - axisDistanceLinePt1ToBoxBoundary),mc);

    // get the 2D distance the potential intersect is from line point 1
    BigDecimal distIntersectFromP1XBD = mutFactorBD.multiply(p2MinusP1XBD);
    BigDecimal distIntersectFromP1YBD = mutFactorBD.multiply(p2MinusP1YBD);

    // get the potential intersect location by adding this 2D distance to line point 1
    double intersectX = lineX1BD.add(distIntersectFromP1XBD).doubleValue();
    double intersectY = lineY1BD.add(distIntersectFromP1YBD).doubleValue();
    return new Point2D.Double(intersectX, intersectY);
  }

  /** "Connect the viewable dots" (i.e. line segment points) to form an enclosed shape,
   *  to facilitate the shading of the appropriate visible area<br>
   *  The first visible x,y pair should be the point at which this line enters the view<br>
   *  The last visible x,y pair should be the point at which this line exits the view<br>
   *  Intermediate x,y pairs should be points within the view area
   *
   *  @param visibleX      set of x coordinates representing connected line segments (min size of 2)
   *  @param visibleY      set of y coordinates representing connected line segments (min size of 2)
   *  @param firstIntersectLoc  view box boundary of entry
   *  @param secondIntersectLoc view box boundary of exit
   *  @param viewBox       view box
   *  @param fullPolygonX  full original polygon x coordinates
   *  @param fullPolygonY  full original polygon y coordinates
   *  @param npts          number of valid polygon points
   *  @param off           offset of first valid polygon point
   *  @return integer array containing connected x/y point arrays
   */
  @InternalUseOnly
  public static int[][] connectTheDots (int[] visibleX, int[] visibleY,
      IntersectLocation firstIntersectLoc,IntersectLocation secondIntersectLoc,
      Rectangle2D.Double viewBox,
      double[] fullPolygonX, double[] fullPolygonY, int npts, int off) {

    if(firstIntersectLoc==secondIntersectLoc && firstIntersectLoc==null) {
      // either we are completely enclosed in a shape to be filled or we did something wrong here
      return formVisibleShape(visibleX, visibleY, null,viewBox);
    }
    // get full polygon points in form needed by GeodeticUtil.insidePolygon
    double[] xyPolygon = new double[npts*2];
    int xIdx = 0;
    for (int i = 0; i < npts; i++) {
      xyPolygon[xIdx]   = fullPolygonX[i];
      xyPolygon[xIdx+1] = fullPolygonY[i];
      xIdx += 2;
    }

    // Find the test corner and Position
    // 1) Default is Corner.X1_Y1_CORNER if neither (visibleX[0], visibleY[0])
    // or (visibleX[visibleX.length -1], visibleY[visibleY.length -1]) are visible x1,y1
    // 2) First alternate is (Corner.X1_Y2_CORNER as long as that is not an intersect
    // 3) Second alternate is Corner.X2_Y1_CORNER

    Position testPosition = new Position(); // actual test position
    Corner   testCorner; // corner of view box that is used for testing (matches position)
    double exitX = visibleX[visibleX.length - 1];
    double exitY = visibleY[visibleY.length - 1];
    if (!((viewBox.getMinX() == visibleX[0]) && (viewBox.getMinY() == visibleY[0])) ||
        !((viewBox.getMinX() == exitX) && (viewBox.getMinY() == exitY)) ) {
      testPosition.setCar(viewBox.getMinX(), viewBox.getMinY(), 0);
      testCorner = Corner.X1_Y1_CORNER;
    }
    else if (!((viewBox.getMinX() == visibleX[0]) && (viewBox.getMinY()  == visibleY[0])) ||
             !((viewBox.getMinX() == exitX) && (viewBox.getMinY()  == exitY)) ) {
      testPosition.setCar(viewBox.getMinX() , viewBox.getMinY() , 0);
      testCorner = Corner.X1_Y2_CORNER;
    }
    else {
      testPosition.setCar(viewBox.getMinX(), viewBox.getMinY(), 0);
      testCorner = Corner.X2_Y1_CORNER;
    }
    boolean inside = insidePolygon(testPosition.x, testPosition.y, fullPolygonX, fullPolygonY, npts, off);
    Corner[] cornersToAdd;

    if (firstIntersectLoc == secondIntersectLoc) {
      cornersToAdd = getCornersNeededSameIntersectLoc(secondIntersectLoc, visibleX[0], visibleY[0],
          visibleX[visibleX.length -1], visibleY[visibleY.length -1], inside);
    }
    else {
      cornersToAdd = getCornersNeededDiffIntersectLoc (firstIntersectLoc,
          secondIntersectLoc, testCorner, inside);
    }
    int[][] visibleShape = formVisibleShape(visibleX, visibleY, cornersToAdd,viewBox);

    return visibleShape;
  }


  /** Form the visible shape by starting with the line segment group (that represents
   *  the portion of the polygon that is visible as it crosses the view box) by adding
   *  and adding the specified view box corner points
   *
   * @param visibleX
   * @param visibleY
   * @param cornersToAdd
   * @param viewBox
   * @return
   */
  private static int[][] formVisibleShape (int[] visibleX, int[] visibleY, Corner[] cornersToAdd,
      Rectangle2D.Double viewBox) {
    // connecting points will be in non-viewable area around margin of view area
    int marginMinX = (int)viewBox.getMinX() - viewBoxMargin;
    int marginMinY = (int)viewBox.getMinY() - viewBoxMargin;
    int marginMaxX = (int)viewBox.getMaxX() + viewBoxMargin;
    int marginMaxY = (int)viewBox.getMaxY() + viewBoxMargin;

    int origLength = visibleX.length;
    int newLength = (cornersToAdd == null) ? origLength + 1 : origLength + cornersToAdd.length+ 1;
    int[][] connectedShapePts = new int[2][];
    connectedShapePts[0] = Arrays.copyOf(visibleX,newLength);
    connectedShapePts[1] = Arrays.copyOf(visibleY,newLength);

    // last point to add will always be connecting the chape back to itself
    connectedShapePts[0][newLength - 1] = visibleX[0];
    connectedShapePts[1][newLength - 1] = visibleY[0];

    if (cornersToAdd == null) {
      return connectedShapePts;
    }
    else {
      for (int i = 0; i < cornersToAdd.length; i++) {

        switch (cornersToAdd[i]) {
          case X1_Y1_CORNER:
            connectedShapePts[0][origLength + i] = marginMinX;
            connectedShapePts[1][origLength + i] = marginMinY;
            break;
          case X1_Y2_CORNER:
            connectedShapePts[0][origLength + i] = marginMinX;
            connectedShapePts[1][origLength + i] = marginMaxY;
            break;
          case X2_Y1_CORNER:
            connectedShapePts[0][origLength + i] = marginMaxX;
            connectedShapePts[1][origLength + i] = marginMinY;
            break;
          case X2_Y2_CORNER:
            connectedShapePts[0][origLength + i] = marginMaxX;
            connectedShapePts[1][origLength + i] = marginMaxY;
            break;
        }
      }
      return connectedShapePts;
    }
  }

  /** Get the corner locations we need to add to this line so it
   *  forms an enclosed shape with the same visible area
   *  Note: This requires a valid entry and exit intersect location
   *  that are DIFFERENT FROM EACH OTHER
   *
   *  @param entry       view border of entry line intersect
   *  @param exit        view border of exit line intersect
   *  @param testCorner  corner used to get point for insidePolygon test
   *  @param inside      true if test point was inside the original polygon
   *  @return
   */
  static Corner[] getCornersNeededDiffIntersectLoc (IntersectLocation entry,
      IntersectLocation exit, Corner testCorner, boolean inside) {

    boolean y1BorderIntersect = (entry  == IntersectLocation.Y1_BORDER) || (exit == IntersectLocation.Y1_BORDER);
    boolean y2BorderIntersect = (entry  == IntersectLocation.Y2_BORDER) || (exit == IntersectLocation.Y2_BORDER);
    boolean x1BorderIntersect = (entry  == IntersectLocation.X1_BORDER) || (exit == IntersectLocation.X1_BORDER);
    boolean x2BorderIntersect = (entry  == IntersectLocation.X2_BORDER) || (exit == IntersectLocation.X2_BORDER);

    // crosses view box y lines
    if (y1BorderIntersect && y2BorderIntersect) {
      // Note: the point tested WILL be the view x1,y1 point, as that is a
      // safe test point for this case (any intersect with x1 corner will be listed
      // as an X1_BORDER
      if (inside) {
        // shade left (i.e. smaller x values)
        if (exit == IntersectLocation.Y2_BORDER) {
          // go from last intersect to x1,y2 then to x1,y1, (then to first)
          return new Corner[]{Corner.X1_Y2_CORNER, Corner.X1_Y1_CORNER};
        }
        else {
          // go from last intersect to x1,y1 then to x1,y2, (then to first)
          return new Corner[]{Corner.X1_Y1_CORNER, Corner.X1_Y2_CORNER};
        }
      }
      else {
        // shade right (i.e. larger x values)
        if (exit == IntersectLocation.Y2_BORDER) {
          // go from last intersect to x2,y2 then to x2,y1, (then to first)
          return new Corner[]{Corner.X2_Y2_CORNER, Corner.X2_Y1_CORNER};
        }
        else {
          // go from last intersect to x2,y1 then to x2,y2, (then to first)
          return new Corner[]{Corner.X2_Y1_CORNER, Corner.X2_Y2_CORNER};
        }
      }
    }

    // crosses view box x lines
    if (x1BorderIntersect && x2BorderIntersect) {
      // Normal: inside and regular x1,y1 test corner means shade down
      // X1Y1 intersect: test corner was alt 1 (x1,y2) means shade up
      boolean needY1CornerValues =
          (inside  && (testCorner == Corner.X1_Y1_CORNER)) ||
          (!inside && (testCorner == Corner.X1_Y2_CORNER));
      if (needY1CornerValues) {
        if (exit == IntersectLocation.X2_BORDER) {
          // go from last intersect to x2,y1 then to x1,y1, (then to first)
          return new Corner[]{Corner.X2_Y1_CORNER, Corner.X1_Y1_CORNER};
        }
        else {
          // go from last intersect to x1,y1 then to x2,y1, (then to first)
          return new Corner[]{Corner.X1_Y1_CORNER, Corner.X2_Y1_CORNER};
        }
      }
      else {
        if (exit == IntersectLocation.X2_BORDER) {
          // go from last intersect to x2,y2 then to x1,y2, (then to first)
          return new Corner[]{Corner.X2_Y2_CORNER, Corner.X1_Y2_CORNER};
        }
        else {
          // go from last intersect to x1,y2 then to x2,y2, (then to first)
          return new Corner[]{Corner.X1_Y2_CORNER, Corner.X2_Y2_CORNER};
        }
      }
    }

    // crosses view box x1 & y1 lines
    if (x1BorderIntersect && y1BorderIntersect) {
      // Normal: inside and regular x1,y1 test corner means shade towards x1,y1 corner
      // X1Y1 intersect: test corner was alt 1 (x1,y2) means shade away from x1,y1 corner
      boolean needX1Y1Corner =
          (inside  && (testCorner == Corner.X1_Y1_CORNER)) ||
          (!inside && ((testCorner == Corner.X1_Y2_CORNER)));
      if (needX1Y1Corner) {
        // go from last intersect to x1,y1 (then to first)
        return new Corner[]{Corner.X1_Y1_CORNER};
      }
      else {
        // need 3 corners
        if (exit == IntersectLocation.Y1_BORDER) {
          // go from last intersect to x2,y1 then to x2,y2, then to x1,y2 (then to first)
          return new Corner[]{Corner.X2_Y1_CORNER, Corner.X2_Y2_CORNER, Corner.X1_Y2_CORNER};
        }
        else {
          // go from last intersect to x1,y2 then to x2,y2, (then to first)
          return new Corner[]{Corner.X1_Y2_CORNER, Corner.X2_Y2_CORNER, Corner.X2_Y1_CORNER};
        }
      }
    }

    // crosses view box x1 & y2 lines
    if (x1BorderIntersect && y2BorderIntersect) {
      // Normal: inside and regular x1,y1 test corner means shade towards x1,y1 corner
      // X1Y1 intersect: test corner was alt 1 (x1,y2) means shade away from x1,y1 corner
      boolean needX1Y1Corner =
          (inside  && (testCorner == Corner.X1_Y1_CORNER)) ||
          (!inside && ((testCorner == Corner.X1_Y2_CORNER)));
      if (!needX1Y1Corner) {
        // go from last intersect to x1,y2 (then to first)
        return new Corner[]{Corner.X1_Y2_CORNER};
      }
      else {
        // need 3 corners
        if (exit == IntersectLocation.Y2_BORDER) {
          // go from last intersect to x2,y2 then to x2,y1, then to x1,y1 (then to first)
          return new Corner[]{Corner.X2_Y2_CORNER, Corner.X2_Y1_CORNER, Corner.X1_Y1_CORNER};
        }
        else {
          // go from last intersect to x1,y1 then to x2,y1, then to x2,y2(then to first)
          return new Corner[]{Corner.X1_Y1_CORNER, Corner.X2_Y1_CORNER, Corner.X2_Y2_CORNER};
        }
      }
    }


    // crosses view box x2 & y1 lines
    if (x2BorderIntersect && y1BorderIntersect) {
      // Note: the point tested WILL be the view x1,y1 point, as that is a
      // safe test point for this case - inside means shade left
      if (!inside) {
        // go from last intersect to x2,y1 (then to first)
        return new Corner[]{Corner.X2_Y1_CORNER};
      }
      else {
        // need 3 corners
        if (exit == IntersectLocation.X2_BORDER) {
          // go from last intersect to x2,y2 then to x1,y2, then to x1,y1 (then to first)
          return new Corner[]{Corner.X2_Y2_CORNER, Corner.X1_Y2_CORNER, Corner.X1_Y1_CORNER};
        }
        else {
          // go from last intersect to x1,y1 then to x1,y2,then to x2,y2 (then to first)
          return new Corner[]{Corner.X1_Y1_CORNER, Corner.X1_Y2_CORNER, Corner.X2_Y2_CORNER};
        }
      }
    }

    // crosses view box x2 & y2 lines
    if (x2BorderIntersect && y2BorderIntersect) {
      // Note: the point tested WILL be the view x1,y1 point, as that is a
      // safe test point for this case - inside means shade left
      if (!inside) {
        // go from last intersect to x2,y2 (then to first)
        return new Corner[]{Corner.X2_Y2_CORNER};
      }
      else {
        // need 3 corners
        if (exit == IntersectLocation.X2_BORDER) {
          // go from last intersect to x2,y1 then to x1,y1, then to x1,y2 (then to first)
          return new Corner[]{Corner.X2_Y1_CORNER, Corner.X1_Y1_CORNER, Corner.X1_Y2_CORNER};
        }
        else {
          // go from last intersect to x1,y2 then to x1,y1, then to x2,y1(then to first)
          return new Corner[]{Corner.X1_Y2_CORNER, Corner.X1_Y1_CORNER, Corner.X2_Y1_CORNER};
        }
      }
    }

    throw new IllegalArgumentException("This method must be called with 2 distinct intersect locations");

  }

  /** Gets the view box corner points that need to be added to the line segment group
   *  in order to form the shape that is the intersection of the polygon with the view box.<br>
   *  The full shape needs to be formed, when it is to be filled.<br>
   *  This method is customized to handle just the case where the line segment group enters and
   *  exits along the same view box boundary.<br>
   *
   *   @param entryExit view boundary at which the line segment group enters and exits the view box
   *   @param entryX    x coordinate at which the line segment group enters the view box
   *   @param entryY    y coordinate at which the line segment group enters the view box
   *   @param exitX     x coordinate at which the line segment group exits the view box
   *   @param exitY     y coordinate at which the line segment group exits the view box
   *   @param inside    true of the view box test point (corner) was inside the polygon
   *   @return view box corner points that should be added (as Corner enum values)
   */
   static Corner[] getCornersNeededSameIntersectLoc (IntersectLocation entryExit,
      double entryX, double entryY, double exitX, double exitY, boolean inside) {
    if (!inside) {
      // no corners need to be added, just need to connect entry adn exit points
      return null;
    }
    else {
      // all 4 corners - just need to get starting corner and direction set
      if (entryExit == IntersectLocation.X1_BORDER) {
        if (exitY > entryY) {
          // clockwise corners
          return new Corner[]{Corner.X1_Y2_CORNER, Corner.X2_Y2_CORNER, Corner.X2_Y1_CORNER, Corner.X1_Y1_CORNER};
        }
        else {
          //counter-clockwise corners
          return new Corner[]{Corner.X1_Y1_CORNER, Corner.X1_Y1_CORNER, Corner.X2_Y2_CORNER, Corner.X1_Y2_CORNER};
        }
      }
      if (entryExit == IntersectLocation.X2_BORDER) {
        if (exitY < entryY) {
          // clockwise corners
          return new Corner[]{Corner.X2_Y1_CORNER, Corner.X1_Y1_CORNER, Corner.X1_Y2_CORNER, Corner.X2_Y2_CORNER};
        }
        else {
          //counter-clockwise corners
          return new Corner[]{Corner.X2_Y2_CORNER, Corner.X1_Y2_CORNER, Corner.X1_Y1_CORNER, Corner.X2_Y1_CORNER};
        }
      }
      if (entryExit == IntersectLocation.Y1_BORDER) {
        if (exitX < entryX) {
          // clockwise corners
          return new Corner[]{Corner.X1_Y1_CORNER, Corner.X1_Y2_CORNER, Corner.X2_Y2_CORNER, Corner.X1_Y2_CORNER};
        }
        else {
          //counter-clockwise corners
          return new Corner[]{Corner.X2_Y1_CORNER, Corner.X2_Y2_CORNER, Corner.X1_Y2_CORNER, Corner.X1_Y1_CORNER};
        }
      }
      if (entryExit == IntersectLocation.Y2_BORDER) {
        if (exitX > entryX) {
          // clockwise corners
          return new Corner[]{Corner.X2_Y2_CORNER, Corner.X2_Y1_CORNER, Corner.X1_Y1_CORNER, Corner.X1_Y2_CORNER};
        }
        else {
          //counter-clockwise corners
          return new Corner[]{Corner.X1_Y2_CORNER, Corner.X1_Y1_CORNER, Corner.X2_Y1_CORNER, Corner.X1_Y2_CORNER};
        }
      }
    }
    throw new IllegalArgumentException("This method must be called with a valid intersect location");
  }

  /** Tests of a point is inside of a polygon.  This is based on the java.awt.Polygon.contains
   *  method, but has been adjusted to be a static method that takes a polygon described
   *  by double points
   *
   *  @param x        x coordinate of point to test
   *  @param y        y coordinate of point to test
   *  @param xpoints  x coordinates of polygon
   *  @param ypoints  y coordiantes of polygon
   *  @param npoints  number of valid polygon points
   *  @return true if the point is inside the polygon
   */
  static boolean insidePolygon(double x, double y, double[] xpoints, double[] ypoints, int npoints, int off) {
    if (npoints <= 2) {
      // could also probably optimize by getting bounding box by doing Arrays.sort on npts of x and y
      // if not within bounding box, could return false here
      return false;
    }
    int hits = 0;

    double lastx = xpoints[npoints + off - 1];
    double lasty = ypoints[npoints + off - 1];
    double curx, cury;

    // Walk the edges of the polygon
    for (int i = off; i < npoints + off; lastx = curx, lasty = cury, i++) {
        curx = xpoints[i];
        cury = ypoints[i];

        if (cury == lasty) {
            continue;
        }

        double leftx;
        if (curx < lastx) {
            if (x >= lastx) {
                continue;
            }
            leftx = curx;
        } else {
            if (x >= curx) {
                continue;
            }
            leftx = lastx;
        }

        double test1, test2;
        if (cury < lasty) {
            if (y < cury || y >= lasty) {
                continue;
            }
            if (x < leftx) {
                hits++;
                continue;
            }
            test1 = x - curx;
            test2 = y - cury;
        } else {
            if (y < lasty || y >= cury) {
                continue;
            }
            if (x < leftx) {
                hits++;
                continue;
            }
            test1 = x - lastx;
            test2 = y - lasty;
        }

        if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
            hits++;
        }
    }

    return ((hits & 1) != 0);
  }

  /** check for box intersection / overlap
   * @param box1 {xmin, ymin, xmax, ymax}
   * @param box2 {xmin, ymin, xmax, ymax}
   * @return true if the boxes intersect / overlap
   * @since NeXtMidas 3.9.2
   */
  @InternalUseOnly
  public static boolean boxIntersect(int[] box1, int[] box2) {
    return (!((box1[0] > box2[2]) || (box1[1] > box2[3]) || (box1[2] < box2[0]) || (box1[3] < box2[1])));
  }

  /** check for box intersection / overlap
  * @param box1 {xmin, ymin, xmax, ymax}
  * @param box2 {xmin, ymin, xmax, ymax}
  * @return true if the boxes intersect / overlap
  * @since NeXtMidas 3.9.2
  */
 @InternalUseOnly
 public static boolean boxIntersect(double[] box1, double[] box2) {
   return (!((box1[0] > box2[2]) || (box1[1] > box2[3]) || (box1[2] < box2[0]) || (box1[3] < box2[1])));
 }

 /** check for a box intersecting / overlapping x bounds
   * @param box1 {xmin, ymin, xmax, ymax}
   * @param xvals {xmin, xmax}
   * @return true if the box intersects / overlaps the x bounds
   * @since NeXtMidas 3.9.2
   */
  @InternalUseOnly
  public static boolean xIntersect(double[] box1, double[] xvals) {
    return (!((box1[0] > xvals[1])|| (box1[2] < xvals[0])));
  }

  /** Calculates the bounding box of the points passed to the constructor.
   *  Sets <code>bounds</code> to the result.
   *  Adapted from Oracle int version
   *  @param xpoints[] array of <i>x</i> coordinates
   *  @param ypoints[] array of <i>y</i> coordinates
   *  @param npoints the total number of points
   */
  static Rectangle2D.Double calculateBounds(double xpoints[], double ypoints[], int npoints, int offset) {
      double boundsMinX = Double.MAX_VALUE;
      double boundsMinY = Double.MAX_VALUE;
      double boundsMaxX = Double.MIN_VALUE;
      double boundsMaxY = Double.MIN_VALUE;

      for (int i = offset; i < npoints; i++) {
          double x = xpoints[i];
          boundsMinX = Math.min(boundsMinX, x);
          boundsMaxX = Math.max(boundsMaxX, x);
          double y = ypoints[i];
          boundsMinY = Math.min(boundsMinY, y);
          boundsMaxY = Math.max(boundsMaxY, y);
      }
      return new Rectangle2D.Double(boundsMinX, boundsMinY,
                             boundsMaxX - boundsMinX,
                             boundsMaxY - boundsMinY);
  }

  /** Set margin around view box used when adding corner points to form
   *  enclosed shape
   *
   *  @param viewBoxMargin margin from view box fro corner points
   */
  @InternalUseOnly
  public static void setViewBoxMargin (int viewBoxMargin) {
    GeometricUtil.viewBoxMargin = viewBoxMargin;
  }

//******************* INNER CLASS *************************************************************************
  /** Holds a Line Segment Group that represents one traversal of the
   *  polygon across the view area
   */
  @InternalUseOnly
  public static class LineSegmentGroup {

    int[] xcoords;
    int[] ycoords;
    IntersectLocation entry;
    IntersectLocation exit;

    LineSegmentGroup (int[] xcoords, int[] ycoords, IntersectLocation entry, IntersectLocation exit) {
      this.xcoords = xcoords;
      this.ycoords = ycoords;
      this.entry = entry;
      this.exit = exit;
    }

    LineSegmentGroup (int xcoordsSize, int ycoordsSize) {
      this.xcoords = new int[xcoordsSize];
      this.ycoords = new int[ycoordsSize];

    }

    /** Get the x coordinates of this line segment group
     *  @return the x coordinates
     */
    @InternalUseOnly
    public int[] getXcoords () {
      return xcoords;
    }

    /** Get the y coordinates of this line segment group
     *  @return the y coordinates
     */
    @InternalUseOnly
    public int[] getYcoords () {
      return ycoords;
    }

    /** Gets the entry intersect boundary
     * @return the entry
     */
    IntersectLocation getEntry () {
      return entry;
    }

    /** Gets the exit intersect boundary
     *  @return the exit
     */
    IntersectLocation getExit () {
      return exit;
    }


  }
}

