[C++] Wielokąt

[SilkyBoy]

Sprawa jest taka. Mam napisac program, który bedzie prezentowal dzielnice miasta i sprawdzal do jakiej dzielnicy nalezy dany punkt (wprowadzany z klawiatury). Inaczej mówiąc mam zrobic klase "wielokąt" w ktorej beda podane wierzcholki dzielnic i napisac do tego jakis algorytm sprawdzajacy w jakiej dzielnicy lezy wpisany przez nas punkt. Bez mapy bitowej (rysowanie tu nie potrzebne, bardziej chodzi o algorytm). Tylko nie berdzo wiem jak sie za to zabrac... Jakies podpowiedzi ?

[TSr]

Tak na szybko wymyśliłem takie rozwiązanie:
Każdy obszar można podzielić na trójkąty (łatwiej będzie sprawdzić czy punkt leży wewnątrz trójkąta).
Teraz to już geometria analityczna się kłania Bierzemy każde dwa wierzchołki trójkąta, przez które przeprowadzamy prostą i sprawdzamy czy nasz wskazany punkt leży po tej samej stronie prostej, po której leży trzeci wierzchołek rozpatrywanego trójkąta. Jeżeli wszystkie 3 testy wypadną pomyślnie to punkt leży wewnątrz trójkąta.

[Toster]

zalozenie 1:
Wielokat jest wypukly
Proponowane rozwiazanie: przepuszczasz prosa pinowa przez wskazany punkt liczysz ile razy przecioles wektory opisujace wielokat. Jesli liczba przeciec jest parzysta to jestes wewnatrz

Zalozenie 2:
Wielokat nie jest wypukly.
Proponowane rozwiazanie: podzial wielokata na trojkaty i sprawdzenie czy punkt najduje sie wewnatrz trojkata (alg. na sieci)

Operacje powyzej przeprowadzasz dla wszystkich wielokatow i wybierasz ten w ktorym sie znajduje punkt.

[Force]

Trudno powiedzieć czy poniższy link polecam, bo nie testowałem go, ale artykuł brzmi logicznie:
Link
I wtedy nie trzeba sprawdzać czy jest wewnątrz trójkątów lub rozpatrywać przypadki

[Iskar]

Pospiesz sie - zmień temat na bardziej opisowe i dodaj przedrostek [C++] albo ten temat raz dwa poleci do kosza.

[marek_haj]

proponuje kosz bo to znow ktos odrabia prace domowe na forum ...

[KaYou]

Na pclab moga ci odrobic zadanie domowe, tutaj sie nie pozywisz