Punkty wewnątrz czworokąta

Wielokąty (n>3). Okręgi. Inne figury płaskie. Zadania i twierdzenia z nimi związane. Geometria rzutowa na płaszczyżnie.
szalejot
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 21 kwie 2011, o 10:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy

Punkty wewnątrz czworokąta

Post autor: szalejot »

Piszę pewien program i mam problem w jednym z kroków:

Dany mam zbiór punktów na płaszczyźnie (każdy jako para współrzędnych (x,y), współrzędne to całkowite liczby dodatnie). Oraz współrzędne wierzchołków czworokąta wypukłego (też same całkowite liczby dodatnie). Muszę znaleźć te punkty, które są wewnątrz tego czworokąta.
Mogę sprawdzać punkt po punkcie, zależy mi na tym, żeby metoda była w miarę prosta obliczeniowo (ze względu na wydajność programu) oraz, żeby działała dla każdego czworokąta wypukłego.

Za pomysły/podpowiedzi z góry dziękuję.
piasek101
Użytkownik
Użytkownik
Posty: 23493
Rejestracja: 8 kwie 2008, o 22:04
Płeć: Mężczyzna
Lokalizacja: piaski
Podziękował: 1 raz
Pomógł: 3263 razy

Punkty wewnątrz czworokąta

Post autor: piasek101 »

Może z tego, że punkty wewnętrzne czworokąta (ich współrzędne) mają spełnić układ odpowiednich nierówności - dotyczących prostych na jakich leżą boki czworokąta.
szalejot
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 21 kwie 2011, o 10:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 2 razy

Punkty wewnątrz czworokąta

Post autor: szalejot »

Wpadłem na pomysł taki: (chyba powinien działać)

- wierzchołki ułożyłem w takiej kolejności, żeby iść po czworokącie zgodnie z kierunkiem wskazówek zegara)
- zamieniłem boki na wektory
- sprawdzam, czy punkt leży po "prawej" stronie wektora (za pomocą iloczynu skalarnego)

Jak leży po "lewej" stronie któregoś z wektorów tworzących boki to odrzucam, jako nienależący do czworokąta.
Powinno działać, nie?
ODPOWIEDZ