Mam n wierzchołków: 0,1,2,..n-1
Teraz chcę sprawdzić czy są podane w kolejności zgodnej z ruchem
wskazówek zegara czy przeciwnej,
Inaczej: gdy mamy zgodnie z ruchem wskazówek zegara, wtedy po prawej
stronie każdej krawędzi mamy wnętrze wielokąta a po lewej pustą
przestrzeń. (gdy idziemy wraz z krawędziami mając i-tą na dole a
i+1-szą u góry)
To jest potrzebne do algorytmu wyznaczania unii wielokątów metodą
Weilera-Athertona dla którego to algorytmu wymagana jest taka sama
orientacja obu wielokątów, gdy by była różna, mógłbym jeden z nich
odwrócić, ale jak to sprawdzić??
Jakieś wyznaczniki? przy czym liczy się całość wielokąta, bo najpierw
może zakręcać w jedną stronę a później zmienić kierunek.

do góry

W dniu 2014-10-30 o 15:55, Borneq pisze:
> wskazówek zegara czy przeciwnej,
> Inaczej: gdy mamy zgodnie z ruchem wskazówek zegara, wtedy po prawej
> stronie każdej krawędzi mamy wnętrze wielokąta a po lewej pustą

http://stackoverflow.com/questions/1165647/how-to-de
termine-if-a-list-of-polygon-points-are-in-clockwise
-order

Czy na pewno zadziała metoda sumowania (x2-x1)(y2+y1), wyjątkowo prosta
a podobno działa na niewypukłych i nawet samoprzecinających się

do góry

On 30.10.2014 15:55, Borneq wrote:
> Mam n wierzchołków: 0,1,2,..n-1
> Teraz chcę sprawdzić czy są podane w kolejności zgodnej z ruchem
> wskazówek zegara czy przeciwnej,
> Inaczej: gdy mamy zgodnie z ruchem wskazówek zegara, wtedy po prawej
> stronie każdej krawędzi mamy wnętrze wielokąta a po lewej pustą
> przestrzeń. (gdy idziemy wraz z krawędziami mając i-tą na dole a
> i+1-szą u góry)
> To jest potrzebne do algorytmu wyznaczania unii wielokątów metodą
> Weilera-Athertona dla którego to algorytmu wymagana jest taka sama
> orientacja obu wielokątów, gdy by była różna, mógłbym jeden z nich
> odwrócić, ale jak to sprawdzić??
> Jakieś wyznaczniki? przy czym liczy się całość wielokąta, bo najpierw
> może zakręcać w jedną stronę a później zmienić kierunek.

Nie masz jakiś warunków na ten wielokąt? Np nieprzecinające
się krawędzie?
Pentagram, z punktami w kolejności rysowania, jest prawo
czy lewoskrętny? ;-)

pzdr
bartekltg

do góry

W dniu 2014-10-30 o 19:47, bartekltg pisze:
> Nie masz jakiś warunków na ten wielokąt? Np nieprzecinające
> się krawędzie?
> Pentagram, z punktami w kolejności rysowania, jest prawo
> czy lewoskrętny? ;-)

Gdy w pentagramie mam punkt początkowy u góry, to gdy następny róg
będzie bardziej po prawej stronie to mamy zgodnie z ruchem wskazówek
zegara. Ciekawe tylko czy algorytm który podąłem ze StackOverflow
poradzi sobie nie tylko z niewypukłymi ale także z samoprzecinającymi
się. Zresztą to bardzo prosty a dobry algorytm, znak pokazuje orientację
a połowa wielkości bezwzględnej pole wielokąta, który nie musi być wypukły

do góry

On 30.10.2014 16:21, Borneq wrote:
> W dniu 2014-10-30 o 15:55, Borneq pisze:
>> wskazówek zegara czy przeciwnej,
>> Inaczej: gdy mamy zgodnie z ruchem wskazówek zegara, wtedy po prawej
>> stronie każdej krawędzi mamy wnętrze wielokąta a po lewej pustą
>
> http://stackoverflow.com/questions/1165647/how-to-de
termine-if-a-list-of-polygon-points-are-in-clockwise
-order
>
>
> Czy na pewno zadziała metoda sumowania (x2-x1)(y2+y1), wyjątkowo prosta
> a podobno działa na niewypukłych i nawet samoprzecinających się

Zadziała, bo to jest zorientowane pole powierzchni.

Matematycznie, forma powierzchni to dx^dy. (to nie potegowanie
tylko iloczyn zewnętrzny). Tw Stokesa i całka po powierzchni
zamienia się po na całkę po brzegu z formy pierwotnej.
Formą pierwotną jest m.in (nie jets wyznaczona jednoznacznie)
y*dx. Po pocałowaniu tego pomiędzy punktami (x1,y1) i (x2,y2)
dostajesz właśnie 0.5(x2-x1)(y2+y1). Aby całość miała sens,
musisz przejść po krzywej zamkniętej.

>
> Gdy w pentagramie mam punkt początkowy u góry, to gdy następny róg
> będzie bardziej po prawej stronie to mamy zgodnie z ruchem wskazówek
> zegara.

Zupełnie mnie to nie przekonuje.

> Ciekawe tylko czy algorytm który podąłem ze StackOverflow
> poradzi sobie nie tylko z niewypukłymi ale także z samoprzecinającymi
> się. Zresztą to bardzo prosty a dobry algorytm, znak pokazuje
> orientację a połowa wielkości bezwzględnej pole wielokąta, który nie
> musi być wypukły

Dostajesz wzór na zorientowaną powierzchnię (każdy element powierzchni
liczysz z taką wagą, ile razy obiega go łamana, licząc w drugą stronę
jako -1). I jak wielkokat jest porządny, to taka definicja jest zgodna
z nasza intuicją. Ale czy to zawsze jest zgodne z definicją, której
wymaga Twoj algorytm - tego na razie nie wiemy.

pzdr
bartekltg

do góry

W dniu 2014-10-30 o 20:31, bartekltg pisze:
>> Gdy w pentagramie mam punkt początkowy u góry, to gdy następny róg
>> będzie bardziej po prawej stronie to mamy zgodnie z ruchem wskazówek
>> zegara.
>
> Zupełnie mnie to nie przekonuje.

Opiszmy 5 punktów na okręgu podobnie jak w zegarze, tylko będziemy mieli
0 na górze, potem 1 aż do 4
z 0 idziemy do punktu 2, tu mamy kreskę, jeszcze nie wiadomo jaka
orientacja, potem idziemy do punktu 4, widać że skręciliśmy zgodnie z
ruchem zegara, gdybyśmy teraz z 4 poszli do 0 otrzymali byśmy trójkąt
zgodnie z ruchem zegara, ale mijamy, idziemy do 1, i zrobiliśmy dwa
obroty zgodnie z ruchem wskazówek zegara.
Ciekawe jakby to teraz sprawdzić tym algorytmem, to powiedziałbym w
którą stronę.

do góry