/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2012 Excensus LLC.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Licence as published
 * by the Free Software Foundation. 
 * See the COPYING file for more information.
 *
 **********************************************************************
 *
 * Last port: triangulate/quadedge/TrianglePredicate.java r524
 *
 **********************************************************************/

#ifndef GEOS_TRIANGULATE_QUADEDGE_TRIANGLEPREDICATE_H
#define GEOS_TRIANGULATE_QUADEDGE_TRIANGLEPREDICATE_H

namespace geos {
namespace geom { // geos.geom

class Coordinate;

/**
 * Algorithms for computing values and predicates
 * associated with triangles.
 * For some algorithms extended-precision
 * implementations are provided, which are more robust
 * (i.e. they produce correct answers in more cases).
 * Also, some more robust formulations of
 * some algorithms are provided, which utilize
 * normalization to the origin.
 * 
 * @author JTS: Martin Davis
 * @author Benjamin Campbell
 *
 */
class TrianglePredicate 
{
public:
  /**
   * Tests if a point is inside the circle defined by 
   * the triangle with vertices a, b, c (oriented counter-clockwise). 
   * This test uses simple
   * double-precision arithmetic, and thus may not be robust.
   * 
   * @param a a vertex of the triangle
   * @param b a vertex of the triangle
   * @param c a vertex of the triangle
   * @param P the point to test
   * @return true if this point is inside the circle defined by the points a, b, c
   */
  static bool isInCircleNonRobust(
	  const Coordinate &a, const Coordinate &b, const Coordinate &c, 
	  const Coordinate &p);
  
  /**
   * Tests if a point is inside the circle defined by 
   * the triangle with vertices a, b, c (oriented counter-clockwise). 
   * This test uses simple
   * double-precision arithmetic, and thus is not 10% robust.
   * However, by using normalization to the origin
   * it provides improved robustness and increased performance.
   * <p>
   * Based on code by J.R.Shewchuk.
   * 
   * 
   * @param a a vertex of the triangle
   * @param b a vertex of the triangle
   * @param c a vertex of the triangle
   * @param P the point to test
   * @return true if this point is inside the circle defined by the points a, b, c
   */
  static bool isInCircleNormalized(
	  const Coordinate &a, const Coordinate &b, const Coordinate &c, 
	  const Coordinate &p);

private: 
  /**
   * Computes twice the area of the oriented triangle (a, b, c), i.e., the area is positive if the
   * triangle is oriented counterclockwise.
   * 
   * @param a a vertex of the triangle
   * @param b a vertex of the triangle
   * @param c a vertex of the triangle
   */
  static double triArea(const Coordinate &a,
		  const Coordinate &b, const Coordinate &c);

public:
  /**
   * Tests if a point is inside the circle defined by 
   * the triangle with vertices a, b, c (oriented counter-clockwise). 
   * This method uses more robust computation.
   * 
   * @param a a vertex of the triangle
   * @param b a vertex of the triangle
   * @param c a vertex of the triangle
   * @param P the point to test
   * @return true if this point is inside the circle defined by the points a, b, c
   */
  static bool isInCircleRobust(
	  const Coordinate &a, const Coordinate &b, const Coordinate &c, 
	  const Coordinate &p);
} ;

} // namespace geos.geom
} // namespace geos

#endif //GEOS_TRIANGULATE_QUADEDGE_TRIANGLEPREDICATE_H

