Алгоритм выпуклой оболочки Arduino

Question

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

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

Answer 1

Вам не нужно находить выпуклый корпус. Просто используйте формулу площади из набора точек, упорядоченных против часовой стрелки:

http://en.wikipedia.org/wiki/Polygon#Area_and_centroid

float totalArea = 0.0;
for(i=0; i<N; i++) {
    float parallelogramArea = (point[i].x*point[i+1].y - point[i+1].x*point[i].y)
    float triangleArea = parallelogramArea / 2.0;
    totalArea += triangleArea;
}
// or divide by 2 out here for efficiency

Формула площади получается из взятия каждого ребра AB и вычисления (подписанной) области между ребром и началом координат (треугольник ABO) путем взятия перекрестного произведения (которое дает вам площадь параллелограмма) и разрезания его в половина (коэффициент 1/2). При наложении вокруг многоугольника эти положительные и отрицательные треугольники будут перекрываться, и область между началом координат и многоугольником будет удалена и будет суммироваться до 0, при этом остается только область внутри. Вот почему формула называется формулой геодезиста, поскольку «геодезист» находится в начале координат; если идти против часовой стрелки, положительная область добавляется при движении влево -> вправо, а отрицательная область добавляется при движении вправо -> влево с точки зрения начала координат.

Математическая формула приведена ниже, но не обеспечивает интуицию за ней (как указано выше):

редактировать (после изменения вопроса)

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

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

• Если многоугольник выпуклый, все, что вам нужно сделать, это отсортировать по углу от некоторой произвольной точки внутри многоугольника (например, центроид трех произвольных точек).

Answer 2

Вы можете найти центр тяжести (cx,cy) точек и затем вычислить углы точек относительно (cx,cy).

angle[i] = atan2(y[i]-cy, x[i]-cx) ; 

Затем отсортируйте точки по углу.

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