Определите, можно ли нарисовать 2d-многоугольник с одним треугольным веером

Сначала я думал, что эта задача будет эквивалентна определению выпуклости многоугольника, однако, похоже, что невыпуклый многоугольник все еще может быть нарисован одним треугольным веером. Рассмотрим такую форму , как невыпуклый многоугольник. Можно легко представить себе некоторую область центральных точек, которая позволила бы нарисовать этот многоугольник с треугольным веером (хотя были бы и другие центральные точки, которые этого не сделали бы). Учитывая фиксированную центральную точку, я хочу иметь возможность определить, если набор 2d точки, определяющие многоугольник, позволяют рисовать его одним треугольным веером.

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

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

3 11
c++ geometry computational-geometry

3 ответа:

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

Это будет выглядеть примерно так: 

vector lastCross = cross_product( vector(vertex[0] - center), vector(vertex[numVerts - 1] - center) );

canBeFan = true;
for (n = 1; canBeFan && n < numVerts; ++n) {
    vector testCross = cross_product( vector(vertex[n] - center), vector(vertex[n - 1] - center) );
    if (0.0 >= dot_product(testCross, lastCross) ) {
        canBeFan = false;
    }
}
2

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

Чтобы проверить, что многоугольник имеет форму звезды, можно построить область, из которой будет виден весь многоугольник. Эта область будет выпуклым множеством, поэтому вы можете пересечь ее с полуплоскостью в O(log(n)).

Это означает, что вы можете пересечь полуплоскости, образованные ребрами, и проверить, что результирующая область видимости непусто в O(n log n).

13

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

Как говорит @jpalecek, термин для этого- звездообразный . Если ваш многоугольник имеет форму звезды, то будет выпуклый многоугольник (внутренний по отношению к оригиналу), точки которого могут видеть все ребра оригинала-и, наоборот, если такого под-многоугольника не существует, оригинал не является в форме звезды, и вы не можете нарисовать его треугольным веером.

Определение этого подугольника является в основномдвойным применением задачивыпуклой оболочки ; она может быть вычислена в O(n log n).

1