Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Определить выпуклость

Автор: loster 10.9.2010, 20:13

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

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

Автор: Akina 10.9.2010, 20:57

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

Автор: loster 10.9.2010, 22:13

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

user posted image

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

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

Автор: Akina 10.9.2010, 22:34

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

Автор: loster 10.9.2010, 23:42

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

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

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

Автор: nmn 11.9.2010, 00:50

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

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

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

Автор: W4FhLF 11.9.2010, 09:39

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

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

Код:

Код


bool IsSharp(POINT P0,POINT P1,POINT P2) 
{ 
     __int64 Xa,Ya,Xc,Yc; 
      
     Xa=P2.x - P1.x; 
     Ya=P2.y - P1.y; 
     Xc=P0.x - P1.x; 
     Yc=P0.y - P1.y; 

     float Ang; 
     Ang=((Xa*Yc-Xc*Ya)/(sqrt(Xa*Xa+Ya*Ya)*sqrt(Xc*Xc+Yc*Yc))); 
    
     if (Ang>0) return false; 
     else return true; 
}