MinimumEnclosingTriangle

MinimumEnclosingTriangle.java

import org.locationtech.jts.geom.Coordinate;

import java.util.ArrayList;
import java.util.List;

/**
 * Implementation of linear minimum area enclosing triangle algorithm.
 * Computational and Applied Mathematics, 35(2), 423–438.
 * doi:10.1007/s40314-014-0198-8
 * 
 * https://github.com/opencv/opencv/blob/master/modules/imgproc/src/min_enclosing_triangle.cpp
 * https://github.com/ovidiuparvu/minimal-area-triangle/tree/master/modules/triangle/src
 * 
 * @author Algorithm by Ovidiu Parvu
 * @author Java port by Michael Carleton
 *
 */
public class MinimumEnclosingTriangle {

	// Intersection of line and polygon

	private static final int INTERSECTS_BELOW = 1;
	private static final int INTERSECTS_ABOVE = 2;
	private static final int INTERSECTS_CRITICAL = 3;

	// Error messages

	private static final String ERR_SIDE_B_GAMMA = "The position of side B could not be determined, because gamma(b) could not be computed.";
	private static final String ERR_VERTEX_C_ON_SIDE_B = "The position of the vertex C on side B could not be determined, because the considered lines do not intersect.";

	// Possible values for validation flag

	private static final int VALIDATION_SIDE_A_TANGENT = 0;
	private static final int VALIDATION_SIDE_B_TANGENT = 1;
	private static final int VALIDATION_SIDES_FLUSH = 2;

	// Threshold value for comparisons

	private static final double EPSILON = 1E-5;

	/*
	 * Broken out into class level for Java as C++ uses pass-by-reference.
	 */
	Coordinate vertexA, vertexB, vertexC;

	Coordinate sideAStartVertex, sideAEndVertex;
	Coordinate sideBStartVertex, sideBEndVertex;
	Coordinate sideCStartVertex, sideCEndVertex;

	public List<Coordinate> triangle;
	public double area = Double.MAX_VALUE;

	public int validationFlag;

	public MinimumEnclosingTriangle() {
		triangle = new ArrayList<Coordinate>();
		vertexA = new Coordinate();
		vertexB = new Coordinate();
		vertexC = new Coordinate();

		sideAStartVertex = new Coordinate();
		sideBStartVertex = new Coordinate();
		sideCStartVertex = new Coordinate();
		sideAEndVertex = new Coordinate();
		sideBEndVertex = new Coordinate();
		sideCEndVertex = new Coordinate();
	}

	/**
	 * Find the minimum area enclosing triangle for the given polygon
	 * 
	 * @param polygon The polygon representing the convex hull of the points (not
	 *                closed)
	 */
	public void findMinimumAreaEnclosingTriangle(final List<Coordinate> polygon) {
		// Algorithm specific variables

		List<Coordinate> copy = new ArrayList<Coordinate>();

		polygon.forEach(c -> copy.add(c.copy()));


		MutableInt a, b, c;
		final int nrOfPoints;

		// Variables initialisation

		nrOfPoints = polygon.size();

		a = new MutableInt(1);
		b = new MutableInt(2);
		c = new MutableInt(0);

		// Main algorithm steps
		while (c.value < nrOfPoints) {
			advanceBToRightChain(polygon, nrOfPoints, b, c);
			moveAIfLowAndBIfHigh(polygon, nrOfPoints, a, b, c);
			searchForBTangency(polygon, nrOfPoints, a, b, c);
			updateSidesCA(polygon, nrOfPoints, a, c);

			if (isNotBTangency(polygon, nrOfPoints, a.value, b.value, c.value)) {
				updateSidesBA(polygon, nrOfPoints, a.value, b.value, c.value);
			} else {
				updateSideB(polygon, nrOfPoints, a.value, b.value, c.value);
			}

			if (isLocalMinimalTriangle(polygon, nrOfPoints, a.value, b.value)) {
				updateMinimumAreaEnclosingTriangle();
			}
			c.inc();
		}
	}

	/**
	 * Return the minimum area enclosing (pseudo-)triangle in case the convex //
	 * polygon has at most three points
	 *
	 *
	 * 
	 * @param polygon  The polygon representing the convex hull of the points
	 * 
	 * @param triangle Minimum area triangle enclosing the given polygon
	 * 
	 * @param area     Area of the minimum area enclosing triangle
	 */
	void returnMinimumAreaEnclosingTriangle(final List<Coordinate> polygon) {
		int nrOfPoints = polygon.size();

		for (int i = 0; i < 3; i++) {
			triangle.add(polygon.get(i % nrOfPoints));
		}

		area = areaOfTriangle(triangle.get(0), triangle.get(1), triangle.get(2));
	}

	/**
	 * Advance b to the right chain
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygon    The polygon representing the convex hull of the points
	 * 
	 * @param nrOfPoints Number of points defining the convex polygon
	 * 
	 * @param b          Index b
	 * 
	 * @param c          Index c int
	 */
	void advanceBToRightChain(final List<Coordinate> polygon, int nrOfPoints, MutableInt b, final MutableInt c) {
		while (greaterOrEqual(height(successor(b.value, nrOfPoints), polygon, nrOfPoints, c.value),
				height(b, polygon, nrOfPoints, c))) {
			advance(b, nrOfPoints);
		}
	}

	/**
	 * Move "a" if it is low and "b" if it is high
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygon    The polygon representing the convex hull of the points
	 * 
	 * @param nrOfPoints Number of points defining the convex polygon
	 * 
	 * @param a          Index a
	 * 
	 * @param b          Index b
	 * 
	 * @param c          Index c
	 */
	void moveAIfLowAndBIfHigh(final List<Coordinate> polygon, int nrOfPoints, MutableInt a, MutableInt b,
			MutableInt c) {
		Coordinate gammaOfA = new Coordinate();

		while (height(b, polygon, nrOfPoints, c) > height(a, polygon, nrOfPoints, c)) {
			if ((gamma(a.value, gammaOfA, polygon, nrOfPoints, a.value, c.value))
					&& (intersectsBelow(gammaOfA, b.value, polygon, nrOfPoints, c.value))) {
				advance(b, nrOfPoints);
			} else {
				advance(a, nrOfPoints);
			}
		}
	}

	/**
	 * Search for the tangency of side B
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygon    The polygon representing the convex hull of the points
	 * 
	 * @param nrOfPoints Number of points defining the convex polygon
	 * 
	 * @param a          Index a
	 * 
	 * @param b          Index b
	 * 
	 * @param c          Index c
	 */
	void searchForBTangency(final List<Coordinate> polygon, int nrOfPoints, MutableInt a, MutableInt b, MutableInt c) {
		Coordinate gammaOfB = new Coordinate(); // TODO mutates by gamma()

		while (((gamma(b.value, gammaOfB, polygon, nrOfPoints, a.value, c.value))
				&& (intersectsBelow(gammaOfB, b.value, polygon, nrOfPoints, c.value)))
				&& (greaterOrEqual(height(b.value, polygon, nrOfPoints, c.value),
						height(predecessor(a.value, nrOfPoints), polygon, nrOfPoints, c.value)))) {
			advance(b, nrOfPoints);
		}
	}

	/**
	 * Check if tangency for side B was not obtained
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygon    The polygon representing the convex hull of the points
	 * 
	 * @param nrOfPoints Number of points defining the convex polygon
	 * 
	 * @param a          Index a
	 * 
	 * @param b          Index b
	 * 
	 * @param c          Index c
	 */
	boolean isNotBTangency(final List<Coordinate> polygon, int nrOfPoints, int a, int b, int c) {
		Coordinate gammaOfB = new Coordinate(); // TODO mutates by gamma();

		if (((gamma(b, gammaOfB, polygon, nrOfPoints, a, c)) && (intersectsAbove(gammaOfB, b, polygon, nrOfPoints, c)))
				|| (height(b, polygon, nrOfPoints, c) < height(predecessor(a, nrOfPoints), polygon, nrOfPoints, c))) {
			return true;
		}

		return false;
	}

	/**
	 * Update sides A and C
	 *
	 * Side C will have as start and end vertices the polygon points "c" and "c-1"
	 * Side A will have as start and end vertices the polygon points "a" and "a-1"
	 *
	 * @param polygon          The polygon representing the convex hull of the
	 *                         points
	 * 
	 * @param nrOfPoints       Number of points defining the convex polygon
	 * 
	 * @param a                Index a
	 * 
	 * @param c                Index c
	 * 
	 * @param sideAStartVertex Start vertex for defining side A
	 * 
	 * @param sideAEndVertex   End vertex for defining side A
	 * 
	 * @param sideCStartVertex Start vertex for defining side C
	 * 
	 * @param sideCEndVertex   End vertex for defining side C
	 */
	void updateSidesCA(final List<Coordinate> polygon, int nrOfPoints, MutableInt a, MutableInt c) {
		sideCStartVertex = polygon.get(predecessor(c.value, nrOfPoints));
		sideCEndVertex = polygon.get(c.value).copy();

		sideAStartVertex = polygon.get(predecessor(a.value, nrOfPoints));
		sideAEndVertex = polygon.get(a.value).copy();
	}

	/**
	 * Update sides B and possibly A if tangency for side B was not obtained
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygon          The polygon representing the convex hull of the
	 *                         points
	 * 
	 * @param nrOfPoints       Number of points defining the convex polygon
	 * 
	 * @param a                Index a
	 * 
	 * @param b                Index b
	 * 
	 * @param c                Index c
	 * 
	 * @param validationFlag   Flag used for validation
	 * 
	 * @param sideAStartVertex Start vertex for defining side A
	 * 
	 * @param sideAEndVertex   End vertex for defining side A
	 * 
	 * @param sideBStartVertex Start vertex for defining side B
	 * 
	 * @param sideBEndVertex   End vertex for defining side B
	 * 
	 * @param sideCStartVertex Start vertex for defining side C
	 * 
	 * @param sideCEndVertex   End vertex for defining side C
	 */
	void updateSidesBA(final List<Coordinate> polygon, int nrOfPoints, int a, int b, int c) {
		// Side B is flush with edge [b, b-1)
		sideBStartVertex = polygon.get(predecessor(b, nrOfPoints)).copy();
		sideBEndVertex = polygon.get(b).copy();

		// Find middle point of side B
		Coordinate sideBMiddlePoint = new Coordinate();

		if ((middlePointOfSideB(sideBMiddlePoint, sideAStartVertex, sideAEndVertex, sideBStartVertex, sideBEndVertex,
				sideCStartVertex, sideCEndVertex))
				&& (height(sideBMiddlePoint, polygon, nrOfPoints, c) < height(predecessor(a, nrOfPoints), polygon,
						nrOfPoints, c))) {
			sideAStartVertex = polygon.get(predecessor(a, nrOfPoints)).copy();
			sideAEndVertex = findVertexCOnSideB(polygon, nrOfPoints, a, c, sideBStartVertex, sideBEndVertex,
					sideCStartVertex, sideCEndVertex).copy();

			validationFlag = VALIDATION_SIDE_A_TANGENT;
		} else {
			validationFlag = VALIDATION_SIDES_FLUSH;
		}
	}

	/**
	 * Set side B if tangency for side B was obtained
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygon          The polygon representing the convex hull of the
	 *                         points
	 * 
	 * @param nrOfPoints       Number of points defining the convex polygon
	 * 
	 * @param a                Index a
	 * 
	 * @param b                Index b
	 * 
	 * @param c                Index c
	 * 
	 * @param validationFlag   Flag used for validation
	 * 
	 * @param sideBStartVertex Start vertex for defining side B
	 * 
	 * @param sideBEndVertex   End vertex for defining side B
	 */
	void updateSideB(final List<Coordinate> polygon, int nrOfPoints, int a, int b, int c) {
		if (!gamma(b, sideBStartVertex, polygon, nrOfPoints, a, c)) {
			System.err.println(ERR_SIDE_B_GAMMA);
		}

		sideBEndVertex = polygon.get(b).copy();

		validationFlag = VALIDATION_SIDE_B_TANGENT;
	}

	/**
	 * Update the triangle vertices after all sides were set and check if a local //
	 * minimal triangle was found or not
	 *
	 * See paper .get(2) for more details
	 *
	 * @param vertexA          Vertex A of the enclosing triangle
	 * 
	 * @param vertexB          Vertex B of the enclosing triangle
	 * 
	 * @param vertexC          Vertex C of the enclosing triangle
	 * 
	 * @param polygon          The polygon representing the convex hull of the
	 *                         points
	 * 
	 * @param nrOfPoints       Number of points defining the convex polygon
	 * 
	 * @param a                Index a
	 * 
	 * @param b                Index b
	 * 
	 * @param validationFlag   Flag used for validation
	 * 
	 * @param sideAStartVertex Start vertex for defining side A
	 * 
	 * @param sideAEndVertex   End vertex for defining side A
	 * 
	 * @param sideBStartVertex Start vertex for defining side B
	 * 
	 * @param sideBEndVertex   End vertex for defining side B
	 * 
	 * @param sideCStartVertex Start vertex for defining side C
	 * 
	 * @param sideCEndVertex   End vertex for defining side C
	 */
	boolean isLocalMinimalTriangle(final List<Coordinate> polygon, int nrOfPoints, int a, int b) {
		if ((!lineIntersection(sideAStartVertex, sideAEndVertex, sideBStartVertex, sideBEndVertex, vertexC))
				|| (!lineIntersection(sideAStartVertex, sideAEndVertex, sideCStartVertex, sideCEndVertex, vertexB))
				|| (!lineIntersection(sideBStartVertex, sideBEndVertex, sideCStartVertex, sideCEndVertex, vertexA))) {
			return false;
		}

		return isValidMinimalTriangle(polygon, nrOfPoints, a, b);
	}

	/**
	 * Check if the found minimal triangle is valid
	 *
	 * This means that all midpoints of the triangle should touch the polygon
	 *
	 * See paper .get(2) for more details
	 *
	 * @param vertexA          Vertex A of the enclosing triangle
	 * 
	 * @param vertexB          Vertex B of the enclosing triangle
	 * 
	 * @param vertexC          Vertex C of the enclosing triangle
	 * 
	 * @param polygon          The polygon representing the convex hull of the
	 *                         points
	 * 
	 * @param nrOfPoints       Number of points defining the convex polygon
	 * 
	 * @param a                Index a
	 * 
	 * @param b                Index b
	 * 
	 * @param validationFlag   Flag used for validation
	 * 
	 * @param sideAStartVertex Start vertex for defining side A
	 * 
	 * @param sideAEndVertex   End vertex for defining side A
	 * 
	 * @param sideBStartVertex Start vertex for defining side B
	 * 
	 * @param sideBEndVertex   End vertex for defining side B
	 * 
	 * @param sideCStartVertex Start vertex for defining side C
	 * 
	 * @param sideCEndVertex   End vertex for defining side C
	 */
	boolean isValidMinimalTriangle(final List<Coordinate> polygon, int nrOfPoints, int a, int b) {
		Coordinate midpointSideA = middlePoint(vertexB, vertexC);
		Coordinate midpointSideB = middlePoint(vertexA, vertexC);
		Coordinate midpointSideC = middlePoint(vertexA, vertexB);

		boolean sideAValid = (validationFlag == VALIDATION_SIDE_A_TANGENT)
				? (areEqualPoints(midpointSideA, polygon.get(predecessor(a, nrOfPoints))))
				: (isPointOnLineSegment(midpointSideA, sideAStartVertex, sideAEndVertex));

		boolean sideBValid = (validationFlag == VALIDATION_SIDE_B_TANGENT)
				? (areEqualPoints(midpointSideB, polygon.get(b)))
				: (isPointOnLineSegment(midpointSideB, sideBStartVertex, sideBEndVertex));

		boolean sideCValid = (validationFlag == VALIDATION_SIDES_FLUSH)
				|| isPointOnLineSegment(midpointSideC, sideCStartVertex, sideCEndVertex);

		return (sideAValid && sideBValid && sideCValid);
	}

	/**
	 * Update the current minimum area enclosing triangle if the newly obtained //
	 * one has a smaller area
	 *
	 *
	 * 
	 * @param triangle Minimum area triangle enclosing the given polygon
	 * 
	 * @param area     Area of the minimum area triangle enclosing the given polygon
	 * 
	 * @param vertexA  Vertex A of the enclosing triangle
	 * 
	 * @param vertexB  Vertex B of the enclosing triangle
	 * 
	 * @param vertexC  Vertex C of the enclosing triangle
	 */
	void updateMinimumAreaEnclosingTriangle() {
		final double triangleArea = areaOfTriangle(vertexA, vertexB, vertexC);

		if (triangleArea < area) {
			triangle.clear();
			triangle.add(vertexA);
			triangle.add(vertexB);
			triangle.add(vertexC);

			area = triangleArea;
		}
	}

	/**
	 * Return the middle point of side B
	 * 
	 * @param middlePointOfSideB Middle point of side B
	 * 
	 * @param sideAStartVertex   Start vertex for defining side A
	 * 
	 * @param sideAEndVertex     End vertex for defining side A
	 * 
	 * @param sideBStartVertex   Start vertex for defining side B
	 * 
	 * @param sideBEndVertex     End vertex for defining side B
	 * 
	 * @param sideCStartVertex   Start vertex for defining side C
	 * 
	 * @param sideCEndVertex     End vertex for defining side C
	 */
	boolean middlePointOfSideB(final Coordinate middlePointOfSideB, final Coordinate sideAStartVertex,
			final Coordinate sideAEndVertex, final Coordinate sideBStartVertex, final Coordinate sideBEndVertex,
			final Coordinate sideCStartVertex, final Coordinate sideCEndVertex) {
//		Coordinate vertexA = new Coordinate(); // TODO init as empty
//		Coordinate vertexC = new Coordinate();

		if ((!lineIntersection(sideBStartVertex, sideBEndVertex, sideCStartVertex, sideCEndVertex, vertexA))
				|| (!lineIntersection(sideBStartVertex, sideBEndVertex, sideAStartVertex, sideAEndVertex, vertexC))) {
			return false;
		}

		final Coordinate c = middlePoint(vertexA, vertexC);
		middlePointOfSideB.x = c.x;
		middlePointOfSideB.y = c.y;

		return true;
	}

	/**
	 * Check if the line intersects below
	 *
	 * Check if the line determined by gammaPoint and polygon.get(polygonPointIndex)
	 * intersects the polygon below the point polygon.get(polygonPointIndex)
	 *
	 * @param gammaPoint        Gamma(p)
	 * 
	 * @param polygonPointIndex Index of the polygon point which is considered when
	 *                          determining the line
	 * 
	 * @param polygon           The polygon representing the convex hull of the
	 *                          points
	 * 
	 * @param nrOfPoints        Number of points defining the convex polygon
	 * 
	 * @param c                 Index c
	 */
	boolean intersectsBelow(final Coordinate gammaPoint, int polygonPointIndex, final List<Coordinate> polygon,
			int nrOfPoints, int c) {
		double angleOfGammaAndPoint = angleOfLineWrtOxAxis(polygon.get(polygonPointIndex), gammaPoint);

		return (intersects(angleOfGammaAndPoint, polygonPointIndex, polygon, nrOfPoints, c) == INTERSECTS_BELOW);
	}

	/**
	 * Check if the line intersects above
	 *
	 * Check if the line determined by gammaPoint and polygon.get(polygonPointIndex)
	 * intersects the polygon above the point polygon.get(polygonPointIndex)
	 *
	 * @param gammaPoint        Gamma(p)
	 * 
	 * @param polygonPointIndex Index of the polygon point which is considered when
	 *                          determining the line
	 * 
	 * @param polygon           The polygon representing the convex hull of the
	 *                          points
	 * 
	 * @param nrOfPoints        Number of points defining the convex polygon
	 * 
	 * @param c                 Index c
	 */
	boolean intersectsAbove(final Coordinate gammaPoint, int polygonPointIndex, final List<Coordinate> polygon,
			int nrOfPoints, int c) {
		double angleOfGammaAndPoint = angleOfLineWrtOxAxis(gammaPoint, polygon.get(polygonPointIndex));

		return (intersects(angleOfGammaAndPoint, polygonPointIndex, polygon, nrOfPoints, c) == INTERSECTS_ABOVE);
	}

	/**
	 * Check if/where the line determined by gammaPoint and //
	 * polygon.get(polygonPointIndex) intersects the polygon
	 *
	 *
	 * 
	 * @param angleGammaAndPoint Angle determined by gammaPoint and
	 *                           polygon.get(polygonPointIndex) wrt Ox axis
	 * 
	 * @param polygonPointIndex  Index of the polygon point which is considered when
	 *                           determining the line
	 * 
	 * @param polygon            The polygon representing the convex hull of the
	 *                           points
	 * 
	 * @param nrOfPoints         Number of points defining the convex polygon
	 * 
	 * @param c                  Index c
	 */

	int intersects(double angleGammaAndPoint, int polygonPointIndex, final List<Coordinate> polygon, int nrOfPoints,
			int c) {
		double anglePointPredecessor = angleOfLineWrtOxAxis(polygon.get(predecessor(polygonPointIndex, nrOfPoints)),
				polygon.get(polygonPointIndex));
		double anglePointSuccessor = angleOfLineWrtOxAxis(polygon.get(successor(polygonPointIndex, nrOfPoints)),
				polygon.get(polygonPointIndex));
		double angleFlushEdge = angleOfLineWrtOxAxis(polygon.get(predecessor(c, nrOfPoints)), polygon.get(c));

		if (isFlushAngleBtwPredAndSucc(angleFlushEdge, anglePointPredecessor, anglePointSuccessor)) {
			if ((isGammaAngleBtw(angleGammaAndPoint, anglePointPredecessor, angleFlushEdge))
					|| (almostEqual(angleGammaAndPoint, anglePointPredecessor))) {
				return intersectsAboveOrBelow(predecessor(polygonPointIndex, nrOfPoints), polygonPointIndex, polygon,
						nrOfPoints, c);
			} else if ((isGammaAngleBtw(angleGammaAndPoint, anglePointSuccessor, angleFlushEdge))
					|| (almostEqual(angleGammaAndPoint, anglePointSuccessor))) {
				return intersectsAboveOrBelow(successor(polygonPointIndex, nrOfPoints), polygonPointIndex, polygon,
						nrOfPoints, c);
			}
		} else {
			if ((isGammaAngleBtw(angleGammaAndPoint, anglePointPredecessor, anglePointSuccessor))
					|| ((isGammaAngleEqualTo(angleGammaAndPoint, anglePointPredecessor))
							&& (!isGammaAngleEqualTo(angleGammaAndPoint, angleFlushEdge)))
					|| ((isGammaAngleEqualTo(angleGammaAndPoint, anglePointSuccessor))
							&& (!isGammaAngleEqualTo(angleGammaAndPoint, angleFlushEdge)))) {
				return INTERSECTS_BELOW;
			}
		}

		return INTERSECTS_CRITICAL;
	}

	/**
	 * If (gamma(x) x) intersects P between successorOrPredecessorIndex and //
	 * pointIntex is it above/below?
	 *
	 *
	 * 
	 * @param succPredIndex Index of the successor or predecessor
	 * 
	 * @param pointIndex    Index of the point x in the polygon
	 * 
	 * @param polygon       The polygon representing the convex hull of the points
	 * 
	 * @param nrOfPoints    Number of points defining the convex polygon
	 * 
	 * @param c             Index c
	 */

	private static int intersectsAboveOrBelow(int succPredIndex, int pointIndex, final List<Coordinate> polygon,
			int nrOfPoints,
			int c) {
		if (height(succPredIndex, polygon, nrOfPoints, c) > height(pointIndex, polygon, nrOfPoints, c)) {
			return INTERSECTS_ABOVE;
		} else {
			return INTERSECTS_BELOW;
		}
	}

	/**
	 * Find gamma for a given point "p" specified by its index
	 *
	 * The function returns true if gamma exists i.e. if lines (a a-1) and (x y)
	 * intersect and false otherwise. In case the two lines intersect in point
	 * intersectionPoint, gamma is computed.
	 *
	 * Considering that line (x y) is a line parallel to (c c-1) and that the
	 * distance between the lines is equal to 2 * height(p), we can have two
	 * possible (x y) lines.
	 *
	 * Therefore, we will compute two intersection points between the lines (x y)
	 * and (a a-1) and take the point which is on the same side of line (c c-1) as
	 * the polygon.
	 *
	 * See paper .get(2) and formula for distance from point to a line for more
	 * details
	 *
	 * @param polygonPointIndex Index of the polygon point
	 * 
	 * @param gammaPoint        Point gamma(polygon.get(polygonPointIndex))
	 * 
	 * @param polygon           The polygon representing the convex hull of the
	 *                          points
	 * 
	 * @param nrOfPoints        Number of points defining the convex polygon
	 * 
	 * @param a                 Index a
	 * 
	 * @param c                 Index c
	 */
	boolean gamma(int polygonPointIndex, Coordinate gammaPoint, final List<Coordinate> polygon, int nrOfPoints, int a,
			int c) {
		Coordinate intersectionPoint1 = new Coordinate(); // init empty (other methods set vals)
		Coordinate intersectionPoint2 = new Coordinate(); // init empty

		// Get intersection points if they exist
		if (!findGammaIntersectionPoints(polygon, nrOfPoints, c, polygonPointIndex, polygon.get(a),
				polygon.get(predecessor(a, nrOfPoints)), polygon.get(c), polygon.get(predecessor(c, nrOfPoints)),
				intersectionPoint1, intersectionPoint2)) {
			return false;
		}

		// Select the point which is on the same side of line C as the polygon
		if (areOnTheSameSideOfLine(intersectionPoint1, polygon.get(successor(c, nrOfPoints)), polygon.get(c),
				polygon.get(predecessor(c, nrOfPoints)))) {
			gammaPoint.x = intersectionPoint1.x; // TODO mutate x & y instead of c++ reference
			gammaPoint.y = intersectionPoint1.y; // TODO mutate x & y instead of c++ reference
		} else {
			gammaPoint.x = intersectionPoint2.x;
			gammaPoint.y = intersectionPoint2.y;
		}

		return true;
	}

	/**
	 * Find vertex C which lies on side B at a distance = 2 * height(a-1) from //
	 * side C
	 *
	 * Considering that line (x y) is a line parallel to (c c-1) and that the
	 * distance between the lines is equal to 2 * height(a-1), we can have two
	 * possible (x y) lines.
	 *
	 * Therefore, we will compute two intersection points between the lines (x y)
	 * and (b b-1) and take the point which is on the same side of line (c c-1) as
	 * the polygon.
	 *
	 * See paper .get(2) and formula for distance from point to a line for more
	 * details
	 *
	 * @param polygon          The polygon representing the convex hull of the
	 *                         points
	 * 
	 * @param nrOfPoints       Number of points defining the convex polygon
	 * 
	 * @param a                Index a
	 * 
	 * @param c                Index c
	 * 
	 * @param sideBStartVertex Start vertex for defining side B
	 * 
	 * @param sideBEndVertex   End vertex for defining side B
	 * 
	 * @param sideCStartVertex Start vertex for defining side C
	 * 
	 * @param sideCEndVertex   End vertex for defining side C
	 */
	Coordinate findVertexCOnSideB(final List<Coordinate> polygon, int nrOfPoints, int a, int c,
			final Coordinate sideBStartVertex, final Coordinate sideBEndVertex, final Coordinate sideCStartVertex,
			final Coordinate sideCEndVertex) {
		Coordinate intersectionPoint1 = new Coordinate();
		Coordinate intersectionPoint2 = new Coordinate();

		// Get intersection points if they exist
		if (!findGammaIntersectionPoints(polygon, nrOfPoints, c, predecessor(a, nrOfPoints), sideBStartVertex,
				sideBEndVertex, sideCStartVertex, sideCEndVertex, intersectionPoint1, intersectionPoint2)) {
			System.out.println(ERR_VERTEX_C_ON_SIDE_B);
		}

		// Select the point which is on the same side of line C as the polygon
		if (areOnTheSameSideOfLine(intersectionPoint1, polygon.get(successor(c, nrOfPoints)), polygon.get(c),
				polygon.get(predecessor(c, nrOfPoints)))) {
			return intersectionPoint1;
		} else {
			return intersectionPoint2;
		}
	}

	/**
	 * Find the intersection points to compute gamma(point)
	 *
	 *
	 * 
	 * @param polygon            The polygon representing the convex hull of the
	 *                           points
	 * 
	 * @param nrOfPoints         Number of points defining the convex polygon
	 * 
	 * @param c                  Index c
	 * 
	 * @param polygonPointIndex  Index of the polygon point for which the distance
	 *                           is known
	 * 
	 * @param side1StartVertex   Start vertex for side 1
	 * 
	 * @param side1EndVertex     End vertex for side 1
	 * 
	 * @param side2StartVertex   Start vertex for side 2
	 * 
	 * @param side2EndVertex     End vertex for side 2
	 * 
	 * @param intersectionPoint1 First intersection point between one pair of lines
	 * 
	 * @param intersectionPoint2 Second intersection point between other pair of
	 *                           lines
	 */
	boolean findGammaIntersectionPoints(final List<Coordinate> polygon, int nrOfPoints, int c, int polygonPointIndex,
			final Coordinate side1StartVertex, final Coordinate side1EndVertex, final Coordinate side2StartVertex,
			final Coordinate side2EndVertex, Coordinate intersectionPoint1, Coordinate intersectionPoint2) {

		List<Double> side1Params = lineEquationParameters(side1StartVertex, side1EndVertex);
		List<Double> side2Params = lineEquationParameters(side2StartVertex, side2EndVertex);

		// Compute side C extra parameter using the formula for distance from a point to
		// a line
		double polygonPointHeight = height(polygonPointIndex, polygon, nrOfPoints, c);
		double distFormulaDenom = Math
				.sqrt((side2Params.get(0) * side2Params.get(0)) + (side2Params.get(1) * side2Params.get(1)));
		double sideCExtraParam = 2 * polygonPointHeight * distFormulaDenom;

		// Get intersection points if they exist or if lines are identical
		if (areIntersectingLines(side1Params, side2Params, sideCExtraParam, intersectionPoint1, intersectionPoint2)) {
			return true;
		} else if (areIdenticalLines(side1Params, side2Params, sideCExtraParam)) {
			intersectionPoint1.x = side1StartVertex.x; // TODO mutate x,y
			intersectionPoint1.y = side1StartVertex.y;
			intersectionPoint2.x = side1EndVertex.x;
			intersectionPoint2.y = side1EndVertex.y;
			return true;
		}

		return false;
	}

	/**
	 * Check if the given lines are identical or not
	 *
	 * The lines are specified as: ax + by + c = 0 OR ax + by + c (+/-)
	 * sideCExtraParam = 0
	 *
	 * @param side1Params     Vector containing the values of a, b and c for side 1
	 * 
	 * @param side2Params     Vector containing the values of a, b and c for side 2
	 * 
	 * @param sideCExtraParam Extra parameter for the flush edge C
	 */
	boolean areIdenticalLines(final List<Double> side1Params, final List<Double> side2Params, double sideCExtraParam) {
		return ((areIdenticalLines(side1Params.get(0), side1Params.get(1), -(side1Params.get(2)), side2Params.get(0),
				side2Params.get(1), -(side2Params.get(2)) - sideCExtraParam))
				|| (areIdenticalLines(side1Params.get(0), side1Params.get(1), -(side1Params.get(2)), side2Params.get(0),
						side2Params.get(1), -(side2Params.get(2)) + sideCExtraParam)));
	}

	/**
	 * Check if the given lines intersect or not. If the lines intersect find //
	 * their intersection points.
	 *
	 * The lines are specified as: ax + by + c = 0 OR ax + by + c (+/-)
	 * sideCExtraParam = 0
	 *
	 * @param side1Params        Vector containing the values of a, b and c for side
	 *                           1
	 * 
	 * @param side2Params        Vector containing the values of a, b and c for side
	 *                           2
	 * 
	 * @param sideCExtraParam    Extra parameter for the flush edge C
	 * 
	 * @param intersectionPoint1 The first intersection point, if it exists
	 * 
	 * @param intersectionPoint2 The second intersection point, if it exists
	 */
	boolean areIntersectingLines(final List<Double> side1Params, final List<Double> side2Params, double sideCExtraParam,
			Coordinate intersectionPoint1, Coordinate intersectionPoint2) {
		return ((lineIntersection(side1Params.get(0), side1Params.get(1), -(side1Params.get(2)), side2Params.get(0),
				side2Params.get(1), -(side2Params.get(2)) - sideCExtraParam, intersectionPoint1))
				&& (lineIntersection(side1Params.get(0), side1Params.get(1), -(side1Params.get(2)), side2Params.get(0),
						side2Params.get(1), -(side2Params.get(2)) + sideCExtraParam, intersectionPoint2)));
	}

	/**
	 * Get the line equation parameters "a", "b" and "c" for the line determined //
	 * by points "p" and "q"
	 *
	 * The equation of the line is considered in the general form: ax + by + c = 0
	 *
	 * @param p One point for defining the equation of the line
	 * 
	 * @param q Second point for defining the equation of the line
	 */
	List<Double> lineEquationParameters(final Coordinate p, final Coordinate q) { // TODO CHANGE TO ARRAY
		List<Double> lineEquationParameters = new ArrayList<Double>();

		double[] out = lineEquationDeterminedByPoints(p, q);
		double a = out[0];
		double b = out[1];
		double c = out[2];

		lineEquationParameters.add(a);
		lineEquationParameters.add(b);
		lineEquationParameters.add(c);

		return lineEquationParameters;
	}

	/**
	 * Compute the height of the point
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygonPoint Polygon point
	 * 
	 * @param polygon      The polygon representing the convex hull of the points
	 * 
	 * @param nrOfPoints   Number of points defining the convex polygon
	 * 
	 * @param c            Index c
	 */
	double height(final Coordinate polygonPoint, final List<Coordinate> polygon, int nrOfPoints, int c) {
		Coordinate pointC = polygon.get(c);
		Coordinate pointCPredecessor = polygon.get(predecessor(c, nrOfPoints));

		return distanceFromPointToLine(polygonPoint, pointC, pointCPredecessor);
	}

	/**
	 * Compute the height of the point specified by the given index
	 *
	 * See paper .get(2) for more details
	 *
	 * @param polygonPointIndex Index of the polygon point
	 * 
	 * @param polygon           The polygon representing the convex hull of the
	 *                          points
	 * 
	 * @param nrOfPoints        Number of points defining the convex polygon
	 * 
	 * @param c                 Index c
	 */
	double height(MutableInt polygonPointIndex, final List<Coordinate> polygon, int nrOfPoints, MutableInt c) {
		Coordinate pointC = polygon.get(c.value);
		Coordinate pointCPredecessor = polygon.get(predecessor(c.value, nrOfPoints));

		Coordinate polygonPoint = polygon.get(polygonPointIndex.value);

		return distanceFromPointToLine(polygonPoint, pointC, pointCPredecessor);
	}

	private static double height(int polygonPointIndex, final List<Coordinate> polygon, int nrOfPoints, int c) {
		Coordinate pointC = polygon.get(c);
		Coordinate pointCPredecessor = polygon.get(predecessor(c, nrOfPoints));

		Coordinate polygonPoint = polygon.get(polygonPointIndex);

		return distanceFromPointToLine(polygonPoint, pointC, pointCPredecessor);
	}

	/**
	 * Advance the given index with one position
	 * 
	 * @param index      Index of the point
	 * 
	 * @param nrOfPoints Number of points defining the convex polygon
	 */
	private void advance(MutableInt index, int nrOfPoints) {
		index.setValue(successor(index.value, nrOfPoints));
	}

	/**
	 * Return the successor of the provided point index
	 *
	 * The successor of the last polygon point is the first polygon point (circular
	 * referencing)
	 *
	 * @param index      Index of the point
	 * 
	 * @param nrOfPoints Number of points defining the convex polygon
	 */
	private static int successor(int index, int nrOfPoints) {
		return ((index + 1) % nrOfPoints);
	}

	/**
	 * Return the predecessor of the provided point index
	 *
	 * The predecessor of the first polygon point is the last polygon point
	 * (circular referencing)
	 *
	 * @param index      Index of the point
	 * 
	 * @param nrOfPoints Number of points defining the convex polygon
	 */
	private static int predecessor(int index, int nrOfPoints) {
		return (index == 0) ? (nrOfPoints - 1) : (index - 1);
	}

	/**
	 * Check if the flush edge angle/opposite angle lie between the predecessor //
	 * and successor angle
	 *
	 * Check if the angle of the flush edge or its opposite angle lie between the
	 * angle of the predecessor and successor
	 *
	 * @param angleFlushEdge Angle of the flush edge
	 * 
	 * @param anglePred      Angle of the predecessor
	 * 
	 * @param angleSucc      Angle of the successor
	 */
	boolean isFlushAngleBtwPredAndSucc(double angleFlushEdge, double anglePred, double angleSucc) {
		if (isAngleBetweenNonReflex(angleFlushEdge, anglePred, angleSucc)) {
			return true;
		} else if (isOppositeAngleBetweenNonReflex(angleFlushEdge, anglePred, angleSucc)) {
			angleFlushEdge = oppositeAngle(angleFlushEdge);

			return true;
		}
		return false;
	}

	/**
	 * Check if the angle of the line (gamma(p) p) or its opposite angle is equal //
	 * to the given angle
	 *
	 *
	 * 
	 * @param gammaAngle Angle of the line (gamma(p) p)
	 * 
	 * @param angle      Angle to compare against
	 */
	boolean isGammaAngleEqualTo(double gammaAngle, double angle) {
		return (almostEqual(gammaAngle, angle));
	}

	/**
	 * Check if the angle of the line (gamma(p) p) or its opposite angle lie //
	 * between angle1 and angle2
	 *
	 *
	 * 
	 * @param gammaAngle Angle of the line (gamma(p) p)
	 * 
	 * @param angle1     One of the boundary angles
	 * 
	 * @param angle2     Another boundary angle
	 */
	boolean isGammaAngleBtw(double gammaAngle, double angle1, double angle2) {
		return (isAngleBetweenNonReflex(gammaAngle, angle1, angle2));
	}

	/**
	 * Get the angle of the line measured from the Ox axis in counterclockwise //
	 * direction
	 *
	 * The line is specified by points "a" and "b". The value of the angle is
	 * expressed in degrees.
	 *
	 * @param a Point a
	 * 
	 * @param b Point b
	 */
	private static double angleOfLineWrtOxAxis(final Coordinate a, final Coordinate b) {
		double y = b.y - a.y;
		double x = b.x - a.x;

		double angle = (Math.atan2(y, x) * 180 / Math.PI);

		return (angle < 0) ? (angle + 360) : angle;
	}

	/**
	 * Check if angle1 lies between non reflex angle determined by angles 2 and 3
	 *
	 *
	 * 
	 * @param angle1 The angle which lies between angle2 and angle3 or not
	 * 
	 * @param angle2 One of the boundary angles
	 * 
	 * @param angle3 The other boundary angle
	 */
	boolean isAngleBetweenNonReflex(double angle1, double angle2, double angle3) {
		if (Math.abs(angle2 - angle3) > 180) {
			if (angle2 > angle3) {
				return (((angle2 < angle1) && (lessOrEqual(angle1, 360)))
						|| ((lessOrEqual(0, angle1)) && (angle1 < angle3)));
			} else {
				return (((angle3 < angle1) && (lessOrEqual(angle1, 360)))
						|| ((lessOrEqual(0, angle1)) && (angle1 < angle2)));
			}
		} else {
			return isAngleBetween(angle1, angle2, angle3);
		}
	}

	/**
	 * Check if the opposite of angle1, ((angle1 + 180) % 360), lies between non //
	 * reflex angle determined by angles 2 and 3
	 *
	 *
	 * 
	 * @param angle1 The angle which lies between angle2 and angle3 or not
	 * 
	 * @param angle2 One of the boundary angles
	 * 
	 * @param angle3 The other boundary angle
	 */
	boolean isOppositeAngleBetweenNonReflex(double angle1, double angle2, double angle3) {
		double angle1Opposite = oppositeAngle(angle1);
		return (isAngleBetweenNonReflex(angle1Opposite, angle2, angle3));
	}

	/**
	 * Check if angle1 lies between angles 2 and 3
	 *
	 *
	 * 
	 * @param angle1 The angle which lies between angle2 and angle3 or not
	 * 
	 * @param angle2 One of the boundary angles
	 * 
	 * @param angle3 The other boundary angle
	 */
	private static boolean isAngleBetween(double angle1, double angle2, double angle3) {
		if ((((int) (angle2 - angle3)) % 180) > 0) {
			return ((angle3 < angle1) && (angle1 < angle2));
		} else {
			return ((angle2 < angle1) && (angle1 < angle3));
		}
	}

	/**
	 * Return the angle opposite to the given angle
	 *
	 * if (angle < 180) then return (angle + 180); else return (angle - 180); endif
	 *
	 * @param angle Angle
	 */
	private static double oppositeAngle(double angle) {
		return (angle > 180) ? (angle - 180) : (angle + 180);
	}

	/**
	 * Compute the distance from a point "a" to a line specified by two points "B"
	 * // and "C"
	 *
	 * Formula used:
	 *
	 * |(x_c - x_b) * (y_b - y_a) - (x_b - x_a) * (y_c - y_b)| d =
	 * ------------------------------------------------------- sqrt(((x_c - x_b)^2)
	 * + ((y_c - y_b)^2))
	 *
	 * Reference: http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html
	 * (Last access: 15.09.2013)
	 *
	 * @param a          Point from which the distance is measures
	 * 
	 * @param linePointB One of the points determining the line
	 * 
	 * @param linePointC One of the points determining the line
	 */
	private static double distanceFromPointToLine(final Coordinate a, final Coordinate linePointB,
			final Coordinate linePointC) {
		double term1 = linePointC.x - linePointB.x;
		double term2 = linePointB.y - a.y;
		double term3 = linePointB.x - a.x;
		double term4 = linePointC.y - linePointB.y;

		double nominator = Math.abs((term1 * term2) - (term3 * term4));
		double denominator = Math.sqrt((term1 * term1) + (term4 * term4));

		return (denominator != 0) ? (nominator / denominator) : 0;
	}

	/**
	 * Compute the distance between two points
	 *
	 * Compute the Euclidean distance between two points
	 *
	 * @param a Point a
	 * 
	 * @param b Point b
	 */
	double distanceBtwPoints(final Coordinate a, final Coordinate b) {
		double xDiff = a.x - b.x;
		double yDiff = a.y - b.y;

		return Math.sqrt((xDiff * xDiff) + (yDiff * yDiff));
	}

	/**
	 * Compute the area of a triangle defined by three points
	 *
	 * The area is computed using the determinant method. An example is depicted at
	 * http://demonstrations.wolfram.com/TheAreaOfATriangleUsingADeterminant/ (Last
	 * access: 15.09.2013)
	 *
	 * @param a Point a
	 * 
	 * @param b Point b
	 * 
	 * @param c Point c
	 */
	private static double areaOfTriangle(final Coordinate a, final Coordinate b, final Coordinate c) {
		double posTerm = (a.x * b.y) + (a.y * c.x) + (b.x * c.y);
		double negTerm = (b.y * c.x) + (a.x * c.y) + (a.y * b.x);

		double determinant = posTerm - negTerm;

		return Math.abs(determinant) / 2d;
	}

	/**
	 * Get the point in the middle of the segment determined by points "a" and "b"
	 * 
	 * @param a Point a
	 * 
	 * @param b Point b
	 */
	private static Coordinate middlePoint(final Coordinate a, final Coordinate b) {
		double middleX = (a.x + b.x) / 2d;
		double middleY = (a.y + b.y) / 2d;
		return new Coordinate(middleX, middleY);
	}

	/**
	 * Determine the intersection point of two lines, if this point exists
	 *
	 * Two lines intersect if they are not parallel (Parallel lines intersect at +/-
	 * infinity, but we do not consider this case here).
	 *
	 * The lines are specified in the following form: A1x + B1x = C1 A2x + B2x = C2
	 *
	 * If det (= A1*B2 - A2*B1) == 0, then lines are parallel else they intersect
	 *
	 * If they intersect, then let us denote the intersection point with P(x, y)
	 * where: x = (C1*B2 - C2*B1) / (det) y = (C2*A1 - C1*A2) / (det)
	 *
	 * @param a1           A1
	 * 
	 * @param b1           B1
	 * 
	 * @param c1           C1
	 * 
	 * @param a2           A2
	 * 
	 * @param b2           B2
	 * 
	 * @param c2           C2
	 * 
	 * @param intersection The intersection point, if this point exists (mutates)
	 */
	private static boolean lineIntersection(double a1, double b1, double c1, double a2, double b2, double c2,
			Coordinate intersection) {
		double det = (a1 * b2) - (a2 * b1);

		if (!(almostEqual(det, 0))) {
			intersection.x = ((c1 * b2) - (c2 * b1)) / (det);
			intersection.y = ((c2 * a1) - (c1 * a2)) / (det);
			return true;
		}

		return false;
	}

	/**
	 * Determine the intersection point of two lines, if this point exists
	 *
	 * Two lines intersect if they are not parallel (Parallel lines intersect at +/-
	 * infinity, but we do not consider this case here).
	 *
	 * The lines are specified by a pair of points each. If they intersect, then the
	 * function returns true, else it returns false.
	 *
	 * Lines can be specified in the following form: A1x + B1x = C1 A2x + B2x = C2
	 *
	 * If det (= A1*B2 - A2*B1) == 0, then lines are parallel else they intersect
	 *
	 * If they intersect, then let us denote the intersection point with P(x, y)
	 * where: x = (C1*B2 - C2*B1) / (det) y = (C2*A1 - C1*A2) / (det)
	 *
	 * @param a1           First point for determining the first line
	 * 
	 * @param b1           Second point for determining the first line
	 * 
	 * @param a2           First point for determining the second line
	 * 
	 * @param b2           Second point for determining the second line
	 * 
	 * @param intersection The intersection point, if this point exists
	 */
	private static boolean lineIntersection(final Coordinate a1, final Coordinate b1, final Coordinate a2,
			final Coordinate b2, Coordinate intersection) {
		double A1 = b1.y - a1.y;
		double B1 = a1.x - b1.x;
		double C1 = (a1.x * A1) + (a1.y * B1);

		double A2 = b2.y - a2.y;
		double B2 = a2.x - b2.x;
		double C2 = (a2.x * A2) + (a2.y * B2);

		double det = (A1 * B2) - (A2 * B1);

		if (!almostEqual(det, 0)) {
			intersection.x = ((C1 * B2) - (C2 * B1)) / det;
			intersection.y = ((C2 * A1) - (C1 * A2)) / det;
			return true;
		}

		return false;
	}

	/**
	 * Get the values of "a", "b" and "c" of the line equation ax + by + c = 0 //
	 * knowing that point "p" and "q" are on the line
	 *
	 * a = q.y - p.y b = p.x - q.x c = - (p.x * a) - (p.y * b)
	 *
	 * @param p Point p
	 * 
	 * @param q Point q
	 * 
	 * @param a Parameter "a" from the line equation
	 * 
	 * @param b Parameter "b" from the line equation
	 * 
	 * @param c Parameter "c" from the line equation
	 */
	double[] lineEquationDeterminedByPoints(final Coordinate p, final Coordinate q) {
//		CV_Assert(areEqualPoints(p, q) == false);

		double a = q.y - p.y;
		double b = p.x - q.x;
		double c = ((-p.y) * b) - (p.x * a);
		return new double[] { a, b, c };
	}

	/**
	 * Check if p1 and p2 are on the same side of the line determined by points a //
	 * and b
	 *
	 *
	 * 
	 * @param p1 Point p1
	 * 
	 * @param p2 Point p2
	 * 
	 * @param a  First point for determining line
	 * 
	 * @param b  Second point for determining line
	 */
	boolean areOnTheSameSideOfLine(final Coordinate p1, final Coordinate p2, final Coordinate a, final Coordinate b) {

		double[] out = lineEquationDeterminedByPoints(a, b);
		double a1 = out[0];
		double b1 = out[1];
		double c1 = out[2];

		double p1OnLine = (a1 * p1.x) + (b1 * p1.y) + c1;
		double p2OnLine = (a1 * p2.x) + (b1 * p2.y) + c1;

		return (sign(p1OnLine) == sign(p2OnLine));
	}

	/**
	 * Check if one point lies between two other points
	 *
	 *
	 * 
	 * @param point            Point lying possibly outside the line segment
	 * 
	 * @param lineSegmentStart First point determining the line segment
	 * 
	 * @param lineSegmentEnd   Second point determining the line segment
	 */
	boolean isPointOnLineSegment(final Coordinate point, final Coordinate lineSegmentStart,
			final Coordinate lineSegmentEnd) {
		double d1 = distanceBtwPoints(point, lineSegmentStart);
		double d2 = distanceBtwPoints(point, lineSegmentEnd);
		double lineSegmentLength = distanceBtwPoints(lineSegmentStart, lineSegmentEnd);

		return (almostEqual(d1 + d2, lineSegmentLength));
	}

	/**
	 * Check if two lines are identical
	 *
	 * Lines are be specified in the following form: A1x + B1x = C1 A2x + B2x = C2
	 *
	 * If (A1/A2) == (B1/B2) == (C1/C2), then the lines are identical else they are
	 * not
	 *
	 * @param a1 A1
	 * 
	 * @param b1 B1
	 * 
	 * @param c1 C1
	 * 
	 * @param a2 A2
	 * 
	 * @param b2 B2
	 * 
	 * @param c2 C2
	 */
	boolean areIdenticalLines(double a1, double b1, double c1, double a2, double b2, double c2) {
		double a1B2 = a1 * b2;
		double a2B1 = a2 * b1;
		double a1C2 = a1 * c2;
		double a2C1 = a2 * c1;
		double b1C2 = b1 * c2;
		double b2C1 = b2 * c1;

		return ((almostEqual(a1B2, a2B1)) && (almostEqual(b1C2, b2C1)) && (almostEqual(a1C2, a2C1)));
	}

	/**
	 * Check if points point1 and point2 are equal or not
	 *
	 *
	 * 
	 * @param point1 One point
	 * 
	 * @param point2 The other point
	 */
	boolean areEqualPoints(final Coordinate point1, final Coordinate point2) {
		return (almostEqual(point1.x, point2.x) && almostEqual(point1.y, point2.y));
	}

	/**
	 * Return the sign of the number
	 *
	 * The sign function returns: -1, if number < 0 +1, if number > 0 0, otherwise
	 */
	private static int sign(double number) {
		return (number > 0) ? 1 : ((number < 0) ? -1 : 0);
	}

	/**
	 * Return the maximum of the provided numbers
	 */
	private static double maximum(double number1, double number2, double number3) {
		return Math.max(Math.max(number1, number2), number3);
	}

	/**
	 * Check if the two numbers are equal (almost)
	 *
	 * The expression for determining if two real numbers are equal is: if (Abs(x -
	 * y) <= EPSILON * Max(1.0f, Abs(x), Abs(y))).
	 *
	 * @param number1 First number
	 * 
	 * @param number2 Second number
	 */
	private static boolean almostEqual(double number1, double number2) {
		return (Math.abs(number1 - number2) <= (EPSILON * maximum(1.0, Math.abs(number1), Math.abs(number2))));
	}

	/**
	 * Check if the first number is greater than or equal to the second number
	 *
	 *
	 * 
	 * @param number1 First number
	 * 
	 * @param number2 Second number
	 */
	private static boolean greaterOrEqual(double number1, double number2) {
		return ((number1 > number2) || (almostEqual(number1, number2)));
	}

	/**
	 * Check if the first number is less than or equal to the second number
	 *
	 *
	 * 
	 * @param number1 First number
	 * 
	 * @param number2 Second number
	 */
	private static boolean lessOrEqual(double number1, double number2) {
		return ((number1 < number2) || (almostEqual(number1, number2)));
	}
	private class MutableInt {

		int value;

		public MutableInt(int value) {
			this.value = value;
		}

		public int getValue() {
			return this.value;
		}

		public void setValue(int value) {
			this.value = value;
		}

		public void inc() {
			this.value++;
		}
	}

}