곡선에 100000 포인트가 있다고 가정하십시오. y = x^2. 이 점들의 볼록한 선체를 찾고 싶습니다. 모든 좌표는 부동 소수점 숫자입니다.부동 정밀도 문제가있을 때 어떻게 convex hull을 실제로 풀 수 있습니까?
내 그레이엄 스캔 구현에서 내가 부동 소수점에서 작동하는 유일한 위치는 처음에 모든 점을 좌표로 정렬 한 다음 세 점이 왼쪽 또는 오른쪽으로 회전하는지 여부를 결정하는 한 가지 기능이 있습니다.
포인트 :
struct point {
double x;
double y;
};
정렬 비교 :
inline bool operator() (const point &p1, const point &p2) {
return (p1.x < p2.x) || (p1.x == p2.x && p1.y > p2.y);
}
왼쪽/오른쪽 회전 :
inline int ccw(point *p1, point *p2, point *p3) {
double left = (p1->x - p3->x)*(p2->y - p3->y);
double right = (p1->y - p3->y)*(p2->x - p3->x);
double res = left - right;
return res > 0;
}
내 프로그램 (100 개) 000 점에서 단지 68,894의 일부임을 말한다 볼록한 선체. 그러나 그들이 곡선에 있기 때문에, 그것들 모두는 볼록한 선체의 일부가되어야합니다.
눈에 그것은 별 차이가 없습니다. 아래 그림을 참조하십시오. 빨간색 점은 볼록 선체의 일부입니다.
image http://oi57.tinypic.com/t8lsvs.jpg
하지만 당신은 충분히 가까이보고, 지점을 확대, 당신은 그들 중 일부는 파란색, 그래서 그들은이 볼록 선체에 포함되지 않은 것을 확인할 수 있습니다.
image http://oi61.tinypic.com/2eol37a.jpg
이제 내 초기 가정은 부동 소수점 오류가이 문제를 일으키는된다.
나는 부동 소수점 숫자에 대해 임의의 정밀도를 갖는 외부 라이브러리를 사용할 수 있다고 생각하지만, C++에서 예로 든 간단한 데이터 형식에 더 관심이 있습니다.
어떻게 정확도를 높일 수 있습니까? 나는 엡실론에 대해 읽었지만 어떻게 엡실론을 사용하면 도움이 될까요? 나는 여전히 서로 가깝다는 점을 같기 때문에 100 %에 가까운 정확도를 얻지는 못할 것입니다.
이 문제를 해결하는 가장 좋은 방법은 무엇입니까?
'long double'을 사용해 보셨습니까? – mch
볼록 선체 알고리즘이 올바르지 만 처음에 y = x^2를 평가할 때 반올림이 발생합니까? – ajclinto
먼저, 유한 정밀도는 실수를 나타낼 수 없습니다. 두 번째로, 플롯하는 점은 근사값입니다. 셋째, 진정한 건설적 재판 (무한 정밀)은 당신이 그들을 비교하기 원하는 방식으로 비교 될 수 없습니다. 다섯째, 왜 신경 쓰시겠습니까? (따라서 중요한 문제는 선체에 어떤 목적이 있습니까?) – Yakk