algorytm.org

Kreślenie okręgów



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Kreślenie okręgów
Ocena użytkowników:***** / 8
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 29 marca 2007 19:12

W trakcie kreślenia okręgu wykorzystamy jego ośmiokrtoną symetrię. Do pełnego narysowania okręgu wystarczy wykonać obliczenia tylko dla wycinka od 0 do 45 stopni (czyli dla punktów dla których spełniony jest warunek y > x). Pozostałe fragmenty mogą być wyświetlone symetrycznie tak jak przedstawiono to na schemacie poniżej:
Okrąg - symetria ośmiokrotna
Równanie okręgu o środku we współrzędnych (0, 0) i promieniu R to: F(x, y) = x2 + y2 - R2
Dla punktów leżących na okręgu F(x, y) = 0
Dla punktów leżących na zewnątrz okręgu F(x, y) > 0
Dla punktów leżących wewnątrz okręgu F(x, y) < 0

Kreślenie okręgu - punkt środkowy Jak widać na rysunku po prawej, idealny okrąg nie przechodzi dokładnie przez punkty, które zapalamy. Należy więc wybrać punkty leżące najbliżej idealnego okręgu. Na czarno zaznaczony mamy aktualny punkt (xp, yp). Jak już powiedzieliśmy wcześniej rysować będziemy tylko początkowe 45 stopni okręgu. W takim wypadku zawsze będziemy musieli podjąc decyzję czy zapalić punkt E (położony na wschód), czy punkt SE (położony na południowy wschód). Który z tych dwóch punktów wybrać? Oczywiście ten leżący bliżej idealnego okręgu. Na rysunku wprowadzono punkt M, leżący dokładnie pośrodku punktów E oraz SE. Zatem jeżeli okrąg przecina się nad punktem M to wybieramy E, jeżeli pod lub dokładnie w wybieramy SE. By efektywnie podejmować taką decyzję wprowadzimy zmienną decyzyjną d = F(xp + 1, yp - 0.5) = (xp + 1)2 + (yp - 0.5)2 - R2
Jeżeli d ≥ 0 to wybieramy kierunek SE.
Jeżeli d < 0 to wybieramy kierunek E.

Początkowa wartość zmiennej decyzyjnej d wynosić będzie F(x0 + 1, y0 - 0.5), gdzie (x0, y0) jest pierwszym rysowanym punktem okręgu - pierwszy rysujemy punkt na samym szczycie okręgu zatem (x0, y0) = (0, R), podstawiając to do przedstawionego wzoru otrzymujemy:
F(0 + 1, R - 0.5) = 1 + (R2 - R + 0.25) - R2 = 1.25 - R

W zależności od wybranego ruchu (SE lub E) inaczej zmieniać będziemy aktualną wartość zmiennej decyzyjnej d
  • jeżeli wybrano kierunek E, to zwiększamy jedynie x:
    dold = (xp + 1)2 + (yp - 0.5)2 - R2
    dnew = F(xp + 2, yp - 0.5) = (xp + 2)2 + (yp - 0.5)2 -R2 = dold + (2xp + 3)

  • jeżeli wybrano kierunek SE, to zwiększamy x i zmniejszamy y:
    dold = (xp + 1)2 + (yp - 0.5)2 - R2
    dnew = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5)2 - R2 = dold + (2xp - 2yp + 5)

Ponieważ początkowa wartość zmiennej decyzyjnej d wyszła nam ułamkowa, a nam zależy na jak najszybszych obliczeniach, zamienimy ją na liczbę całkowitą (operacje na liczbach stałoprzecinkowych wykonywane są szybciej niż na liczbach zmiennoprzecinkowych). Przemnożymy zatem jej wartości przez 4 (decyzja zależy wyłącznie od znaku zmiennej decyzyjnej, dlatego możemy tak postąpić). I tak ostatecznie otrzymujemy:
  • wartość początkowa: d = 5 - 4*R
  • inkrementacja przy wyborze kierunku E: d = d + 8 * x + 12
  • inkrementacja przy wyborze kierunku SE: d = d + 8 * (x - y) + 20


Przykład:

Obliczymy 5 początkowych punktów dla okręgu o promieniu R = 10 i środku we współrzędnych (0, 0).
Pierwszy punkt to (0, R) = (0, 10)
Początkowa wartość zmiennej decyzyjnej d = 5 - 4*R = 5 - 40 = -35
Jej wartość jest mniejsza niż zero, a więc wybieramy kierunek E.
Zatem kolejny punkt to (0 + 1, 10) = (1, 10)
Wartość zmiennej decyzyjnej zmieniamy zgodnie ze wzorem d = -35 + 8 * 0 + 12 = - 23
Jej wartość jest mniejsza niż zero, a więc znów wybieramy kierunek E.
Zatem kolejny punkt to (1 + 1, 10) = (2, 10)
Wartość zmiennej decyzyjnej zmieniamy zgodnie ze wzorem d = -23 + 8 * 1 + 12 = - 3
Jej wartość jest mniejsza niż zero, a więc znów wybieramy kierunek E.
Zatem kolejny punkt to (2 + 1, 10) = (3, 10)
Wartość zmiennej decyzyjnej zmieniamy zgodnie ze wzorem d = -3 + 8 * 2 + 12 = 25
Jej wartość jest większa niż zero, więc wybieramy kierunek SE.
Zatem kolejny punkt to (3 + 1, 10 + 1) = (4, 11)
Wartość zmiennej decyzyjnej zmieniamy zgodnie ze wzorem d = 25 + 8 * (4 - 11) + 20 = -11
...

Obliczenia te należy kontynuować dopóki y > x, pamiętać też należy, że każdy obliczony punkt "potrkatować" trzeba wspomnianą już osimiokrotną symetrią.
Gdyby okrąg, który chcemy kreślić miał środek w punkcie innym niż (0, 0), obliczenia przebiegałyby identycznie jak dla okręgu o współrzednych środka (0, 0) tylko do ostatecznych punktów, które rysowalibyśmy dodalibyśmy przesunięcie równe środkowi. Tzn. dla okręgu o promieniu R = 10 i środku we współrzędnych (15, 30) otrzymalibyśmy identyczne obliczenia jak poprzednio tylko punkty, które narysowalibyśmy byłyby następujące:
(0 + 15, 10 + 30) = (15, 30)
(1 + 15, 10 + 30) = (16, 40)
(2 + 15, 10 + 30) = (17, 40)
(3 + 15, 10 + 30) = (18, 40)
(4 + 15, 11 + 30) = (19, 41)


Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Andrzej BoruckiC#MS Visual Studio 2010
.cs
.cs
***** / 3
Tomasz LubińskiC/C++Borland Builder 6
.cpp
.cpp
***** / 5
Andrzej BoruckiC/C++Qt Creator
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 3
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 01 września 2012 14:05
Dodaj komentarz