Wielokąt wypukły.

Hej :) Mam do zrobienia zadanie, które sprawdza czy wielokąt jest wypukły. Z tego co już wiem jest jedna zależność co do kąta, jeśli przeciągniemy prostą wzdłuż tych dwóch punktów kąt ma znajdować się po prawej stronie i ma być większy od 0 stopni. Czyli cały czas idziemy w prawą strone.Musimy też założyć, że ma conajmniej 3 punkty, jeśli ma trzy punkty to one nie mogą leżeć na jednej prostej. Nie wiem jednak jak zapisać to w programie python. Proszę o pomoc :)
mam pomysł na początek, ale nie wiem jak dalej

X=[....]
Y=[....]
import.random
random.seed()
x=random.randint(0,len(X)-1)
y=random.randint(0,len(Y)-1)

 X=[....]
 Y=[....]
 import.random
 random.seed()
 x=random.randint(0,len(X)-1)
 y=random.randint(0,len(Y)-1)

Co to w ogóle jest? :|

---

**Najprościej** (ale nie najwydajniej) jest imho zrobić tak: sprawdzasz, czy linia poprowadzona pomiędzy dwoma dowolnymi różnymi nienastępującymi po sobie wierzchołkami koliduje z którąkolwiek z linii poprowadzonych pomiędzy dwoma następującymi po sobie wierzchołkami. Innymi słowy:  Kolizja linia-linia jest banalna, więc myślę, że nie powinieneś mieć z tym problemu ;)

tym początkiem chcialam założyć, że komputer wybiera sobie losowo jakieś punkty, ale nie wiem czy napisałam to dobrze

Najprościej (ale nie najwydajniej) jest imho zrobić tak: sprawdzasz, czy linia poprowadzona pomiędzy dwoma dowolnymi różnymi nienastępującymi po sobie wierzchołkami koliduje z którąkolwiek z linii poprowadzonych pomiędzy dwoma następującymi po sobie wierzchołkami.

Ale kombinujesz. Nie dość że algorytm O(n^2), to jeszcze wcale nie najprostszy ;].

Najprościej, jak pisała @AgnieszkaUp, iść po kolei po punktach i sprawdzać czy 'zakręt' jaki tworzą trzy kolejne punkty jest 'w prawo' czy 'w lewo'. Tzn. jeśli narysujesz wielokąt wypukły na ziemi i będziesz chodził po jego krawędziach, to zawsze będziesz skręcał w jednym kierunku - nigdy tak że raz w lewo, raz w prawo.

Tutaj luźna implementacja tego pomysłu, przy czym zakłada że wielokąt jest wierzchołkami w kierunku przeciwnym do ruchu wskazówek zegara (nie testowana dokładnie, ale powinno działać):

def sub(a, b): # odejmowanie "wektorów"
    return (a[0] - b[0], a[1] - b[1])

def cross(u, v): # cross product między wektorami
    return u[0] * v[1] - u[1] * v[0]

def is_convex(poly):
    p = poly + [poly[0], poly[1]] # żeby się warunkami brzegowymi nie przejmować
    for i in xrange(len(poly)):
        if cross(sub(p[i], p[i+1]), sub(p[i+1], p[i+2])) < 0:
            return False
    return True

(Cross product wektorów (a ściśle jego analogia w 2D) jest równy liczbowo |a|*|b|*sin(a, b), więc po jego znaku możemy zgadywać kierunek 'skrętu')

Trzy przykłady na których przetestowałem przed wysłaniem:

print is_convex([ (0, 0), (1, 0), (1, 1), (0, 1) ])
print is_convex([ (0, 0), (1, 0), (0.1, 0.1), (0, 1) ])
print is_convex([ (0.7, 0.7), (1, 0), (1, 1), (0, 1) ])

A mógłbyś wytłumaczyć mi jak to zrobiłeś, bo ja znam tylko instrukcje: for in range, if, return. Reszta jest dla mnie magią

Typowa odpowiedź na takie pytanie to sugestia poszukania tutoriala od podstaw języka. Szczególnie że mój kod korzysta w sumie tylko z tego co wymieniłaś. Nawet nie wiem o jakie instrukcje Ci chodzi:

• xrange? Można by wyjaśniać różnicę, ale w (dużym...!) uproszczeniu - to to samo co range, tylko szybciej działające.
• def? Def służy do definiowania funkcji. Popatrz np. tutaj - http://sapus.univ.szczecin.pl/~jakubs/py/py8.html
  No i tyle chyba.

Ew. jeśli nie pomogłem - sprecyzuj pytanie.

sub(a, b): == sub?
cross(u, v): == napisałeś ze jest to product między wektorami, ale co to oznacza?
def is_convex(poly): ==?
p = poly + [poly[0], poly[1]] # żeby się warunkami brzegowymi nie przejmować, nie rozumiem tego
for i in xrange(len(poly)): == długosc poly, ale co to jest to poly

trzeba również jakos zalozyc ze musi byc wiecej niz 3 punkty, jesli sa trzy to ze nie leza na jednej prostej, no i czy dobrze zaczęłam tam wczesniej, ze program losuje sobie jakies liczby, a potem sprawdza je

sub(a, b): == sub?
def is_convex(poly): ==?

Def służy do definiowania funkcji. Popatrz np. tutaj - http://sapus.univ.szczecin.pl/~jakubs/py/py8.html

cross(u, v): == napisałeś ze jest to product między wektorami, ale co to oznacza?

Cross product ściśle, na polski tłumaczone jako iloczyn wektorowy. Taka matematyczna operacja na wektorach. Ciekawą własnością jest że:

(Cross product wektorów (a ściśle jego analogia w 2D) jest równy liczbowo |a|*|b|*sin(a, b), więc po jego znaku możemy zgadywać kierunek 'skrętu')

|a| i |b| > 0, czyli znak iloczynu mówi nam o znaku sinusa kąta między wektorami - a z tego z kolei można wnioskować w którą stronę skręca obwód.
Samo udowodnienie dlaczego to działa może być trochę skomplikowane, ale wystarczy Ci wiedzieć że cross zwraca wartość iloczynu wektorowego między parametrami.

p = poly + [poly[0], poly[1]] # żeby się warunkami brzegowymi nie przejmować, nie rozumiem tego

W pętli bierzemy p[i], p[i+1] i p[i+2]. Pod koniec pętli byśmy w końcu wyszli poza wierzchołki, a my chcemy w tamtym momencie brać początkowe. Jedna opcja to brać poly[(i+1)%len(poly)], ale prościej tak jak zrobiłem.

for i in xrange(len(poly)):

Poly to wielokąt który sprawdzasz. Przekazany do funkcji.

Wydaje mi się że powinnaś poczytać jakiś kurs podstaw pythona / bardziej się przykładać na lekcjach, bo czarno to widzę :/