Задан произвольный n-угольник через массив точек(x,y) с обходом против часовой стрелки

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

  Что такое "выпуклость многоугольника"?

Ну может не совсем правильно выразился. Имеется ввиду следующее:
Если внутренние углы при всех вершинах многоугольника меньше 180 градусов, то такой многоугольник называется выпуклым
Выпуклость соответсвенно - вершина при которой угол меньше 180 градусов


на рисунке многоугольник, все вершины кроме одной - выпуклые

Мне дан массив точек многоугольника, надо выяснить какие из них являются выпуклостями а какие нет.
Долго думал, но так и не нашёл путь к постороению алгоритма   

Закрасить. Если угол с крашеной стороны меньше - выпуклость, иначе впуклость.

хм, а как высчитать угол, если у меня есть координаты?

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

upd вспомнил, что угол можно найти через векторное произведение, буду пробовать)

Это сообщение отредактировал(а) loster - 11.9.2010, 00:10

закраска будет довольно накладной, мне кажется. И как например закрашивать многоугольник с дробными координатами?

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

Добавлено через 5 минут и 39 секунд
в самопересекающемся, область многоугольника можно так же задать положением относительно границ, тут только при пересечении границы будет меняться расположение области многоугольника на противоположное

Ну у тебя есть два отрезка с общей точкой, угол в которой и требуется определить. 

Задача решена здесь: http://irodov.nm.ru/cgi-bin/ikonboard/topi...=7&topic=33

Код: