Как определить смещение метки, чтобы метка всегда находилась снаружи полигона?

Question

У меня есть несколько вершин многоугольника с метками на них.Я хочу разместить метки так, чтобы они всегда находились снаружи полигона.Таким образом, на изображении выше все надписи в порядке, кроме # 3 и # 4, которые я хочу расположить снизу, вне полигона.Так в общем, как определить для конкретной вершины, как сместить ее так, чтобы она находилась вне многоугольника?

Answer 1

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

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

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

Answer 2

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

Я предполагаю, что многоугольник считается простым многоугольником, который не пересекается сам по себе.Если многоугольник пересекает сам себя, определение его «внутри» не так однозначно, и существует несколько определений внутренней части.Я не буду считать, что многоугольник выпуклый - все внутренние углы меньше 180 °.(Это позволит получить более простой ответ.) Я также предполагаю, что вы хотите, чтобы центр вашей метки находился вне многоугольника, но позволил бы углу или небольшой части метки находиться внутри.

Во-первых,Пройдите через многоугольник и найдите его «угол намотки», величина, на которую угол направления изменяется во время обхода.Если многоугольник простой, угол будет либо + 180 °, либо -180 °.Один из них означает, что вы прошли многоугольник по часовой стрелке, а другой - против часовой стрелки.(Это зависит от вашей системы координат: декартовой, графической или другой.)

Затем снова обведите полигон.Теперь, когда вы знаете направление многоугольника, в каждой вершине вы можете определить, идет ли внешний угол по часовой стрелке или против часовой стрелки от входящего сегмента.Найдите это направление и размер угла, затем сдвиньте половину этого угла в этом направлении.Переместитесь на заданное расстояние от вершины вдоль этого угла, и у вас будет положение центра вашей метки.

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

Я дал ответ на связанный вопрос: Как эффективно определить, является ли многоугольник выпуклым,невыпуклый или сложный? .

Answer 3

Может быть, что-то вроде этого: во-первых, убедитесь, что многоугольник не пересекается сам, смотрите предыдущие ответы. Затем, пусть многоугольник ориентирован против часовой стрелки и представлен массивом (матрица 2 на n + 2) его вершин (вершины пройдены против часовой стрелки)

double P[n+2][2] = {{pxn, pyn}, {px1, py1}, {px2, py2},  ...,  {pxn, pyn}, {px1, py1}};
double Label_position[n][2];

void generate_labels(const double (&P)[n+2][2], double (&Label_position)[n][2]){

   double v1[2];
   double v2[2];

   for(j = 1, j <= n, j = j+1) {

      v1[0] = P[j][0] - P[j-1][0];
      v1[1] = P[j][1] - P[j-1][1];
      v2[0] = P[j+1][0] - P[j][0];
      v2[1] = P[j+1][1] - P[j][1];

      v1 = normalize(v1);
      v2 = normalize(v2);

      t = add_vectors(v1, v2);
      t = normalize(t);

      Label_position[j][0] = t[1] + P[j][0];
      Label_position[j][1] = - t[0] + P[j][1];  
   }
}

Эта функция генерирует координаты точек на кончиках биссектрисы векторов углов, указывающих на внешность многоугольника (см. ответ Ива Дауста и сгенерированное им изображение).