Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

Algorytm sprawdzenią czy dany wielokąt jest figurą wypukłą

23 Jan 2007 15:54 6122 10
  • Level 17  
    Otóż stoję przed takim problemem,mam dane współrzędne wierzchołków wielokąta (n-wierzchołków).Moim zadaniem jest sprawdzenie,czy powstały wielokąt jest figurą wypukłą.Jak to sprawdzić?? Czy istnieje jakiś algorytm?? A może ktoś pisał coś podobnego w c++?? Potrzebuję tego pilnie. Proszę szanownych kolegów o pomoc.
  • Level 11  
    podaj matematyczne warunki istnienia wielokąta wypukłego bądź kiedy figura nim nie jest
  • Level 31  
    Wydaje mi się, że wystarczy sprawdzić iloczyny wektorowe wszystkich sąsiednich boków (n iloczynów dla n-kąta). Jeśli mają te same znaki, to wielokąt jest wypukły (chyba... ;) ).
  • Level 11  
    Matematyczna definicja wypuklosci:
    A jest wypukly <=> dla kazdego a i b nalezacego do A, dla kazdego t nalezacego do przedzialu (0,1) punkt t*a + (1-t)b nalezy do A.

    jest jeszcze kilka innych konkurencyjnych definicji, ale ta jest najprostsza.

    Moja pierwsza proba podejscia do algorytmu, przy zalozeniu ze punktow jest skonczenie wele i ze wielokat jest z RxR (czyli ze standardowej plaszczyzny):

    Majac dwa wierzcholki A=(a1,a2) i B=(b1,b2) musimy sprawdzic czy punkt C=(t*a1+(1-t)*b1,t*a2+(1-t)*b2) nalezy do zbioru A dla t z odcinka (0,1) (z tym ze moc odcinka (0,1) to continuum.. ale moza to jakos liczbami wymiernymi aproksymowac...).

    Teraz powstaje pytanie- jak sprawdzic czy dany punkt plaszczyzny nalezy do zbioru wyznaczonego przez N punktow plaszczyzny? To nie jest rozwiazanie, ale przerzucenie problemu. Moze wymysle taki agorytm.. albo ktos inny na elce :) Gratuluje tym co przeczytali do konca i zrozumieli :)

    Idea: prawdpodobnie wystarczy sprawdzic dla t=1/2, ale dowodu nie podam bo pewien nie jestem i dowodu nie znam :) jeszcze...
  • R.I.P. Meritorious for the elektroda.pl
    A może skorzystać z takiej oto definicji:
    Wielokąt jest wypukły, jeśli dla każdego boku wszystkie wierzchołki wielokąta leżą po tej samej stronie tego boku lub na tym boku.

    Zaletą tej definicji jest to, że aby stwierdzić wypukłość lub wklęsłość wielokąta wystarczy znać wierzchołki wielokąta a dokładnie ich współrzędne – nie jest nam potrzebny rysunek wielokąta.

    ( http://kaztyc.webpark.pl/wklesle.htm )
  • Level 17  
    Kolega jankolo ma rację,właśnie opierając się na tym stwierdzeniu,staram się stworzyć swój program.Mam czas do niedzieli wieczór,jak napiszę to wrzucę kod,ewentualnie kod do poprawki :)
  • Level 17  
    Zatem stworzyłem programik korzystając z twierdzenia,na które uwagę zwrócił kolega jankolo. Program działa poprawnie, ale jeszcze kwestia, gdy boki są prostymi prostopadłymi do osi OX:
    Code:

    #include <iostream.h>
    #include <string.h>
    #include <vector.h>
    #include <fstream.h>

    class punkt{
          double x;
          double y;
          public:
                 punkt(){x=y=0;}
                 punkt(double _x,double _y){
                           x=_x;
                           y=_y;
                           }
                 double daj_x(){return x;}
                 double daj_y(){return y;}
                 friend ostream& operator<<(ostream& ,punkt& );
          };
         
     ostream& operator<<(ostream& s,punkt& p){
           s<<"("<<p.x<<","<<p.y<<")";
           return s;
           }

    class wielokat{
          vector<punkt> P;
          vector<bool> B;
          public:
                 void wczytanie_wielokata();
                 double wyl_prostej(punkt,punkt,double);
                 bool spr_wyp();     
                 void wypisz_wiel();
                 friend class punkt;
                 
          };

    double wielokat::wyl_prostej(punkt p, punkt k,double w_x){
           if(p.daj_x()==k.daj_x()) return p.daj_x();
           else
           return ( (k.daj_y()-p.daj_y()) / (k.daj_x()-p.daj_x()) )*( w_x-p.daj_x() )+p.daj_y();
           }
     
    bool wielokat::spr_wyp(){
         if(P.size()-1<3){ return false;}
         else if(P.size()-1==3){ return true;}
         else{
         for(int j=0;j<P.size()-1;j++){
                 for(int d=0;d<P.size()-1;d++){
                    double pom = (P[d].daj_y()-wyl_prostej(P[j],P[j+1],P[d].daj_x()));   
                 if(pom > 0.0){ B.push_back(true);}                                                                       
                 if(pom < 0.0) {B.push_back(false);}
                                                         }
                                       vector<bool> T(B.size());
                                       vector<bool> F(B.size());
                                       for(int z=0;z<B.size();z++) {
                                               T[z]=true;
                                               F[z]=false;
                                               }
                                       if(B==T || B==F){
                                                for(int l=0;l<B.size()+1;l++){
                                               B.pop_back();
                                               T.pop_back();
                                               F.pop_back();
                                                       }
                                               }
                                       else {return false;break;}
                 }
                                       return true;
                                       }
         }
         
    void wielokat::wczytanie_wielokata(){
                          double i, j;
                          ifstream plik;
                          plik.open("dane.txt", ios::binary);
                          plik.seekg(0, ios::beg);
                          if(plik.is_open()){
                          while(!plik.eof()){
                          plik >> i >> j;
                          P.push_back(punkt(i, j));
                                               }
                          }
                           P.push_back(P[0]);           
         }
     
    void wielokat::wypisz_wiel(){
         for(int k=0;k<P.size()-1;k++){
                                  cout<<P[k]<<" ";
                                  }
                                  cout<<endl;
         }
       

    int main(){
        wielokat W;
        W.wczytanie_wielokata();
        W.wypisz_wiel();
        if( W.spr_wyp()==false) cout<<endl<<"Wielokat nie jest wypukly"<<endl;
        else cout<<endl<<"Wielokat jest wypukly"<<endl;
      system("PAUSE");
        return 0;
        }
       

    Później jeszcze poszperałem z kolegą w necie i znaleśliśmy taki programik:
    http://www.republika.pl/wmula/snippets/isconvex.py
    Jeśli byłby ktoś uprzejmy przetłumaczyć to na C++ i ewentualnie z moimi klasami to ładnie zgrać.
  • Level 17  
    Ostateczna wersja algoryrtmu, sprawdziłem go na kilkunastu różnych przypadkach,ale nie wiem czy jest w 100% uniwersalny dla wszelkich punktów i wielokątów w układzie współrzędnych:

    Code:

    /*
    *******************************************************************************
    Program sprawdzający czy dany wielokąt jest figurą wypukłą.
    Algorytm opiera się na stwierdzeniu:
    ** Wielokąt jest wypukły, jeśli dla każdego boku wszystkie wierzchołki wielokąta leżą po tej samej stronie tego boku lub na tym boku.**
    ********************************************************************************
    */
    #include <iostream.h>
    #include <string.h>
    #include <vector.h>
    #include <fstream.h>

    //Klasa punkt przechowuje wierzchołki, oraz posiada zaprzyjazniony strumień do
    //wypisania wierzchołka;

    class punkt{
          double x;
          double y;
          public:
                 punkt(){x=y=0;}
                 punkt(double _x,double _y){
                           x=_x;
                           y=_y;
                           }
                 double daj_x(){return x;}
                 double daj_y(){return y;}
                 friend ostream& operator<<(ostream& ,punkt& );
          };

    //Zaprzyjaźniony operator wypisywania wierzchołka

     ostream& operator<<(ostream& s,punkt& p){
           s<<"("<<p.x<<","<<p.y<<")";
           return s;
           }


    //Klasa wielokat - składa się z dwóch wektorów z wbudowanej biblioteki STL,
    //jeden przechowuje wczytane wierzchołki, drugi wartości booloskie

    class wielokat{
          vector<punkt> P;
          vector<bool> B;
          public:
                 void wczytanie_wielokata(); //wczytuje wielokąt z pliku dane.txt
                 double wyl_prostej(punkt,punkt,double); //wylicza rownanie prostej (boku) przechodzącego przez każde 2 wierzchołki
                 bool spr_wyp();     //sprawdza czy pozostałe wierzchołki leżą po jednej stronie prostej
                 void wypisz_wiel(); //wypisuje wielomian
                 friend class punkt; //zaprzyjaźnienie z klasa punkt-zamiast dziedziczenia
          };

    double wielokat::wyl_prostej(punkt p, punkt k,double w_x){
           if(p.daj_x()==k.daj_x()) return 0.0; //sytuacja,gdy boki są prostymi prostopadłymi do osi OX,wtedy nie sa funckjami
           else
           return ( (k.daj_y()-p.daj_y()) / (k.daj_x()-p.daj_x()) )*( w_x-p.daj_x() )+p.daj_y();
           }
     
    bool wielokat::spr_wyp(){
         if(P.size()-1<3){ return false;} //jeśli ilość wierzchołków jest mniejszy niż 3,to nie można mówić o wielokącie
         else if(P.size()-1==3){ return true;} //jeśli ilość wierzchołków równa się 3,to jest to trójkąt -zatem figura płaska-pod warunkiem,że punkty nie są wspołliniowe
         else{
         for(int j=0;j<P.size()-1;j++){
                 for(int d=0;d<P.size()-1;d++){
                    double pom = (P[d].daj_y()-wyl_prostej(P[j],P[j+1],P[d].daj_x()));   
                    if(pom!=0 && wyl_prostej(P[j],P[j+1],P[d].daj_x())==0.0){ //sytuacja,gdy boki są prostymi prostopadłymi do osi OX,wtedy nie są funckjami
                                                                              //zatem sprawdzamy tylko po której stronie leżą pozostałe wierzchołki,co zależne jest tylko od ich współrzędnych x-owych
                           if(P[j].daj_x()>P[d].daj_x()){B.push_back(true);}
                           if(P[j].daj_x()<P[d].daj_x()){B.push_back(false);}
                           }
                           else{
                 if(pom > 0.0){ B.push_back(true);}                                                                       
                 if(pom < 0.0) {B.push_back(false);}
                               }
                                                         }
                                       vector<bool> T(B.size());
                                       vector<bool> F(B.size());
                                       for(int z=0;z<B.size();z++) {
                                               T[z]=true; 
                                               F[z]=false;
                                               }
                                       if(B==T || B==F){
                                                for(int l=0;l<B.size()+1;l++){
                                               B.pop_back();
                                               T.pop_back();
                                               F.pop_back();
                                                       }
                                               }
                                       else {return false;break;}
                                        }
                                       return true;
                                       }
         }
         
    void wielokat::wczytanie_wielokata(){
                          double i, j;
                          ifstream plik;
                          plik.open("dane.txt", ios::binary);
                          plik.seekg(0, ios::beg);
                          if(plik.is_open()){
                          while(!plik.eof()){
                          plik >> i >> j;
                          P.push_back(punkt(i, j));
                                               }
                          }
                           P.push_back(P[0]);           
         }
     
    void wielokat::wypisz_wiel(){
         for(int k=0;k<P.size()-1;k++){
                                  cout<<P[k]<<" ";
                                  }
                                  cout<<endl;
         }
       

    int main(){
        wielokat W;
        W.wczytanie_wielokata();
        W.wypisz_wiel();
        if( W.spr_wyp()==false) cout<<"Wielokat nie jest wypukly"<<endl;
        else cout<<"Wielokat jest wypukly"<<endl;
      system("PAUSE");
        return 0;
        }
       
  • Level 11  
    z iloczynu skalarnego mozemy policzyc kat miedzy wektorami (a sa nimi poszczegolne boki)

    w wielokacie wypuklym zaden kat nie jest wiekszy niz 180 stopni.
    sprawa troche sie kompiluje, acos w math.h zawsze zwraca liczba dodatnia,
    ale juz ktos wspomnial, ze mozna tez sprawdzic czy wszystkie iloczyny skalarne maja ten sam znak.

    EDIT:
    nie, w tym problemie nie pomoze iloczyn skalarny, np.
    Code:
      xxx
    
      x x
    xxx xxx
    x     x
    xxx xxx
      x x
      xxx

    zauwazmy, ze wszystkie iloczyny wektorowe sa tej samej wartosci, tj. maja ten sam znak, a figura nie jest wypukla.
    kwadrat tez ma wszystkie iloczyny tego samego znaku, a jest wypukly.

    poprawnie zadziala sprawdzanie dla kazdego boku czy wszystkie punkty leza po tej samej jego stronie.
  • Level 10  
    Witam,
    czy ktoś mógłby mi podać przykładowy plik txt z danymi do tego programu?