Проверка выпуклости снаружи

Question

Есть ли какой-либо метод или алгоритм для определения выпуклых (или невыпуклых) свойств области извне (периметр)?

Один из способов - построить касательную линию в каждой точке периметра и обсудить, сколько раз эта линия пересекает точки периметра. Если пересечение не показано (для всех точек периметра), мы можем заключить, что область является выпуклой. В противном случае область невыпуклая.

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

Есть ли еще более простые способы?

Любые идеи или решения будут оценены, спасибо.

Answer 1

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

Итак, все, что вам нужно сделать, это взглянуть на три вершины за раз, назвать их v_n, v_{n + 1} и v_{n + 2}. Затем вы можете определить, на какой стороне отрезка, соединяющего v_n и v_{n + 2,} находится вершина v_{n + 1}. Для CCW v_{n + 1} должно быть справа от отрезка, а для CW - слева. Существует ответ на другой вопрос, который обеспечивает метод для определения этого.

Есть дополнительные детали реализации, которые вы должны выработать (например, как работать с n=N, количеством точек в вашем многоугольнике, но это должно дать вам место для начала).

Реализация, основанная на этом подходе, будет выполняться в O(N) времени и пространстве.

ОБНОВЛЕНИЕ: В ответ на вопрос ниже, "как насчет неполигональных областей"? В общем, это намного сложнее. Математически можно показать, что область невыпуклая, найдя отрезок линии с конечными точками внутри области, но имеющий некоторую часть отрезка линии снаружи области. Я подозреваю, что вы ищете способ реализовать это с помощью цифрового компьютера, и поэтому чисто математический подход не практичен.

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

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

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

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

Answer 2

Алгоритм, который я использовал (в псевдокоде):

function isConvex(vertices[Count] V):
  convex = true
  if Count <= 3 return convex
  for N = 0 to Count while convex:
    // line segment between previous and subsequent vertices
    LineSegment segment1 = new LineSegment(
         V[(N + Count - 1) % Count], V[(N + 1) % Count]);
    // line segment between the point and any other point
    LineSegment segment2 = new LineSegment((V[N], V[N+2 % Count]);
    if not segment1.intersects(segment2) then convex = false;
  return convex

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

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

А также, что бы ни стоило, оригинал этого алгоритма был написан на ассемблере на процессоре, который больше не существует, поэтому я не буду предоставлять реальный код;-).