Как рассчитать площадь неправильной формы?

17

У меня есть объект комнаты, определенный набором циклических отрезков, для которого мне нужно вычислить площадь. Классы могут быть описаны следующим образом (в псевдокоде):

class Point {
    float x; 
    float y;
    ...
    float distanceFrom(Point p);
}

class Segment {
    Point start;
    Point end;
    ...
    float length();
}

class Room {
    List<Segment> walls;
    ...
    float area();
}

Стены комнаты никогда не могут пересекаться нигде, кроме как в конечных точках сегментов, и любые созданные «подциклы» также будут разделены на новую комнату. Решение не обязательно должно быть идеально точным (допустимая погрешность 10%) и также не очень часто (<1 / с).

algorithm geometry
источник
7
Было бы более целесообразно Roomсодержать список Points, а затем получить сегменты, соединив каждую точку вместе, а затем вернув ее обратно. В противном случае, с вашей текущей настройкой, это очень восточно, чтобы получить неправильные значения (например, незакрытая комната, комната со стеной посередине и т. Д.). Это был бы лучший вариант.
MCMastery
Другой вариант - верхняя триангуляция формы и вычисление площадей каждого треугольника. Трудной частью является триангуляция. Выполнимо, но не всегда красиво. Ответ от шнурка еще лучше.
Draco18s больше не доверяет SE
@MCMastery Это решение не будет работать, так как оно требует, чтобы Rooms всегда было завершено, и это может быть не так, если у меня есть игрок, который собирает Rooms, используя Segments. Кроме того, функцию закрытой комнаты легко определить (просто переберите Segments и убедитесь, что они создают комнату).

Ответы:

31

Вы можете использовать формулу шнурка Гаусса :

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

A = 0

for (i = 0; i < points.length; i++) do

    A += points[i].x * points[(i + 1) % points.length].y - points[i].y * points[(i + 1) % points.length].x

end

A /= 2
Балинт
источник
2
Я всегда использовал это, чтобы вычислить перекрестное произведение двух векторов, никогда не знал, что это было названо алгоритмом
Сидар
3
Обратите внимание, что это можно расширить, чтобы вычислить объем нерегулярного трехмерного объекта из треугольников, и это можно считать тривиальным случаем основной теоремы исчисления.
Дитрих Эпп
5
Площадь здесь подписана. Пройдите точки в другом направлении, и финал Aотменяется. В зависимости от цели, A = |A|может понадобиться. С помощью отрицательного кода области можно найти область на неправильном пончике, используя внутренний и внешний список точек (один в обратном порядке).
chux - Восстановить Монику
6
Потому что, конечно, у Гаусса или Эйлера есть формула для этого.
CorsiKa
0

Мы также могли бы использовать метод Монте-Карло.

Нарисуйте прямоугольник вокруг произвольной формы. Возьмите равномерно распределенный источник PRNG, например. Mersenne Twister, а затем ограничить выход по X, Y длины прямоугольника, используя функцию по модулю. Считайте нет. случайных точек, которые приземляются внутри вашей фигуры. Разделите на общее количество полученных баллов. Умножьте это отношение на площадь прямоугольника. С каждой итерацией вы будете сходиться к истинной области. Алгоритм смехотворно распараллеливается и может использоваться для вычисления произвольных размерных «объемов» фигуры, при условии, что вы можете определить, находится ли координата R ^ N в пределах границы R ^ N фигуры.

,

Здесь кто-то использует этот метод, чтобы найти область круга, а затем использует его для вычисления числа пи https://www.youtube.com/watch?v=VJTFfIqO4TU.

FranG
источник
2
-1: Вы не хотите использовать модуль по модулю, чтобы получить его в диапазоне, вы хотите использовать равномерное распределение или другое распределение, делая это по модулю, имеет все виды статистических проблем.
user1997744
12
Этот метод может быть полезен, когда у нас нет простого многоугольника, а есть некая неявная форма, границу которой трудно выразить, например, фрактальный шарик или метабол. Однако в случае многоугольника, как в вопросе, кажется, что это будет излишне дорого.
DMGregory
Как указал @DMGregory, это не то, что я искал. Тем не менее, я думаю, что это заслуживает +1, если кому-то еще это нужно.
Это интересно, но не станет ли стоимость тестов на включение слишком высокой? То есть, если у вас есть форма, которая достаточно сложна, чтобы оправдать такой подход, разве тесты на включение не будут действительно дорогими, поэтому вы не захотите делать их тоннами? (в предположении многоугольников)
Маттиа
Хорошо, по модулю действительно проблематично, но это простое решение. Что мы действительно получаем, так это случайные P = 1/2 биты 0/1, поэтому мы получаем равномерное распределение чисел, например. для 3 битов от 0 до 7. Выполнение rand% 5, если случайное число принимает значение 6 или 7, преобразуется в 1 или 2, эффективно увеличивая 1,2, делая распределение неравномерным. Чтобы избежать этого, вам нужно что-то вроде конечного автомата, который вращает отображение, например. 6,7 карты до 1,2, затем до 3,4, затем 5,0, и это продолжается. Мы также могли бы выбросить 6,7, когда они подошли. Во всяком случае, это проблема реализации библиотеки.
FranG
-1

Другой подход: не надо.

Вместо:

while (Segments.Count > 3)
{
    Segment A = Segments[Segments.Count - 2];
    Segment B = Segments[Segments.Count - 1];
    Segment C = new Segment(B.End, A.Start);
    Triangle T = new Triangle(A, B, C);
    Segments[Segments.Count - 2] = C;
    Segments.RemoveAt(Segments.Count - 1);
    if (B is inside the new shape Segments)
        Area -= T.Area;
    else
        Area += T.Area;
}
Area += new Triangle(Segments[0], Segments[1], Segments[2]).Area;

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

Лорен Печтель
источник
2
Формула Гаусса «Шнурки» - это сокращение, которое вдвое сокращает количество вычислений. Проработай это.
Питер Гиркенс