Algorytm sprawdzenią czy dany wielokąt jest figurą wypukłą
chlo - 23 Sty 2007 16:54
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.
Lukasz_K - 23 Sty 2007 18:37
podaj matematyczne warunki istnienia wielokąta wypukłego bądź kiedy figura nim nie jest
paweliw - 23 Sty 2007 22:16
Definicje podające sposób sprawdzania czy wielokąt jest wklęsły czy wypukły są dostępne w sieci np.:
DEFINICJE Wieloboku, Wielokąta
Wielokąty wklęsłe
Problem tylko jak to przełożyć na język programowania ...
Sam Sung - 23 Sty 2007 22:58
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... ).
pelekkk - 24 Sty 2007 02:08
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...
jankolo - 24 Sty 2007 02:56
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 )
chlo - 25 Sty 2007 18:18
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
chlo - 26 Sty 2007 00:26
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:
#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ć.
chlo - 26 Sty 2007 18:07
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:
/*
*******************************************************************************
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;
}