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

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

Итак, все, что вам нужно сделать, это взглянуть на три вершины одновременно, назовите их v _n, v _{n + 1 < / sub> и v n + 2. Затем вы можете определить, с какой стороны отрезка линии v n и v n + 2 вершина v n + 1 сидит на. Для CCW, v n + 1 должен быть справа от линейного сегмента, а для CW он должен быть слева. Существует ответ на другой вопрос, который предоставляет метод определения этого.}

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

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

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

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

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

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

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

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

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 текущей итерации, что делает его более быстрым, но более сложным для записи даже в псевдокоде.

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