Алгоритм добавления новой точки в многоугольник

Question

Привет всем,

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

http://i30.tinypic.com/1127ggk.jpg

Моя структура данных представляет собой двойной список следующим образом.

RzCurve {
   RzNode *head;
};


RzNode{
      double x;
      double y;
      RzNode *next;
      RzNode *prev;
}

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

Какие-нибудь советы по этому поводу?

С уважением, umanga

Answer 1

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

Answer 2

I будет проходить через все пары углов, вычислить биссектрису для двух углов. Если выбранная точка попадает в полуплоскость, определяемую двумя биссектрисами, и сегментом между двумя углами, то ваша точка должна быть добавлена ​​к текущему сегменту (т. Е. Новая точка соединяется с двумя исследуемыми углами).

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

Пример:

альтернативный текст http://img265.imageshack.us/img265/2098/134073347.png