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

Odpowiedz Nowy wątek
2013-09-30 22:25
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.

Pozostało 580 znaków

2013-09-30 22:42
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) ;)


Pozostało 580 znaków

2013-09-30 22:54
Algorytm
0

http://www.algorytm.org/geometria-obliczeniowa/

Pozostało 580 znaków

2013-10-01 07:53
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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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