есть многоугольник (к новому году, рассмотрим ёлку    ) ...



многоугольник представлен двумерным массивом [ 7, 3 ] - 7 точек по 2 координаты (х,y) и угол альфа при этой вершине.

этот самый внутренний угол альфа и надо найти для каждой вершины ёлки.

ну хорошо, дам свои соображения))

для i-ой вершины имеем: 
1) найти угол альфа при i-ой вершине в треугольнике (i-1 , i ,  i+1)  (ясно, что в треугольнике он обязан быть меньше 180 градусов => проверка если нет, то альфа = альфа - 180)  
2) найти точку M [x,y] середины отрезка между соседними (i-1 и  i+1) вершинами.
3) выяснить, внутри или снаружи многоугольника находится М.
4) если снаружи, то альфа=360 - альфа 


способ тупой, ибо упирается в не менее сложную проблему определения положения М относительно многоугольника.

+ эта проблема усложниться, если в ёлке будет дырка   

А противоположно лежащие прямые параллельны? (1,2 // 6,7) (1,6 // 2,3) ну и т.д.

случай берем общий. в ёлке могут быть и дырки!



Это сообщение отредактировал(а) CompWorm - 6.1.2009, 16:19

Может сперва разобраться с параллельными!! 
Там хотя бы будут противоположные, вертикальные, накрестлежащие углы...

Dobermann, 
а с остальными то что делать? распиши свой алгоритм пожалуйста.
            в условии сказано: есть массив с вершинами...
ну вот у тебя координаты точек... ты собираешься сперва выяснить что чему параллельно и решить задачу для этих случаев, а потом подумать над еще одним алгоритмом для остальных?   
ИМХО, этот второй алгоритм как раз будет универсальным и для параллельных прямых.


я почесал репку и придумал такой довольно универсальный вариант определения положения точки М...

необходимо определить для каждой пары вершин, образующих отрезок, пересекается ли этот отрезок с горизонтальным лучом, пущенным из точки М. если  горизонтальный луч пересек нечетное число отрезков - значит М внутри многоугольника. если четное - вне многоугольника.
просчитываем это дважды - для левой и правой полуплоскости относительно вертикали через точку М
  


отсюда вопрос к тем, кто силён в математике - как узнать, пересек ли луч отрезок?    

Это сообщение отредактировал(а) CompWorm - 6.1.2009, 17:00

Алгоритм в принципе не плох, только зачем 2 луча если можно ограничиться одной горизонтальной прямой. Но он ни к чему...


А зачем вообще отрезок?!! Не усложняй!! Ведь даны координаты Х и У всех точек!!!
Ну ведь же у точки М есть свои координаты...вот координатами и сравнивать, по другому никак, ток в координатах числа есть...Плоскость ведь у тебя одна - ХУ, т.е. можно сравнить координату Х точки М, с координатами Х точек твоей елки. Так же с У. 
Вопрос только один, у точки М есть координаты?

Пересекает ли луч отрезок. Есть уравнение луча. Не проблемма найти уравнение для прямой, содержащей отрезок. Найти координату пересечения и проверить её на принадлежность отрезку.

Если я правильно поняла задачу, то нужно найти выпуклую оболочку, а все невходящие в нее вершины и будут внутренними. Правда, не совсем понятно, как быть с дырками... что такое "внутренний угол", для контура дырки...

Добавлено через 12 минут и 40 секунд
А нет, неправильно поняла... нужно просто вычислить все углы. 
Тогда я бы предложила вместо проверки точки внутри-снаружи (что тоже можно) проверять конечную точку второго отрезка каждой пары. Если она с той же стороны от прямой, проходящей через первый отрезок, что и весь многоугольник, то угол выпуклый, иначе - вогнутый. Если ориентация контура заранее неизвестна (т.е. с какой стороны от контура внутренность многоугольника), нужно просто вычислить его площадь со знаком. Это эффективнее, чем для каждой пары отрезков вычислять "внутри-снаружи", т.к. требуется только один проход по отрезкам для вычисления плошади + фиксированная формула для каждого отрезка. А проверка "внутри-снаружи" требует прохода по всем отрезкам для каждой такой проверки.

Добавлено через 14 минут и 6 секунд

Ага, почесал... теорема Жордана это называется

  

ну, я не математик, а русская смекалка помогает изобретать велосипеды   

так, посмотрим что же у меня получилось из описанного выше материала.

код привожу на Delphi.

строить будем симметричную ёлку (для наглядности), хотя можно и что угодно другое.


основная функция GetAlpha, после, скажем, нажатия кнопки,
в цикле вызывается для каждой вершины VrtN
вот, собсно, она сама


тут для i-ой вершины имеем: 
1) находим угол альфа при i-ой вершине в треугольнике (i-1 , i ,  i+1)  он всегда<180
2) для определения с какой стороны он фигуры, находим точку M [x,y] середины отрезка между соседними (i-1 и  i+1) вершинами.
3) и юзаем проверку if PointInPolygon

последняя решается моим "велосипедом"   

по словам Earnest, мы используем теорему Жордана 
смысл в том, что если горизонтальный луч пересекает нечетное
число отрезков, образуемых граничными точками, то наша точка внутри.

определить, пересекает ли горизонтальный луч
идущий вправо из точки M[X ; Y] данный отрезок
ИМХО, проще всего ориентируясь на принадлежность точки луча отрезку.
то есть, если на отрезке есть такая точка К[x > X ; Y],
то отрезок пересекается.
принадлежность точки выражается равенствами:
    P * x1 + (1-P) * x2 = x
    P * y1 + (1-P) * y2 = y
    0 >= P >= 0
тогда, зная y=Y получаем P = (y-y2) / (y1-y2)
теперь осталось сравнить, есть ли такая точка,
что P * x1 + (1-P) * x2 > X
случай когда конец отрезка лежит на луче P=0 или Р=1
необходимо разрешить просчитывать лишь для одного из отрезков...
например, только для первого: 0 >= P > 0




  

жду комментов, критики и оптимизаций   

Это сообщение отредактировал(а) CompWorm - 6.1.2009, 23:50

Присоединённый файл ( Кол-во скачиваний: 3 )
 ___________________.rar 176,64 Kb

Ну так работает?

тестирую.
у меня пока все работает...

Что-то я вашего алгоритма не понимаю.
Вот будет у нас такая фиговина, например:
(0,0), (1,1), (2,0), (1,4).
Посмотрим на угол ((0,0), (1,4), (2,0)). Очевидно, этот угол внутренний. Ваш алгоритм возьмёт середину (получится точка (1,0)), и она окажется вне многоугольника, из чего он сделает вывод, что этот угол не внутренний.

Я поддерживаю алгоритм Earnest - посчитать площадь со знаком, по ней понять направление обхода многоугольника, и просто обойти многоугольник в нужном направлении, каждый раз проверяя, куда направлена текущая тройка точек (p[i-1], p[i], p[i+1]).
Да и кодить тут всего-ничего придётся.

maxdiver, 
вы невнимательно читали. конкретно в вашей задаче, луч пройдет из средней точки и далее через (2,0), засчитав его как пересечение.

но вы частично правы, если немного видоизменить ваше услокие 
(0,0), (1,3), (2,1), (1,4).
то задача нерешабельна моим алгоритмом.    это я малость упустил.

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

Это сообщение отредактировал(а) CompWorm - 7.1.2009, 00:13