Выпуклость многоугольника C ++?

Как я могу проверить, является ли многоугольник выпуклым или нет, только зная точки многоугольника с их координатами в c ++?


c++ algorithm computational-geometry polygon convex
person user2116010    schedule 03.03.2013    source источник
comment
Конечно, вы не ожидаете, что мы предоставим вам полный исходный код для такой проблемы. Что ты пробовал? Вы застряли в алгоритме? Разве вы не знаете, как сформулировать алгоритм на C ++?   -  person Oswald    schedule 04.03.2013
comment
Вы можете пройти по точкам одну за другой, взять двух соседей текущей точки, а затем использовать теорему косинусов, чтобы узнать угол, заключенный между этими тремя точками. Если вы найдете угол больше 90 градусов, то многоугольник вогнутый, если нет углов больше 90 градусов, то он выпуклый.   -  person    schedule 04.03.2013
comment
Я пробовал этот способ, но не знаю, как определить, внутренний это угол или внешний, потому что мне нужен внутренний   -  person user2116010    schedule 04.03.2013
comment
@ user2116010 Теорема косинусов всегда дает меньший угол. Затем вы можете определить, является ли это внутренним или внешним углом, по относительным координатам x и y центральной точки относительно двух других точек.   -  person    schedule 04.03.2013

Ответы (3)


arrow_upward
3
arrow_downward

Для каждой стороны многоугольника вычислите линейное уравнение (Ax+By+C=0) и проверьте (поместите x и y в уравнение и получите его знак), что все точки находятся с одной стороны от него.

РЕДАКТИРОВАТЬ: если вы путешествуете по выпуклому многоугольнику, вы всегда будете вращаться в одном направлении (влево или вправо) в каждой точке. Используя кросс-произведение, вы можете просто определить, на какую сторону (отрицательную или положительную) вы будете вращать следующий поворот. Если все перекрестные произведения трех последовательных точек будут иметь знак равенства, то ваш многоугольник выпуклый.

person hate-engine    schedule 03.03.2013

arrow_upward
1
arrow_downward

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

Это O (n log n), но не основывается на предположении, что точки указаны в правильном порядке по краям многоугольника. Если предположение верно, то ответ от hate-engine будет оптимальным (т.е. линейное время).

person Rafał Dowgird    schedule 03.03.2013

arrow_upward
1
arrow_downward

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

Псевдокод из wiki:

jarvis(S)
   pointOnHull = leftmost point in S
   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]  // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|-1
         if (endpoint == pointOnHull) or
            (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0] // wrapped around to first hull point

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

person masoud    schedule 03.03.2013