DjangoBB LoFi version

Начало » Центр помощи » задача о многоугольнике

ZigertoN

Март 10, 2011 11:25:52

Добрый день. Возникли проблемы при решении задачи.
1.Написать программу чтоб можно было рисовать многоугольник. Зделал.

import pylab

xlist = []
ylist = []
print "Enter coordinat:"
q=1
a=0
while q == 1:
    x = raw_input("x:")
    xlist.append(x)
    y = raw_input("y:")
    ylist.append(y)

    if a == 1:
        if x==xlist[0]:
            if y==ylist[0]:
                q=0
    a =1

pylab.plot (xlist, ylist,
    linestyle = "-",
    marker = "o",
    color = "blue",
    markerfacecolor = "green")

Если можно написать код покрасивее то подскажите как.

2. Нужно чтоб программа могла определять выпуклый многоугольник или нет. Тут начались проблемки. Поискав в инете наткнулся на следующее:
http://delphid.dax.ru/www/exampl20.htm но увы делфи вообще не знаю, но как определить выпуклось понял. Проблема в том что не могу сообразить как реализовать…

3. Нужно чтоб программа могла определить какие точки нужно убрать чтоб многоугольник стал выпуклым если это не так. Предполагаю что этот пункт решится сам сабой если разберусь со вторым.

xyxel

Март 10, 2011 16:15:07

Как вариант:
проверить, находится ли точка (каждая вершина многоугольника) в многоугольнике (фигура, составленная из оставшихся вершин).
Алгоритм: http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%B2_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%B5
Если да - многоугольник вогнутый.

ZigertoN

Март 10, 2011 19:05:38

помогите разобраться с кодом

def inPolygon(x, y, xp, yp):
   c=0
   for i in range(len(xp)):
       if (((yp[i]<=y and y<yp[i-1]) or (yp[i-1]<=y and y<yp[i])) and \
           (x > (xp[i-1] - xp[i]) * (y - yp[i]) / (yp[i-1] - yp[i]) + xp[i])): c = 1 - c    
   return c

print( inPolygon(100, 0, (-100, 100, 100, -100), (100, 100, -100, -100)))

ZigertoN

Март 10, 2011 20:22:52

не получилось этот код приладить к себе. решил пойти другим путем. многоугольник будет вогнутым если внутрений угол будет больше чем 180 градусов.
Сейчас нужно посчить каждый угол при известный трех координатах.

doza_and

Март 10, 2011 22:50:31

Проверить, что все углы при последовательном обходе вершин имеют один знак.
Знак можно узнать через векторное произведение векторов двух соседних сторон (разница координат вершин).

ZigertoN

Март 27, 2011 14:11:35

помогите пожалуйсто разобраться с кодом

def inPolygon(x, y, xp, yp):
   c=0
   for i in range(len(xp)):
       if (((yp<=y and y<yp) or (yp<=y and y<yp)) and \
           (x > (xp - xp) * (y - yp) / (yp - yp) + xp)): c = 1 - c
   return c

print( inPolygon(100, 0, (-100, 100, 100, -100), (100, 100, -100, -100)))

ZigertoN

Март 31, 2011 19:24:51

ап