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ę.
Punkty wewnątrz czworokąta
-
- 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
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.
-
- 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
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?
- 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?