Java의 극점 각도로 점 정렬

Question

그레이엄 스캔 알고리즘을 사용하여 점 집합의 볼록 선체를 찾습니다. 극점 각도로 점을 정렬하려고하는데 어떻게해야하는지 잘 모릅니다. (나는 이미 Y 좌표로 점 집합을 정렬했다.) 이미 쓴 적이 무엇

은 다음과 같이이다 :

나는 X와 Y가 double으로 좌표가 어디 Coord 클래스입니다

public double angle(Coord o, Coord a) 
{ 
    return Math.atan((double)(a.y - o.y)/(double)(a.x - o.x)); 
} 

.

나는 Stack Overflow의 비슷한 게시물 중 누군가가 C++로이 각도를 구현하려고했지만 비슷한 것을 이해하지 못했다. qsqrt. 우리는 자바에서 이와 비슷한 것을 가지고 있습니까?

qreal Interpolation::dp(QPointF pt1, QPointF pt2) 
{ 
    return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y())); 
} 

누구든지 나를 도울 수 있으면 기쁠 것입니다.

Answer 1

극좌표를 계산할 필요가 없습니다. trig 함수는 사분면 내에서 단조롭기 때문에 (항상 증가하거나 항상 감소 함), 함수 자체로 정렬하면됩니다. 당신 사건의 황갈색. 그레이엄 스캔을 최하 지점부터 시작하여 구현하는 경우 처음 두 사분면 만 살펴 봐야하므로 두 사분면보다 단조롭기 때문에 코탄으로 정렬하는 것이 가장 쉽습니다.

다른 말로하면 - (x - x1)/(y - y1) (여기서 (x1, y1)은 출발점의 좌표 임)으로 정렬 할 수 있으며 계산이 더 빨라집니다. 먼저 y == y1이있는 포인트를 분리하여 (x - x1)`기호에 따라 목록의 상단 또는 하단에 추가해야하지만 식별하기 쉽습니다. 왜냐하면 이미 시작점을 찾기 위해 y로 정렬.

Answer 2

Math.atan()은 -pi/2에서 pi/2 사이의 각도를 반환합니다. 다른 두 좌표에 대한 결과를 조정해야합니다.

볼록 선체 중앙에서 각을 구하려면 먼저 centroid이 원점이되도록 좌표를 변환해야합니다.

Answer 3

위에서 언급했듯이, 극각 자체를 계산하는 것은 일들에 대해가는 아주 엉성한 방법입니다. 간단한 비교자를 정의하고 교차 곱을 사용하여 극각으로 정렬 할 수 있습니다. 여기에 (I 스캔 내 자신의 그레이엄을 위해 사용하는) C++ 코드입니다 :

struct Point { 
    int x, y; 
} 

int operator^(Point p1, Point p2) { 
    return p1.x * p2.y - p1.y * p2.x; 
} 

bool operator<(Point p1, Point p2) 
{ 
    if(p1.y == 0 && p1.x > 0) 
     return true; //angle of p1 is 0, thus p2 > p1 

    if(p2.y == 0 && p2.x > 0) 
     return false; //angle of p2 is 0 , thus p1 > p2 

    if(p1.y > 0 && p2.y < 0) 
     return true; //p1 is between 0 and 180, p2 between 180 and 360 

    if(p1.y <0 && p2.y > 0) 
     return false; 

    return (p1^p2) > 0; //return true if p1 is clockwise from p2 
} 

당신은 Point 클래스를 정의하여, 자바 같은 일을 구현할 수 있습니다. 기본적으로 교차 제품을 반환하기 위해 ^ 연산자를 오버로드했습니다. 나머지는 분명합니다, 이것이 도움이되기를 바랍니다!