Как узнать, образует ли группа точек невыпуклую форму?

Question

Я хотел бы сделать триангуляцию многоугольника в THREE.JS, представленного группой 2d точек.Можно ли провести тест на массиве 2d точек, который покажет, имеет ли группа точек выпуклую или невыпуклую форму?Существует ли лучшая практика для такого рода триангуляции, которая будет хорошо работать как для выпуклых, так и для невыпуклых форм?

Answer 1

Предполагая, что у вас есть 2D-форма, определенная контуром, последовательность 2D-векторов в порядке CCW. Форма является выпуклой, если все пары последовательных ребер образуют левый (против часовой стрелки) контур. Вы можете убедиться в этом, представив два ребра в виде тройки точек, а затем вызвать leftOn(), который возвращает истину, если упомянутое свойство left задано или если точки коллинеарны.

function leftOn( a, b, c ) {

    return area2( a, b, c ) >= 0;

}

function area2( a, b, c ) {

    return ( ( c.x - a.x ) * ( b.y - a.y ) ) - ( ( b.x - a.x ) * ( c.y - a.y ) );

}

Подробнее об этом подходе вы можете прочитать в: Вычислительная геометрия в Си, Джозеф О'Рурк