Вычислить площадь из гео-координат на невыпуклых многоугольниках

Question

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

Из этого полигона дорожки я бы хотел вычислить площадь, в которой находится дорожка. Для выпуклых полигонов это не должноЭто не проблема, так как я думаю, мне просто нужно вычислить площадь треугольников (когда у каждого треугольника есть одна начальная точка в первой точке).В основном, как показано на левом изображении.(Желтый многоугольник - это многоугольник, созданный из GPS-местоположений, темные линии показывают треугольники для расчета площади, светло-желтый - желаемая область)

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

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

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

Было бы здорово, если бы кто-нибудь мог помочь мне с этим! Спасибо!

Answer 1

Вы можете взглянуть на общую формулу для площади многоугольника: http://mathworld.wolfram.com/PolygonArea.html. Это также охватывает случай невыпуклых многоугольников (если они не являются самопересекающимися).

Answer 2

Я делаю это все время, но я не знаю алгоритм, потому что я использую библиотеку, такую ​​как GEOS в C / C ++, JTS в Java или Shapely в Python.

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

Answer 3

Немного поздно, но я только что реализовал это в Java для координат GPS.Вы должны нормализовать координаты GPS, как описано здесь: Расчет площади многоугольника с использованием широты и долготы, сгенерированных из декартового пространства и файла мира .Работает хорошо, но есть погрешность около 0,005%, потому что декартовы координаты являются приближением, основанным на идеальном радиусе Земли.В приведенном ниже коде предполагается использование пар типа [долгота, широта] geojson, а не наоборот.

public static double area(double[][] polygon) {
    Validate.isTrue(polygon.length > 3,"polygon should have at least three elements");

    double total=0;
    double[] previous=polygon[0];

    double[] center = polygonCenter(polygon);
    double xRef=center[0];
    double yRef=center[1];


    for(int i=1; i< polygon.length;i++) {
        double[] current = polygon[i];
        // convert to cartesian coordinates in meters, note this not very exact
        double x1 = ((previous[0]-xRef)*( 6378137*PI/180 ))*Math.cos( yRef*PI/180 );
        double y1 = (previous[1]-yRef)*( Math.toRadians( 6378137 ) );
        double x2 = ((current[0]-xRef)*( 6378137*PI/180 ))*Math.cos( yRef*PI/180 );
        double y2 = (current[1]-yRef)*( Math.toRadians( 6378137 ) );

        // calculate crossproduct
        total += x1*y2 - x2*y1;
        previous=current;
    }

    return 0.5 * Math.abs(total);
}

Answer 4

Вы хотите посмотреть на кривую заполнения пространства, например, на z-кривую или гильбертову кривую.Кривая SFC разделяет поверхность на множество плиток и сводит двумерную задачу к одномерной.Вы хотите найти блог Ника о пространственном индексе Гильберта и квадродереве.