파이썬에서 두 원에 공통 인 모든 정수 점을 어떻게 찾을 수 있습니까?두 원에 공통 인 모든 점 찾기
예를 들어 중심점이 (x1,y1) 및 (x2,y2)이고 반경이 r1=r2 인 두 개의 동등한 크기의 원이 교차하는 벤 다이어그램을 생각해보십시오. 또한 우리는 이미 두 개의 교차점이 (xi1,yi1)과 (xi2,yi2)임을 알고 있습니다.
효율적으로 양쪽 원에 포함 된 모든 점 (x,y)의 목록을 어떻게 생성합니까? 즉, 교차점을 포함하는 상자를 그려서 반복하고, 주어진 점이 두 원 내에 있는지 확인하지만 더 좋은 방법이 있습니까?
그래서 두 원 안에있는 격자 점을 찾고 싶습니까?
박스를 그리는 방법과 상자의 모든 포인트를 반복하는 방법은 나에게 가장 단순한 것 같습니다. 상자의 점 수가 교차점의 점 수와 비교되는 한 효율적일 것입니다.
가능한 한 효율적이지 않더라도 실제 병목 현상이라고 생각할 충분한 이유가 생길 때까지는 최적화하지 마십시오.
예, 격자 점이 더 적절한 용어 일 것입니다 - "두 개의 교차하는 원에있는 직사각형 격자 점"으로가 보겠습니다. 병목 현상이 아니지만 본질적으로이 기능이 반복되고 있습니다. 제외 할 점수의 수는 중요 할 것입니다. –
여기에는 네 가지 사례가 있습니다.
질문에서 분명히 네 번째 경우에만 적용됩니다. – SilentGhost
명시된 가정은 그것을 암시하지만, 고려되지 않은 다른 가능성을 나열하는 데있어 잘못된 점은 무엇입니까? –
* 또한 우리는 이미 원의 교차점 두 개가'(xi1, yi1)'과'(xi2, yi2) '임을 알고 있습니다. * 어떻게 * * 고려해 볼 수 있습니까? – SilentGhost
그래픽 개발에 사용되는 다양한 클리핑 알고리즘을 살펴볼 수도 있습니다. 나는 당신이 여기에서 묻고있는 것과 비슷한 많은 문제를 해결하기 위해 클리핑 알고리즘을 사용했다.
서클의 위치와 반경이 그리드보다 작은 입도로 다를 수 있다면 어쨌든 여러 개의 점을 확인할 것입니다.
검색 영역을 적절하게 정의하여 검사 할 포인트 수를 최소화 할 수 있습니다. 이 교점 사이의 거리와 동일한 폭 및 D 두 센터와 분리되는
r1 + r2 - D
동일한 높이를 갖는다. 이 사각형은 일반적으로 X 및 Y 축과 정렬되지 않습니다. 두 개의 원이 교차하는지 여부에 대한 테스트도 제공됩니다.
실제로이 점의 절반 만 확인하면됩니다.반지름이 같으면 1/4의 반지름 만 확인하면됩니다. 문제의 대칭성이 당신을 도와줍니다.
그러나이 'w X h'사각형은 사용을 피하려고하는 "상자"입니다. 나는 대칭을 사용한다는 생각을 좋아하지 만, 그것은 나에게 일어나지 않았다. –
"모든 포인트"는 "모든 픽셀"을 의미합니다. 귀하의 디스플레이가 NY 픽셀로 NX라고 가정합니다. 배열이 두 개 있습니다.
int x0[NY], x1[NY]; initially full of -1.
교차점은 두 곡선 사이에서 마름모 모양입니다. 각 곡선을 따라 x, y 값을 반복합니다. 각 y 값 (즉, 곡선이 y + 0.5를 횡단하는 위치)에서 x 값을 배열에 저장합니다. x0 [y]가 -1이면 x0에 저장하고, x1에 저장합니다.
y의 최소값과 최대 값도 추적하십시오.
완료되면 y 값을 반복하고 각 y에서 x0과 x1 사이의 x 값, 즉 for (ix = x0[iy]; ix < x1[iy]; ix++) (또는 그 반대로)을 반복합니다.
픽셀은 x와 y가 정수인 점이 아니라는 점을 이해하는 것이 중요합니다. 오히려 픽셀은 그리드 선 사이의 작은 사각형입니다. 이렇게하면 가장자리에 문제가 생기는 것을 막을 수 있습니다.
거의 다 왔어. 상자 안의 점들을 반복하는 것은 상당히 좋지만, 두 번째 좌표의 경우 한계 사이에서 직접 반복하는 것이 좋습니다.
먼저 x 축을 따라 반복하고, y 축에 대해 경계 상자 좌표 사이를 반복하는 대신 각 원이 x 선과 교차하는 위치를 알아내는 것이 좋습니다. 더 구체적으로 교차점의 y 좌표에 관심이 있습니다. 그 사이를 반복하십시오 (반올림에주의하십시오)
당신이 이미 원 안에 있다고 알고 있기 때문에, 당신은 수표를 완전히 건너 뛸 수 있습니다. 포인트가 많으면 많은 수표를 건너 뛰고 성능이 약간 향상 될 수 있습니다.
추가 개선 사항으로 교차점을 계산해야하는 횟수를 최소화하기 위해 x 축 또는 y 축을 선택할 수 있습니다.
모든 점을 말하면 모든 정수 점을 의미합니다. 수학적으로 당신은 무한한 수의 포인트에 대해서 이야기하고 있습니다. – Ukko
예, 미안합니다. 정수 값입니다. 명확성을 위해 편집 됨. –