Обоснованность алгоритма построения несамопересекающегося многоугольника

Question

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

---

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

Алгоритм:

Предположим, что существует множество V, содержащее все вершины

1) Сортировка всех вершин в V по x-координате

2) Представьте прямую линию (назовем ее «делителем»), параллельную оси x, которая, начиная с первого узла, расширяется до бесконечности и делит / разбивает вершины на два набора.

3) Теперь рассмотрим два набора:

A = Множество всех вершин выше или на разделительной линии

B = Множество всех оставшихся вершин

4) Начиная с самой левой вершины A, соедините все вершины в A, пока не дойдете до самой правой

5) Если крайняя правая вершина отсортированного множества V (вершина с наибольшей координатой x) не находится в A, соедините с ней последнюю вершину (крайнюю правую из A).

6) Работать задом наперед, начиная с крайней правой вершины отсортированного множества V (вершины с наибольшей координатой x), соединяя все вершины из B

7) Соединить первую (самую левую вершину B) вершину B с самой левой вершиной A

---

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

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

Answer 1

Вот контрпример.Когда шаг 5 не рисует линию, возможно самопересечение.

Answer 2

Я не уверен, что правильно понимаю, что вы пытаетесь сделать.В другой теме и в соответствующей теме по математике. SE (которая привела меня сюда), вы сказали, что у вас есть многоугольник и вы пытаетесь найти его центр тяжести.Здесь вы говорите, что у вас есть набор точек, и вы хотите построить из него непересекающийся многоугольник.Это две совершенно разные вещи.Как я упоминал в math.SE, если многоугольники, как известно, не являются выпуклыми, набор точек не однозначно определяет многоугольник - поэтому предлагаемый здесь алгоритм может построить некоторый произвольный не самопересекающийся многоугольник (у меня естьне проверил, успешно ли он это делает) но это может или не может иметь какое-либо отношение к многоугольнику, который вас изначально интересовал. Или я неправильно понял ваш вопрос в math.SE, и у вас на самом деле есть только некоторые точки и вы хотите построить только любойнесамопересекающихся полигонов от них и не волнует, что может быть несколько неэквивалентных решений для этого?

Answer 3

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

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

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

Форма обычно будет несколько звездообразной, но удовлетворяющей требованиям.

Выполнение вычислений будет выглядеть так:

• Перевести все точки в набор координат с началом [0,0] в одной из точек.
• преобразовать все точки в набор полярных координат
• сортировка по возрастанию по углу, по возрастанию по радиусу.
• соединить все точки в порядке сортировки.
• подключиться последним к первой ([0,0]) точке.

Answer 4

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

Кроме того, соединение (5) может привести к некоторым самопересечениям с созданными соединениямив точке (6)

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

Мы предполагаем, что множество вершин V конечно;)

Кроме этого - я верю, что ваше утверждение верно.

Answer 5

У меня была такая же проблема в javascript и библиотеке OpenLayers.Так что это мое решение для определения валидности многоугольника в слое «векторы» как OpenLayers.Layer.Vector:

var ps = vectors.features[0].geometry.getVertices(), i, j, inx, x1, x2, x3, x4, y1, y2, y3, y4, x43, x21, y21, y43, y31, maxx12, maxx34, minx12, minx34;
ps.push(ps[0]);
for(i = 0; i < ps.length -1 ; i++ ) {
  x1 = ps[i].x; x2 = ps[i+1].x;
  y1 = ps[i].y; y2 = ps[i+1].y;
  for(j = i + 2; j < ps.length -1 ; j++ ) {
    x3 = ps[j].x; x4 = ps[j+1].x;
    y3 = ps[j].y; y4 = ps[j+1].y;
    x43 = x4 - x3; x21 = x2 - x1; y21 = y2 - y1; y43 = y4 - y3; y31 = y3 - y1;
    inx = ( x43*y21*x1 - x21*y43*x3 + y31*x21*x43 )/( x43*y21 - x21*y43 );
    if( x1 < x2 ){
      minx12 = x1; maxx12 = x2;
    } else {
      minx12 = x2; maxx12 = x1;
    }
    if( x3 < x4 ){
      minx34 = x3; maxx34 = x4;
    } else {
      minx34 = x4; maxx34 = x3;
    }
    if (minx12 < inx && inx < maxx12 && minx34 < inx && inx < maxx34 ){
      console.log('intersected!'+' ,x1: '+x1+' ,x2: '+x2+' ,inx: '+inx+' ,i: '+i+' ,j: '+j);

      return;
    }
  }
}

надеюсь, вам понравится !!