--> Archiwum Forum
Cacek [ Konsul ]
Matematyka - pomóżcie, bo pamięć już nie ta ;-)
Sytuacja wyglada tak:
mamy uklad wspolzednych x,y. W ukladzie tym mamy;
1. Kwadrat o wierzcholkach A,B,C,D - znamy wspolzedne x,y kazdego z tych wiercholkow. Jak teraz sprawdzic czy punkt Z(x,y) nalezy do tego kwadratu czy nie nalezy? :)
2. Jak to policzyc dla prostokata?
(pewnie tak samo)
3. Jak to policzyc dla dowolnego czworokata?
(pewnie tak samo)
Bede bardzo wdzieczny za przypomnienie :-)
graf_0 [ Nożownik ]
Sposób wymyślony przeze mnie, być może niezgody z jakąś lepszą, optymalną metodą książkową.
wyliczasz 4 proste pomiędzy wierzchołkami. sprawdzasz czy punkt Z leży nad prostymi zamykającymi czworokąt od dołu i pod tymi, które zamykają go od góry. Jeśli tak, to punkt leży w czworokącie.
konioz [ Konsul ]
graf_0 ---> w sumie dobry sposob, ale jeszcze mozna go uproscic... najpierw sobie narysowac, jak beda trudne liczby (jakies pierwiastki itp.), to mniej wiecej widac, i tak pod ktorym bokiem lezy ten punkt, albo w jakich okolicach. Wtedy mozna policzyc tylko jedna prosta i czy ten punkt lezy (nad nia/ pod nia), a nie meczyc sie ze wszystkimi.
Cacek [ Konsul ]
Z tym rysowaniem, to troche odpada, bo musze z tego zrobic bardziej "algorytm" :) Dlatego chodzi mi o "metode" w krokach.
Romanujan [ Konstruktor Katapult ]
Hmm, no dobra - mój pomysł:
1. Wyznacz odcinki będące bokami czworokąta.
2. Weź punkt i poprowadź z niego półprostą w dowolnym kierunku.
3. Policz z iloma odcinkami-bokami przecina się półprosta - jeśli z parzystą liczbą, to punkt nie leży wewnątrz, jeśli z nieparzystą - leży wewnątrz.
Algorytm działa dla wszystkich wielokątów (nawet tych, które nie są wypukłe).
Romanujan [ Konstruktor Katapult ]
Acha, i przy liczeniu, z iloma bokami przecina się półprosta nie bierz czasem pod uwagę wierzchołków :-)
Cacek [ Konsul ]
Wielkie dzieki wszystkim za pomoc :)
Xerces [ Konsul ]
Jest jeszcze inny sposób. Musisz wyznaczyć równanie parametryczne tego wielokąta a potem algebraicznie sprawdzić, czy dany punkt do niego nalezy