BADANIE PRZYNALE»NOªCI PUNKTU DO WIELOKíTA

rezentowany problem nale┐y do problem≤w geometrycznych, a algorytm jego rozwi▒zania to jeden z podstawowych algorytm≤w geometrycznych. Jak │atwo siΩ domy╢liµ, ta grupa algorytm≤w zajmuje siΩ problemami geometrii na p│aszczy╝nie lub w przestrzeni. Tym razem poka┐Ω Wam, w jaki spos≤ mo┐na sprawdziµ, czy dany punkt nale┐y do wnΩtrza jakiego╢ wielok▒ta. My╢lΩ, ┐e nie trzeba Tobie wiΩcej t│umaczyµ - po prostu mamy sprawdziµ, czy jaki╢ punkt jest wewn▒trz wielok▒ta czy na zewn▒trz. Odpu╢cimy sobie tym razem sprawdzanie, czy punkt ten nie nale┐y przypadkiem do brzegu wielok▒ta. Jest to do╢µ proste i omawiany przeze mnie algorytm mo┐na │atwo rozbudowaµ tak, aby brzeg wielok▒ta te┐ by│ sprawdzany.

Pozostaje sprecyzowaµ, jakie wielok▒ty bΩdziemy badaµ. BΩd▒ to po prostu figury o bokach bΩd▒cych odcinkami, czyli nie bierzemy pod uwagΩ bardziej z│o┐onych obiekt≤w. Rozwa┐ane wielok▒ty nie musz▒ byµ wypuk│e, choµ - je╢li by╢my wiedzieli, ┐e s▒ wypuk│e - to algorytm mo┐na by znacznie upro╢ciµ.

Brzegi wielok▒ta, kt≤re bΩd▒ nam potrzebne przy badaniu przynale┐no╢ci punktu, s▒ jak wiadomo zbiorami niesko±czenie wielu punkt≤w. W programie bΩdziemy potrzebowali jakiej╢ metody na zapamiΩtanie wielok▒ta. Najprostszym i zarazem najbardziej naturalnym sposobem na zapmiΩtanie go w pamiΩci jest pamiΩtanie wsp≤│rzΩdnych kolejnych wierzcho│k≤w wielok▒ta w odpowiedniej tablicy. Jest to chyba oczywiste.

Je╢li nie mamy ju┐ problemu z zapamiΩtaniem w pamiΩci wielok▒ta oraz punktu (to drugie to chyba bana│?), nale┐y zastanowiµ siΩ, jak mo┐na sprawdziµ, czy punkt nale┐y do wnΩtrza wielok▒ta. Pozornie sprawa mo┐e wydawaµ siΩ trudna, ale algorytm opiera siΩ na jednym, bardzo prostym spostrze┐eniu. Za│≤┐my, ┐e z badanego punktu poprowadzili╢my dowoln▒ p≤│prost▒ o ko±cu w tym punkcie. Je╢li siΩ chwilkΩ zastanowisz, to dojdziesz do wniosku, na kt≤rym opiera siΩ ca│y algorytm: je╢li ta prosta przetnie boki wielok▒ta nieparzyst▒ ilo╢µ razy, to badany punkt z pewno╢ci▒ znajduje siΩ wewn▒trz wielok▒ta i odwrotnie - je╢li przetnie ona jego boki parzyst▒ ilo╢µ razy, lub nie przetnie ich wcale, to punkt ten na pewno le┐y na zewn▒trz wielok▒ta. Jak chwilkΩ sobie nad tym pomy╢lisz, to ca│a idea bΩdzie jasna jak s│o±ce. Aby lepiej zrozumieµ to, co przeczyta│e╢, sp≤jrz na poni┐szy rysunek:

Analizowany przez nas punkt zaznaczy│em na rysunku kolorem czerwonym, a przyk│adow▒ p≤│prost▒ zielonym. To, ┐e punkt nale┐y do wnΩtrza wielok▒ta, nie budzi chyba Twoich w▒tpliwo╢ci. Nasza p≤│prosta przecina boki wielok▒ta 5 razy, czyli nieparzyst▒ ilo╢µ. Spr≤buj w my╢lach umiejscawiaµ punkt w innych miejscach i wyobra╝ sobie odpowiednie p≤│proste, a przekonasz siΩ, ┐e nasze g│≤wne spostrze┐enie jest jak najbardziej prawdziwe.

Nie bez powodu na pocz▒tku naszych rozwa┐a± wybra│em tak▒ p≤│prost▒, kt≤ra jest "pozioma", czyli m≤wi▒c fachowo, r≤wnoleg│a do osi OX uk│adu wsp≤│rzΩdnych. Wynika to z faktu, ┐e taka p≤│prosta jest potem bardzo wygodna w programie, prosta j▒ zawieraj▒ca ma bardzo proste r≤wnanie, a ponadto pozioma p≤│prosta jest dla cz│owieka najnaturalniejszym wyborem. (to ostatnie oczywi╢cie nie mo┐e byµ brane pod uwagΩ przy projektowaniu algorytm≤w :-).

Jak wynika z powy┐szych rozwa┐a±, nale┐y po prostu policzyµ ilo╢µ przeciΩµ dowolnej p≤│prostej o ko±cu w badanym punkcie z bokami i na tym koniec. Mo┐na to zrobiµ wΩdruj▒c po kolei po wszystkich bokach i sprawdzaj▒c po kolei czy przecinaj▒ one p≤│prost▒ (o szczeg≤│ach p≤╝niej), ale... ┐ycie nie jest takie proste. Jak zapewne pamiΩtasz z lekcji matematyki, w podobnych sytuacjach trzeba bardzo uwa┐aµ na szczeg≤lne przypadki. Na przyk│ad sp≤jrz na rysunek poni┐ej:

Jak widzisz, sprawa siΩ troszeczkΩ skomplikowa│a. CzΩ╢µ wierzcho│k≤w wielok▒ta znajduje siΩ bowiem na naszej p≤│prostej. Ma│o tego, jeden z bok≤w zawiera siΩ w tej p≤│prostej!!! Je╢li trochΩ siΩ zastanowiµ, rozwi▒zanie przychodzi samo. Je╢li jaki╢ wierzcho│ek zawiera siΩ w p≤│prostej, to je╢li jego "s▒siedzi" s▒ po przeciwnej stronie p≤│prostej, sytuacjΩ trzeba traktowaµ jako kolejne przeciΩcie - w przeciwnym razie (gdy obaj "s▒siedzi" s▒ po tej samej stronie p≤│prostej) jako brak przeciΩcia. Je╢li za╢ w p≤│prostej zawiera siΩ ca│y bok wielok▒ta, trzeba post▒piµ tak samo, bior▒c pod uwagΩ s▒siad≤w tego boku. Sprawa po chwili namys│u wydaje siΩ prosta. Tak jest w istocie, ale tylko gdy patrzymy sobie z boku na rysuneczek. W praktyce sytuacja jest naprawdΩ trudna, bo wymaga rozbudowanego i dobrze przemy╢lanego kodu, co w po│▒czeniu z elementami geometrii analitycznej (o kt≤rych p≤╝niej) mo┐e uczyniµ program nieczytelnym i bardzo trudnym do zrozumienia.

Warto w takiej sytuacji zadaµ sobie pytanie: czy nie mo┐na by rozwi▒zaµ problemu w prostszy spos≤b? Odpowied╝ jest oczywi╢cie twierdz▒ca, a i ten inny spos≤b ca│kiem logiczny. Je╢li znajdziemy siΩ w k│opotliwej sytuacji, nale┐y po prostu wybraµ inn▒ p≤│prost▒ - bezpieczn▒, czyli nie zawieraj▒c▒ w sobie wierzcho│k≤w wielok▒ta. Wtedy ca│y problem upro╢ci siΩ do poprzednich, │atwiejszych sytuacji.

W praktyce ju┐ od pocz▒tku najlepiej jest losowo wybieraµ po│o┐enie p≤│prostej, a┐ do uzyskanie po┐adanej sytuacji.

To tyle teorii. Teraz najtrudniejsza czΩ╢µ, czyli zakodowanie algorytmu. Poni┐esz przedstawiam przyk│adowy program napisany w c++. Jego podstawow▒ czΩ╢ci▒ jest klasa wielokat. Zawiera ona wierzcho│ki zapisane w tablicy, funkcje czytaj▒ce informacje o wielok▒cie i rysuj▒ce go. Najwa┐niejsza jest jednak funkcja spr, kt≤ra sprawdza czy punkt o wsp≤│rzΩdnych podanych jako argument nale┐y do wielok▒ta. P≤│prosta jest reprezentowana w tej funkcji przez kierunkowe r≤wnanie prostej o wsp≤│czynniku kierunkowym a wiΩkszym od 0 wybieranym losowo i badany punkt ograniczaj▒cy jednocze╢nie p≤│prost▒. DziΩki temu ┐e a>0 p≤│prosta jest skierowana "w prawo do g≤ry". Wiedz▒c, ┐e zawsze tak jest, mo┐na │atwo sprawdziµ, czy punkt przeciΩcia prostej z bokiem reprezentowanym przez dwa punkty nale┐y do p≤│prostej (zwiΩkszamy liczbΩ przeciΩµ) lub tylko do prostej (brak przeciΩcia) przez por≤wnanie wsp≤│rzΩdnych punktu przeciΩcia ze wsp≤│rzΩdnymi analizowango punktu. Wsp≤│rzΩdne punktu przeciΩcia odcinka i p≤lprostej wyliczane s▒ z odpowiednio przekszta│conych wzor≤w z geometrii analitycznej. Po znalezieniu punktu przeciΩcia sprawdzamy jak ju┐ powiedzia│em jego przynale┐no╢µ do p≤│prostej, ale te┐ koniecznie do odcinka zawartego w drugiej prostej (funkcja w_odcinku). Trzeba te┐ pamiΩtaµ, ┐e r≤wnanie kierunkowe nie opisuje prostej r≤wnoleg│ej do osi OY, wiΩc taki przypadek rozpatruje siΩ osobno w funkcji przeciecie.

/* Problem przynale┐no╢ci punktu do wielok▒ta
Autor: Micha│ Staszkiewicz
e-mail: pasman@wp.pl
www: http://pasman.republika.pl/
JΩzyk: C++
Kompilator: Borland C++ v. 3.1
*/

#include<iostream.h>
#include<conio.h>
#include<graphics.h>
#include<stdio.h>
#include<stdlib.h>

class wielokat { //Klasa reprezentuj▒ca wielok▒t
  private:
  int ile;  //Ilo╢µ wierzcho│k≤w wielok▒ta
  struct punkt{ //Struktura reprezentuj▒ca pojedynczy punkt
    float x,y;
  };
  punkt wierzcholki[15]; //Maksymalnie 15 wierzcho│k≤w
  int naprostej(int a,int b); //Czy na prostej y=a*x+b jest jaki╢ wierzcho│ek
  int przeciecie(int p1, int p2, float a, float b, float x, float y);
     //czy p≤│prosta zawarta w prostej y=a*x+b o pocz▒tku (x,y) przecina odcinek
     //o ko±cach w punktach o indeksach w tablicy [p1] i [p2]
  int w_odcinku(float x,float y,float x1,float y1,float x2,float y2);
    //Czy punkt (x,y) zawiera siΩ w odcinku o ko±cach (x1,y1) i (x2,y2)
  public:
  void pobierz(void); //Pobieranie informacji o wielokÑcie
  void rysuj(void);  //Kre╢lenie wielokÑta
  void spr(float x, float y); //Sprawdzenie przynale╛noÿci punktu
};

int wielokat::naprostej(int a, int b){
  int i; //Zmienna pomocnicza, wskazuje wierzcho│ki
  for (i=0;i<ile;i++)
    if (wierzcholki[i].y==a*wierzcholki[i].x+b) return 1; //Jest
      //wierzcho│ek na prostej!
  return 0; //Nie ma na prostej wierzcho│ka
}

int wielokat::w_odcinku(float x,float y,float x1,float y1,float x2,float y2){
  if ((x>x1) && (x>x2)) return 0;
  if ((x<x1) && (x<x2)) return 0;
  if ((y>y1) && (y>y2)) return 0;
  if ((y<y1) && (y<y2)) return 0;
  return 1;
}

int wielokat::przeciecie(int p1, int p2, float a2, float b2, float x, float y){
  float x1=wierzcholki[p1].x;
  float y1=wierzcholki[p1].y;
  float x2=wierzcholki[p2].x;
  float y2=wierzcholki[p2].y;
  float xprzec,yprzec;//Wsp≤│rzΩdne punktu przeciΩcia siΩ prostych
  if (x1!=x2){ //Je╢li prosta z bokiem nie jest równoleg│a do osi OY
    float a1=((y2-y1)/(x2-x1)); //Wsp≤│czynnik kierunkowy prostej zaw. bok
    float b1=(y1-((x1*(y2-y1))/(x2-x1))); //Wsp≤│czynnik b dla prostej zaw. bok
    //Teraz mamy wsp≤│rzΩdne punktów p1,p2 bez potrzeby odwo│ywania siΩ do
    //tablicy
    if (a1==a2) //Je╢li prosta jest || do boku
      return 0;
    xprzec=(b2-b1)/(a1-a2); //Pozioma wsp≤│rzΩdna punktu przeciΩcia
    yprzec=a1*xprzec+b1; //Pionowa wsp≤│rzΩdna punktu przeciΩcia */
    } else { //Je╢li jest r≤wnoleg│a
    xprzec=x1;
    yprzec=a2*x1+b2;
  }
  if ((xprzec>x) && (yprzec>y) && (w_odcinku(xprzec,yprzec,x1,y1,x2,y2)))
    //Je╢li punkt przeciΩcia nale┐y do p≤│pr. i boku jednocze╢nie
    return 1; else
      return 0;
}

void wielokat::pobierz(void)
{
  clrscr();
  cout << "Ile wierzcho│k≤w ma mieµ wielok▒t?\n";
  cin >> ile;
  int i;
  for (i=0;i<ile;i++){
    cout << "\nPozioma wsp≤│rzΩdna " << i+1 << "-ego wierzcho│ka=";
    cin >> wierzcholki[i].x;
    cout << "\nPionowa wsp≤│rzΩdna " << i+1 << "-ego wierzcho│ka=";
    cin >> wierzcholki[i].y;
  }
}

void wielokat::rysuj(void)
{
  int karta=9,tryb=2;
  initgraph(&karta,&tryb,"c:/prog/borlandc/bgi");
  int i;
  line(320,0,320,479);
  line(0,240,639,240);
  for (i=0;i<ile-1;i++)
    line(int(wierzcholki[i].x)+320, -int(wierzcholki[i].y)+240, int(wierzcholki[i+1].x)+320,-int(wierzcholki[i+1].y)+240);
  line(int(wierzcholki[0].x)+320, -int(wierzcholki[0].y)+240, int(wierzcholki[ile-1].x)+320,-int(wierzcholki[ile-1].y)+240);
  getch();
}

void wielokat::spr(float x, float y){
  int i; //Zmienna pomocnicza - wskazauje na pierwszy punkt
  int przec=0; //Ilo╢µ przeci╢µ - bardzo wa╛ne!!!
  float a,b; //Wsp≤│czynniki w r≤wnaniu kierunkowym
  randomize();
  do {
    a=random(1000); //Losujemy wsp≤│czynnik kierunkowy
    b=y-a*x; //Wyliczamy wsp≤│czynnik b dla prostej
  } while(naprostej(a,b)); //Dop≤ki na tej prostej jest jaki╢ wierzcho│ek
    //Teraz nie mo┐e by│ ┐adnego wierzcho│ka na prostej :-D
  for (i=0;i<ile;i++)
    if (przeciecie(i,(i+1)%ile,a,b,x,y)) //Je╢li bok przecina p≤│prost▒
      przec++;
  putpixel(320+int(x),240-int(y),14); //Rysuje badany punkt
  getch();
  closegraph();
  if (przec%2==0) //Je╢li parzysta liczba przeciΩµ
    cout << "\nNie nale╛y!!!\n"; else //w przeciwnym razie:
      cout << "\nNale╛y!!!\n";
  cout << przec;
  getch();
}

main()
{
  wielokat figura;
  figura.pobierz();
  figura.rysuj();
  figura.spr(5,10);
}