Wielokąt Gwiaździsty.Metoda MonteCarlo.

Odpowiedz Nowy wątek
2014-12-27 10:29
0

Witam,

na wstępie chciałbym powiedzieć , iż będąc studentem informatyki stosowanej , nienawidzę zadań typu "Policz to w najtrudniejszy możliwy sposób" , matematyka jest piękna , ale po co ją komplikować..

Przechodząc do konkretów:
Mam do policzenia pole wielokąta gwiaździstego foremnego , metodą Monte Carlo. Zrobiłem mały research i (mam nadzieję) poniekąd zrozumiałem tę metodę numeryczną ( która z kolei nie została stworzona do liczenia pól.. ) , lecz cały czas błądzę w poszukiwaniu przedziału losowania liczb i warunku pozytywnego losowania. Podaję kod mojej dotychczasowej pracy :
Użytkownik podaje jedynie ilość trójkątów i wymiary każdego z nich ( tj. podstawę i wysokość ):

 import java.util.Scanner;
import java.util.Random;
import java.lang.Math;
public static void main(String[] args) 
    { Scanner input = new Scanner(System.in);
      System.out.println("Podaj ilosc trojkatow");
      int liczba = input.nextInt();
      System.out.println("Podaj wysokosc trojkatow");
      int wysokosc = input.nextInt();
      System.out.println("Podaj wymiar podstawy trojkatow");
      int podstawa = input.nextInt();
      System.out.println("Wymiary : " + liczba + " Wys. " + wysokosc + " podstawa " + podstawa);
      double R = podstawa/(2*(Math.sin(Math.PI/liczba))); // R : promien kola opisanego na wielokacie foremnym        
      int N = 10*100000; // ilosc losowan
       int Npoz = 0; // ilosc sukcesow
      double Pk = Math.pow(R,2) + podstawa*wysokosc; // pole opisanego na wielokacie kwadratu
      System.out.println("Promien kola:");
      System.out.println(R);
      System.out.println("Pole opisanego kwadratu :");
      System.out.println(Pk);
      double Pwk = 0.25 * liczba * (podstawa*podstawa) * (1/Math.tan(Math.PI/liczba)); // pole wielokata foremnego wewnatrz   gwiazdy
      double xa,ya;
      Random generator = new Random();
      //Pwk + 2*((podstawa*podstawa*Math.sqrt(3.0))/4)
      for (int i = 0 ; i < N ; i ++ )
      {
          //x = generator.nextDouble()-R + generator.nextInt((int)(2*R));
          //y = generator.nextDouble()-R + generator.nextInt((int)(2*R));
          xa = ((generator.nextDouble()-2*R+2*wysokosc + 2*generator.nextInt((int)(2*R+2*wysokosc))));
          ya = ((generator.nextDouble()-2*R+2*wysokosc + 2*generator.nextInt((int)(2*R+2*wysokosc))));
          System.out.println("Punkt x : " + xa + " y :" + ya + " Wartosc x^2+y^2 : " + ((xa*xa)+(ya*ya)));
          if (xa+ya <= Pwk + 2*((podstawa*podstawa*Math.sqrt(3.0))/4)  )
          {
              //System.out.println("Punkt zmiescilby sie w wielokacie !!");
              Npoz++;
          }
      }

Za każdą podpowiedź dziękuję i z góry przepraszam jeśli noobuje :)

edytowany 1x, ostatnio: bogdans, 2014-12-27 21:35

Pozostało 580 znaków

2014-12-27 11:04
0

Wyliczyłbym bounding box tej gwiazdy taki, żeby był równoległy do osi. http://pl.wikipedia.org/wiki/Bry%C5%82a_brzegowa
Losowanie punktów i liczenie pola będzie prostsze na prostokącie niż na kole.
Potem odpowiednio trzeba losować punkty w obrębie tego prostokąta. Normalnie można wylosować 2 wartości odpowiadające współrzędnym w tym prostokącie. Ważne żeby były równo rozłożone.
Na sprawdzenie czy punkt jest wewnątrz są dwie możliwości.
1.
Skorzystać z reprezentacji gwiazdy jako zbioru odcinków i algorytmu np "Inside vs Outside" pokazanego w linku niżej do sprawdzenia czy punkt jest w wielokącie.
http://erich.realtimerendering.com/ptinpoly/

  1. Powinna być bardziej wydajna.
    Myślę, że można zrobić użytek z tego, że ramiona tej gwiazdy są równo rozłożone. Wtedy wyliczając kąt między jej środkiem a wylosowanym punktem można by łatwo wyliczyć odległość brzegu.
    W takiej gwieździe
    http://screenshooter.net/100253651/dcjoafb
    trójkąty są rozmieszczone co 360/5 = 72 stopnie.
    Jeśli kąt między środkiem a punktem weźmiemy modulo 72 dostajemy jakby coś takiego
    http://screenshooter.net/100253651/xdjwlbq

Może coś się z tym da zrobić. To jest tylko tok mojego myślenia, nie wiem czy ten 2. punkt rzeczywiście coś pomoże, czy tak się da to zrobić w prosty sposób.

edytowany 4x, ostatnio: Sopelek, 2014-12-27 11:37

Pozostało 580 znaków

2014-12-27 12:09
0

Dziękuję za tak szybką odpowiedź:)
Udało mi się wywalczyć małe ułatwienie tzn. wielokąt ma się składać z min:4 maks:16 trójkątów.

Co do postu Sopelka:
Myślę że , bounding box będzie w tym przypadku kwadratem , ponieważ można w łatwy sposób obliczyć jego wymiary tj. 2promień wewnętrznego wielokąta foremnego ( jest na to wzór ) oraz 2 wysokość trójkąta podana przez użytkownika(ponieważ tak jak pisałem , użytkownik podaje wymiary trójkąta). Co do propozycji to rzeczywiście są ciekawe , 1 pomysł nawet nietrudno dałoby się oprogramować , ale musiałbym wtedy z góry narzucić wartości y , ponieważ nie ma wzoru , czy powtarzalności przy rysowaniu tego typu wielokąta. Teraz muszę dokończyć małe GUI na inny projekt i zedytuje tego posta kiedy wezmę się za Twoje propozycje :)

edytowany 1x, ostatnio: Dabeg, 2014-12-27 12:11

Pozostało 580 znaków

2014-12-27 21:39

Mam wrażenie, że stosujesz jakąś własną definicję wielokąta gwiaździstego. http://en.wikipedia.org/wiki/Star_polygon
Pytać powinieneś o ilość wierzchołków, "offset", tzn. co który łączyć, ewentualnie o promień koła. Jaki użytkownik potrafi podać poprawne dane wielokąta gwiaździstego foremnego?
A jeśli chodzi o algorytm, to najprościej będzie chyba tak:


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 2x, ostatnio: bogdans, 2014-12-28 07:29

Pozostało 580 znaków

2014-12-28 18:06
0

Bogdans,
Na wstępie muszę powiedzieć , że rzadko zajmowałem się geometrią. Jeśli chodzi o tą definicję to bazowałem na informacjach z zadania(tj. że użytkownik podaje wymiary i ilość trójkątów) oraz interpretowałem informacje z http://pl.wikipedia.org/wiki/Wielok%C4%85t_gwia%C5%BAdzisty , a konkretnie , tu cytat:"Na przykład, pięciokąt gwiaździsty foremny (pentagram) otrzymujemy w następujący sposób z pięciokąta foremnego" , stąd wziąłem , że środek to powinien być wielokąt foremny. Choć przyznaje , że mogłem popełnić błąd. Skontaktuje się z wykładowcą bo być może nie popełniłem tej gafy sam :) Tyle jeśli chodzi o przedstawienie mojego toku rozumowania przy tej definicji.

A jeśli chodzi o Twoją propozycję algorytmu dziękuję za przedstawienie tej biblioteki , bo przyda się nie tylko do tego projektu, sądzę także , że Twój pomysł jest naturalnie o wiele prostszy i mniej zawiły z tym , że mam pytanie :

  • czy mógłbyś udostępnić ten program ? ( Tu mam na myśli ten o rysowaniu wielokąta gwiaździstego)
edytowany 1x, ostatnio: Dabeg, 2014-12-28 18:08

Pozostało 580 znaków

2014-12-28 19:26
0

@Dabeg, to prawda, że "środek" foremnego wielokąta gwiaździstego jest wielokątem foremnym. Mi chodziło o to, że chyba nikt nie potrafi podać wysokości i wymiaru podstawy trójkątów, tak by utworzyły one (do spółki z wielokątem foremnym w środku) foremny wielokąt gwiaździsty.
Kod mojego programu jest tu: http://4programmers.net/Pastebin/3687. Program pisałem tylko do własnego użytku, jest on zatem pozbawiony głupotoodporności - uznałem, że w takiej sytuacji jest ona zbyteczna.
Edit. Gdybyś doczytał artykuł z polskiej Wikipedii do końca, to byś zauważył, że istnieje tylko jeden pięciokąt foremny gwiaździsty. Przy Twoim rozumieniu jest ich nieskończenie wiele.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 2x, ostatnio: bogdans, 2014-12-29 07:52

Pozostało 580 znaków

2014-12-30 14:43
0

@bogdans, przyznaję się do błędu , ale mam nadzieję , że student ma prawo popełniać błędy :)

  • Po tym projekcie zacznę z pewnością zabawę z biblioteką Swing, konstrukcja tego api jest bardzo ciekawa.

W każdym razie dziękuję za udzieloną pomoc temat można uznać za zamknięty.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0