import Jcg.geometry.*;
import Jcg.geometry.kernel.FilteredPredicates_2;
import Jcg.geometry.kernel.GeometricPredicates_2;
import Jcg.mesh.*;
import Jcg.polyhedron.*;
import Jcg.pointLocation.*;
import Jcg.viewer.old.*;

/**
 * Point location in planar triangulations via random walk. <br>
 * Remark: the planar triangulation is implemented using the half-edge data structure (Polyhedron_3<Point_2> class)
 * 
 * @author Luca Castelli Aleardi, Ecole Polytechnique (INF562)
 * @version 2012-2026
 */
public class PointLocationInTriangulations implements PlanarPointLocation {
 
	/** Predicates used to perform geometric computations and tests (approximate, exact or filtered computations) */
	static GeometricPredicates_2 predicates;
	
	PointLocationInTriangulations() {
		predicates=new FilteredPredicates_2();
		//predicates=new ApproximatePredicates_2();
		//predicates=new ExactPredicates_2();		
	}
    
    /**
     * Returns the barycenter point of a face randomly chosen
     */    
    public static Point_2 getRandomPoint(Polyhedron_3<Point_2> polyhedron){
    	Face<Point_2> randomFace=getRandomFace(polyhedron);
    	return createCenterVertex(randomFace);
    }

    /**
     * Returns a face randomly chosen
     */    
    public static Face<Point_2> getRandomFace(Polyhedron_3<Point_2> polyhedron){
    	int nFaces=polyhedron.sizeOfFacets();
    	int randomIndex=(int)(nFaces*Math.random());
    	return polyhedron.facets.get(randomIndex);
    }

    /**
     * Compute and return the barycenter point of a given face
     */    
    public static Point_2 createCenterVertex(Face<Point_2> f){
    	int degree=f.degree();
    	Point_2[] neighbors=new Point_2[degree];
    	
    	Halfedge<Point_2> e=f.getEdge();
    	neighbors[0]=(Point_2)e.getVertex().getPoint();
    	for(int i=1;i<degree;i++)   {
    		e=e.getNext();
    		neighbors[i]=(Point_2)e.getVertex().getPoint();
    	}
    	Point_2 centerVertex;
    	centerVertex=new Point_2();
    	centerVertex.barycenter(neighbors);
    	return centerVertex;
    }
    
    /**
     * Compute and return the first edge intersected by segment (p1, p2), inside face f. <br>
     * 
     * @param p1  	the origin point (assumed to be inside face 'f')
     * @param p2  	the query point
     * @param f 	a face which is assumed to contain point p1
     * 
     * @return  	the halfedge (contained in face 'f') which is intersected by the segment (p1, p2)
     */    
    public static Halfedge<Point_2> getFirstIntersectedEdge(Face<Point_2> f, Point_2 p1, Point_2 p2) {
    	throw new Error("TO BE COMPLETED: exercise");
   }

    /**
     * Compute and return the half-edge 'h' intersected by segment (p1, p2), which inside the face 'f' defined by half-edge 'first'.
     * 
     * @param first  	input half-edge (incident to a face 'f')
     * @param p1  		the origin point
     * @param p2  		the query point
     * @return  		the half-edge 'h' intersected by segment (p1, p2), and different from 'first'. 
     * 					The result is 'null whether there in no other intersected half-edge.
     */    
    public static Halfedge<Point_2> getNextIntersectedEdge(Halfedge<Point_2> first, Point_2 p1, Point_2 p2) {
    	throw new Error("TO BE COMPLETED: exercise");
   }

    /**
     * Compute and return the face containing the query point 'p2'. <br>
     * The random walk starts from the (randomly chosen) point 'p1'.
     * The 'first' half-edge is incident (and inside) to the face 'f' containing 'p1'.
     * 
     * @param first  	input half-edge (incident to a face 'f')
     * @param p1  		the origin point
     * @param p2  		the query point
     * @return    		an half-edge incident (inside) the face 'f' that contains 'p2'
     */    
    public static Halfedge<Point_2> locatePoint(Halfedge<Point_2> first, Point_2 p1, Point_2 p2) {
    	throw new Error("TO BE COMPLETED: exercise");
   }

    /**
     * Locate the query point in the triangulation.
     * 
     * @param triangulation  	input triangulation (represented using half-edge data structure)
     * @param queryPoint   		input query point
     */    
    public Halfedge<Point_2> locatePoint(Polyhedron_3<Point_2> triangulation, Point_2 queryPoint) {
    	throw new Error("TO BE COMPLETED: exercise");
   }
    
}