Sprawdzanie czy punkt leży w wielokącie (point in polygon)

0

Witam.
Potrzebuję napisać funkcję która sprawdzi czy punkt znajduje się w wielokącie.
Mam taki algorytm:

 
void check ( polygon [n ], n , x , y) {
    int crossings =0;
    int i =0 , j=n -1 , dx , dy ;
      for (; i <n ; i ++) {
          if (( polygon [i ].y <y && polygon [j ].y >= y) || ( polygon [j ].y <y && polygon [i ].y >= y )) {
             dy = polygon [ i ]. y - polygon [j ]. y;
             dx = polygon [ i ]. x - polygon [j ]. x;
             if ( polygon [ i ]. x +(y - polygon [i ]. y )* dx /dy < x)
                 crossings ++;
          }
          j=i ;
      }
      return crossings %2;
}

Jednak potrzebne są tutaj wierzchołki wielokąta, a ja ich nie posiadam. Muszę je jakoś wyznaczyć,a nie wiem nawet czy się da.
Mój program działa tak, że klikam gdzieś na ekranie, a on wypełnia go kolorem, no wiadomo jeśli kliknięty pkt jest w wielokącie to wielokąt zostanie wypełniony.
Musze jednak dorobić opcję która wyświetli komunikat iż dany (kliknięty punkt) znajduje się w wielokącie.'
Czy ktoś wie jak to zrobić?
Dziękuję i pozdrawiam.

1

Mój program działa tak, że klikam gdzieś na ekranie, a on wypełnia go kolorem, no wiadomo jeśli kliknięty pkt jest w wielokącie to wielokąt zostanie wypełniony.

http://en.wikipedia.org/wiki/Flood_fill

1

http://bit.ly/1j8KrD7 - skrócony link

1

Co to znaczy, że nie masz wierzchołków. W takim razie jak jest zaprogramowany, że wyświetla się w konkretnym miejscu?

Jeśli masz jakąś mapę twoich wielokątów i one się nie zmieniają, a ty potrzebujesz dla klikniętego punktu wyliczyć wielokąt, w którym się znajduje, to ten problem ten nazywa się lokalizacja planarna punktu. Jest opisany w książce Geometria obliczeniowa M. de Berga (rozdział 6), możesz poszukać w sieci lub najbliższej bibliotece. Trzeba w nim stworzyć mapę trapezową i to będzie trochę skomplikowane, ale może warto spróbować.

Jeżeli masz tylko jeden wielokąt (opisany odcinkami, czy wierzchołkami) to możesz sprawdzać sprawdzając położenie względem każdego z odcinków (prosta, na której leży odcinek dzieli płaszczyznę na pół, sprawdzasz, czy punkt leży po właściwej stronie tej prostej; dla każdego odcinka).

0

Tak ale ja te wielokąty sam rysuję z odcinków i potem muszę je wypełnić kolorem, a przy kliknięciu mam pokazać komunikat, że punkt(piksel), w który kliknąłem należy lub nie do wielokąta.
To wygląda mniej więcej tak: http://zapodaj.net/72c751c9aa1a8.jpg.html
I jak kliknę tam gdzie jest na czarno wypełnione (tzn podczas wypełniania na czarno na przykład) ma mi wyświetlić że pkt leży w wielokącie albo nie.
Kod funkcji wypełniającej wygląda tak: http://ideone.com/uOKljr .

0

xxx
Dobra, nieważne. Teraz popatrzyłem jak to wygląda.

Tylko pojawia się pytanie jaki chcesz mieć wynik jeśli np te odcinki tworzą 2, albo więcej wielokątów.

@Edit.
Jeśli będzie to zawsze jeden to można wyliczyć punkty przecięcia tych odcinków (wszystkie punkty przecięcia) i połączyć je np według ruchu wskazówek zegara (zrobić otoczkę wypukłą).

Jeśli będzie więcej to byłoby to bardziej skomplikowane.

1

Jest do tego jakiś algorytm?

Jeśli wiadomo, że będzie to zawsze wielokąt składający się ze wszystkich punktów będących przecięciami tych odcinków to wystarczy posortować te punkty względem kąta pomiędzy jakimś punktem w środku tego wielokąta (może być nawet względem dowolnego punktu z punktów przecięć, wtedy tylko trzeba go pominąć), a każdym z punktów.

0

Ale jak mam uzyskać te punkty przecięcia? Funkcja która rysuje odcinki nigdzie nie zapisuje tych przecięć.
Nie mam pojęcia jak mam uzyskać te punkty, w których odcinki się przecinają.

1

Na internecie jest pełno kodów w C++ do wyliczenia punktu przecięcia 2 odcinków.
Możesz sobie nawet to samemu rozwiązać, bo nie jest to takie trudne.

0

Ok panowie. Zrobili my :)
Dzięki śliczne.
Zdrówka.

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