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

Question

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

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

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

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

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

Answer 1

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

Таким образом, все, что вам нужно сделать, это искать три вершины, в то время, называть их v _п, v _{п + 1} и v _{п + 2}. Затем можно определить, какая сторона сегмента линии, соединяющей v _п и v _{п + 2}вершину v _{п + 1} сидит на. Для CCW v _{n + 1} должен находиться справа от отрезка линии, а для CW - слева. Существует answer to another question which provides метод определения этого.

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

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