package PbuliClass;
import java.awt.geom.Point2D;
import java.util.List;
/**¸ÃÀàÓÃÓÚÅжϵãÊÇ·ñÔÚ¶à±ßÐÎÄÚ*/
public class IsPtInPoly {
	/** 
	* ÅжϵãÊÇ·ñÔÚ¶à±ßÐÎÄÚ 
	* shapeÐÎ×´
	* @param point ¼ì²âµã 
	* @param pts   ¶à±ßÐεĶ¥µã¼¯ºÏ 
	* @return µãÔÚ¶à±ßÐÎÄÚ·µ»Øtrue,·ñÔò·µ»Øfalse 
	*/  
	public static boolean inPoly(Point2D.Double point, List<Point2D.Double> pts){	   
	   boolean boundOrVertex = true; //Èç¹ûµãλÓÚ¶à±ßÐεĶ¥µã»ò±ßÉÏ£¬Ò²Ëã×öµãÔÚ¶à±ßÐÎÄÚ£¬Ö±½Ó·µ»Øtrue	   
	   int N = pts.size(); 
	   int intersectCount = 0;
	   double precision = 2e-10; //¸¡µãÀàÐͼÆËãʱºòÓë0±È½ÏʱºòµÄÈÝ²î  
	   Point2D.Double p1, p2;
	   Point2D.Double p = point; //µ±Ç°µã  
	     
	   p1 = pts.get(0);   
	   for(int i = 1; i <= N; ++i){      
	       if(p.equals(p1)){  
	           return boundOrVertex;
	       }  
	       p2 = pts.get(i % N);        
	       if(p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)){                
	           p1 = p2;   
	           continue;
	       }  
	         
	       if(p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)){
	           if(p.y <= Math.max(p1.y, p2.y)){                 
	               if(p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)){
	                   return boundOrVertex;  
	               }  
	                 
	               if(p1.y == p2.y){                       
	                   if(p1.y == p.y){
	                       return boundOrVertex;  
	                   }else{
	                       ++intersectCount;  
	                   }   
	               }else{
	                   double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;                       
	                   if(Math.abs(p.y - xinters) < precision){
	                       return boundOrVertex;  
	                   }  
	                     
	                   if(p.y < xinters){ 
	                       ++intersectCount;  
	                   }   
	               }  
	           }  
	       }else{                 
	           if(p.x == p2.x && p.y <= p2.y){                    
	               Point2D.Double p3 = pts.get((i+1) % N);                      
	               if(p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)){
	                   ++intersectCount;  
	               }else{  
	                   intersectCount += 2;  
	               }  
	           }  
	       }              
	       p1 = p2;  
	   }  
	     
	   if(intersectCount % 2 == 0){
	       return false;  
	   } else { 
	       return true;  
	   }  
	    
	}

}