Punkty kratowe wewnątrz i na bokach wielokąta.

0

Witam. Potrzebuję znaleźć algorytm, który dla wielokąta o dowolnej liczbie boków pozwoli mi wyznaczyć ilość punktów kratowych leżących wewnątrz wielokąta nie leżących na jego bokach, oraz algorytm, który pozwoli mi wyznaczyć ilość punktów kratowych leżących na jego bokach.

Mam daną ilość wierzchołków wielokąta, oraz ich współrzędne w układzie kartezjańskim.

Proszę o pomoc.

0

Jeśli rozwiązanie może być debilne/wymyślone na szybko:

Szukasz wierzchołka skrajnie na lewo.
Lecisz od jednego wierzchołka do drugiego zgodnie z ruchem wskazówek zegara i wyznaczasz równanie prostej na której leżą.
Wyznaczasz wszystkie punkty, które leżą wewnątrz wielokąta - na prawo od prostej.
Wyjdzie Ci z tego układ wielu równań. Punkty kratowe spełniają wszystkie z nich.
Możesz kombinować z wyznaczaniem y tak, żeby ograniczyć się do jednej pętli, ale jak może być debilne to:
Wyznaczasz krawędzie wszystkich wierzchołków (tak jakbyś miał wpisać ten wielokąt w kwadrat).
Zagnieżdżasz 2 pętle i sprawdzasz, czy punkty kratowe spełniają równanie. Liczysz ich sumę.

Co do punktów na liniach.
Masz równanie prostej i krawędzie. Szukasz całkowitych y spełniających równanie prostej.

Idę o zakład, że jeśli by to rozpisać to da się skrajnie uprościć, ale nie umiem(działaj) ;)

0

V=((Ax-Cx)*(By-Cy)-(Bx-Cx)*(Ay-Cy));
Ax,Ay - Bx,By - bok wielokąta
Cx,Cy - punkt
V = 0 punkt leży na tym boku
V < 0 punkt jest po lewej
V > 0 punkt jest po prawej

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