- Tytuł:
-
Program calculating the area of a figure made of circles
Program obliczający pole figury złożonej z kół - Autorzy:
- Bogacz, Michał
- Opis:
-
The purpose of the work is to develop and implement an algorithm that will calculate the area covered by a set of wheels (disks) placed on a plane. The program receives the wheel centers and their radii as arguments. The wheels may overlap. The most difficult problem to solve in this task is to calculate the surface area of the common parts of any overlapping wheels and define which of them should be included in the final result. To calculate the area covered by a set of wheels, you can use the Monte Carlo method, which gives an approximate result of the surface area. The reason for developing a new algorithm for calculating the surface area covered by a set of wheels is to obtain the result with the maximum possible precision and in less time than with the Monte Carlo method. The work covers cases of coherent surfaces in two-dimensional space. The first part of the work contains the terminology used when describing the algorithm. The second part of the work consists of the following steps of the algorithm. Then each part of the algorithm is described in detail. The last part of the work contains information about the efficiency and correctness of the algorithm. Finally, there is a summary of the work.
Celem pracy jest opracowanie i implementacja algorytmu, który będzie obliczał powierzchnię zakrytą przez zbiór kół (dysków) umieszczonych na płaszczyźnie. Jako argumenty działania program otrzymuje położenia środków kół oraz ich promienie. Koła mogą się nakładać. Najtrudniejszym problemem do rozwiązania w tym zadaniu jest obliczenie pola powierzchni części wspólnych dowolnie nakładających się na siebie kół oraz zdefiniowanie, które z nich należy uwzględnić przy końcowym wyniku. Do obliczenia pola powierzchni zakrywanego przez zbiór kół można użyć metody Monte Carlo, która podaje przybliżony wynik pola powierzchni. Metoda polega na opisaniu kwadratu na kołach. Następnie generator liczb pseudolosowych zwraca liczby określające współrzędne położenia punktów w danym kwadracie. Kolejnym krokiem algorytmu jest sprawdzenie, czy kolejne punkty należą do koła wpisanego w dany kwadrat. Dokładność metody Monte Carlo jest zależna od ilości losowanych liczb oraz jakości użytego generatora liczb pseudolosowych. Powodem opracowania nowego algorytmu służącego do obliczania pola powierzchni zakrywanego przez zbiór kół jest uzyskanie wyniku z maksymalną możliwą precyzją oraz w czasie krótszym niż z metody Monte Carlo. Praca obejmuje przypadki powierzchni jednospójnych w przestrzeni dwuwymiarowej. W pierwszej części pracy zawarta została terminologia używana podczas opisu algorytmu. Druga część pracy składa się z wymienionych kolejno kroków algorytmu. Następnie każda część algorytmu jest szczegółowo opisana. Ostatnia część pracy zawiera informacje o wydajności oraz poprawności algorytmu. Na końcu znajduje się podsumowanie pracy. - Dostawca treści:
- Repozytorium Uniwersytetu Jagiellońskiego
Inne