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. static int IlePunktow(double r)
  2. {
  3. int ile = 0;
  4. for (int x = -(int)Math.Ceiling(r); x <= r; x++)
  5. {
  6. for (int y = -(int)Math.Ceiling(r); y <= r; y++)
  7. {
  8. if (x * x + y * y <= r * r)
  9. {
  10. ile++;
  11. }
  12. }
  13. }
  14. return ile;
  15. }

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. static int IlePunktow(double r)
  2. {
  3. int ile = 0;
  4. int x = (int)Math.Ceiling(r);
  5. for (int y = 1; y <= (int)Math.Ceiling(r); y++)
  6. {
  7. while (x > 0 && x * x + y * y > r * r)
  8. {
  9. x--;
  10. }
  11. ile += x;
  12. }
  13. return (ile + (int)r) * 4 + 1;
  14. }

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. static void Main(string[] args)
  2. {
  3. Console.Write("Promień okregu\n r = ");
  4. double r = double.Parse(Console.ReadLine());
  5. int ile = IlePunktow(r);
  6. Console.WriteLine("Punktów w środku: {0}", ile);
  7. Console.ReadKey();
  8. }

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