Android 는 다각형 영역 에 있 지 않 은 점 을 어떻게 판단 합 니까?

어떤 사람 이 나 에 게 한 점 이 다각형 안에 있 는 지 아 닌 지 를 어떻게 판단 하 느 냐 고 물 었 다.원래 이 다각형 을 하나의 삼각형 으로 나 누 려 고 했 는데 그림 과 같다.
 
그리고 이 점 이 특정한 삼각형 에 있 는 지 아 닌 지 를 판단 한다.만약 에 있다 면 이 다각형 에 있 을 것 이다.그 문 제 는 다음 에 이 점 이 삼각형 에 있 는 지 아 닌 지 를 판단 하 는 것 으로 바 뀌 었 다.이 점 D 와 삼각형 의 세 점 A,B,C 가 조 합 된 삼각형 a,b,c 의 면적 의 합 이 이 삼각형 의 면적 과 같다 면 이 점 이 삼각형 에 있다 는 것 을 설명 한다.그림 과 같다.

코드 는 다음 과 같 습 니 다:

public boolean isInTriangle(Point A, Point B, Point C, Point P) { 
 double ABC = triAngleArea(A, B, C); 
 double ABp = triAngleArea(A, B, P); 
 double ACp = triAngleArea(A, C, P); 
 double BCp = triAngleArea(B, C, P); 
 if ((int) ABC == (int) (ABp + ACp + BCp)) {//              ，        ,                 （25714.25390625、25714.255859375） 
  return true; 
 } else { 
  return false; 
 } 
} 
 
private double triAngleArea(Point A, Point B, Point C) {//                   
 double result = Math.abs((A.getX() * B.getY() + B.getX() * C.getY() 
   + C.getX() * A.getY() - B.getX() * A.getY() - C.getX() 
   * B.getY() - A.getX() * C.getY()) / 2.0D); 
 return result; 
} 

모든 것 이 그렇게 합 리 적 으로 보이 고 코드 도 다 썼 으 며 테스트 도 다 했 으 니 문제 가 없습니다!그러나 마지막 으로 나 는 한 가지 문 제 를 소홀히 한 것 을 발견 했다.또 하나의 다각형 의 상황 은 고려 하지 못 했다.그것 이 바로 바나나 형의 다각형 이다.그림 과 같다.

이 문제 가 나 오 자마자 나 는 바로 동 그 라 미 를 쳤 다.이것 은 어떻게 해 야 하 는 지,마지막 으로 인터넷 에서 해결 방법 을 찾 았 다.그것 은 바로 이 점 을 따라 평행선 을 만 드 는 것 이다.만약 에 이 점 의 한쪽 과 다각형 이 교차 하 는 점 이 홀수 라면 이 점 이 이 다각형 에 있다 는 것 을 설명 한다.그림 과 같다.

코드 는 다음 과 같 습 니 다:

/** 
 *   ：             ：                      ：       ，  ! 
 * 
 * @param point 
 *          
 * @param APoints 
 *             （        ） 
 * @return 
 */ 
public boolean PtInPolygon(Point point, List<Point> APoints) { 
 int nCross = 0; 
 for (int i = 0; i < APoints.size(); i++) { 
  Point p1 = APoints.get(i); 
  Point p2 = APoints.get((i + 1) % APoints.size()); 
  //    y=p.y   p1p2     
  if (p1.getY() == p2.getY()) // p1p2   y=p0.y   
   continue; 
  if (point.getY() < Math.min(p1.getY(), p2.getY())) //    p1p2     
   continue; 
  if (point.getY() >= Math.max(p1.getY(), p2.getY())) //    p1p2     
   continue; 
  //      X    
  // -------------------------------------------------------------- 
  double x = (double) (point.getY() - p1.getY()) 
    * (double) (p2.getX() - p1.getX()) 
    / (double) (p2.getY() - p1.getY()) + p1.getX(); 
  if (x > point.getX()) 
   nCross++; //         
 } 
 //        ，        --- 
 return (nCross % 2 == 1); 
} 

프로젝트 다운로드:한 점 이 다각형 에 있 는 지 여부
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.