Strona główna » Algorytmy » Artykuły » Punkty w Kole
 

Punkty w Kole

Zadanie

Znajdź wszystkie punkty o całkowitych współrzędnych, które znajdują się wewnątrz koła znajdującego się w punkcie (0, 0) i o pewnym promieniu r. Algorytm powinien zwrócić ile takich punktów jest.

Przykład

Poniżej zostały przedstawione przykładowe koła o podanych promieniach r oraz zaznaczone punkty na siatce o całkowitych współrzędnych, które się mieszczą w kole.

r = 1, 5 punktów
r = sqrt(2) = 1.414.., 9 punktów
r = 2, 13 punktów

Implementacja

Naiwne Poszukiwanie

Pierwszy sposób wyszukiwania punktów polega na przejrzeniu wszystkich punktów znajdujących się wewnątrz kwadratu opisanego na kole. Dla każdego punktu następnie jest sprawdzany warunek x2 + y2 = r2. Oto przykładowa realizacja podanego algorytmu:

  1. int IlePunktow(double r) {
  2.   int ile = 0;
  3.   for (int x = -ceil(r); x <= r; x++) {
  4.     for (int y = -ceil(r); y <= r; y++) {
  5.       if (x * x + y * y <= r * r) {
  6.         ile++;
  7.       }
  8.     }
  9.   }
  10.   return ile;
  11. }

Cały algorytm składa się z licznika i dwóch pętli. Nie jest to metoda optymalna, ponieważ złożoność rośnie kwadratowo tj. O(r2) (licząc dokładniej do przejrzenia jest prawie 4r2 punktów).

Optymalny

Zauważmy, że koło składa się z czterech identycznych ćwiartek, a ponadto pewne jest, że punkt środkowy zawsze istnieje (z założenia koło ma r > 0). Wzdłuż dowolnej osi od środka na zewnątrz jest floor(r) punktów. Pozostaje zatem dodać do tej wartości ilość punktów w ćwiartce, ale nie na krawędzi, a następnie pomnożyć przez 4 i dodać jeden punkt. Przyjrzyjmy się poniższej grafice:

Przykład podziału

W celu policzenia ile jest "zielonych" punktów to wykonujemy następujące operacje: ustawiamy x na ilość punktów wzdłuż osi oraz y = 1. Następnie jeśli punkt znajduje się poza kołem to zmniejszamy x tak długo, aż znajdziemy się w kole. Wartość x zmniejszamy, aż do osiągnięcia wartości 0. Proces ten powtarzamy dla każdego y, który jest ograniczony promieniem koła r.

Oto przykładowy kod realizujący to zadanie:

  1. int IlePunktow(double r) {
  2.   int ile = 0;
  3.   int x = ceil(r);
  4.   for (int y = 1; y <= ceil(r); y++) {
  5.     while (x > 0 && x * x + y * y > r * r) {
  6.       x--;
  7.     }
  8.     ile += x;
  9.   }
  10.   return (ile + int(r)) * 4 + 1;
  11. }

Zaletą takiego rozwiązania jest znaczne poprawienie złożoności, ponieważ warunek zostanie policzony dla maksymalnie r punktów. Ponadto znaczna część punktów jest policzona bez sprawdzania warunku na bycie wewnątrz koła.

Testowanie funkcji

Oto przykładowy fragment kodu do wczytania promienia koła, a następnie wypisaniu ile punktów znajduje się w środku.

  1. int main () {
  2.   double r;
  3.   cout << "Promien okregu\n r = ";
  4.   cin >> r;
  5.   int ile = IlePunktow(r);
  6.   cout << "Punktow w srodku " << ile;
  7.   system("pause");
  8.   return 0;
  9. }

Uwaga: przedstawione w zadaniu metody wymagają podania promienia r z odpowiednią dokładnością. W przypadku sqrt(2) należy podać wartość 1.415, ponieważ 1.414 nie pokaże prawidłowego wyniku.

Zadania
Zadanie 1
Napisz program realizujący zadanie podane w artykule, ale dla koła o dowolnej lokalizacji w układzie współrzędnych.
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1