Самый быстрый способ получить формулу Шнурка

Question

Я сделал функцию, которая вычисляет площадь полигона с помощью Shoelace.

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

Моя функция:

def shoelace_formula(polygonBoundary, absoluteValue = True):
    nbCoordinates = len(polygonBoundary)
    nbSegment = nbCoordinates - 1

    l = [(polygonBoundary[i+1][0] - polygonBoundary[i][0]) * (polygonBoundary[i+1][1] + polygonBoundary[i][1]) for i in xrange(nbSegment)]

    if absoluteValue:
        return abs(sum(l) / 2.)
    else:
        return sum(l) / 2.

Мой полигон:

polygonBoundary = ((5, 0), (6, 4), (4, 5), (1, 5), (1, 0))

Результат:

22.

Есть идеи?

Я пытаюсь с Numpy: это быстрее, но вы должны сначала преобразовать свои координаты.

import numpy as np
x, y = zip(*polygonBoundary)

def shoelace_formula_3(x, y, absoluteValue = True):

    result = 0.5 * np.array(np.dot(x, np.roll(y, 1)) - np.dot(y, np.roll(x, 1)))
    if absoluteValue:
        return abs(result)
    else:
        return result

Answer 1

Для меня самым быстрым способом было бы использовать numpy, где вам нужно отправить массив numpy из (x,y) cordinates в качестве аргумента в методе шнурков:

import numpy as np
def shoelace(x_y):
    x_y = np.array(x_y)
    x_y = x_y.reshape(-1,2)

    x = x_y[:,0]
    y = x_y[:,1]

    S1 = np.sum(x*np.roll(y,-1))
    S2 = np.sum(y*np.roll(x,-1))

    area = .5*np.absolute(S1 - S2)

    return area

Answer 2

Взгляните на пример Rosetta Code с использованием Numpy. Numpy дает быстрое решение.

Для вашего удобства я вставляю ниже фрагмент кода Rosetta Code:

      import numpy as np
# x,y are arrays containing coordinates of the polygon vertices
x=np.array([3,5,12,9,5]) 
y=np.array([4,11,8,5,6]) 
i=np.arange(len(x))
#Area=np.sum(x[i-1]*y[i]-x[i]*y[i-1])*0.5 # signed area, positive if the vertex sequence is counterclockwise
Area=np.abs(np.sum(x[i-1]*y[i]-x[i]*y[i-1])*0.5) # one line of code for the shoelace formula

Answer 3

Это очень простая реализация формулы шнурков на питоне.

      class Polygon:
  def __init__(self,arr):
    self.arr = arr
  def area(self):
    total=0
    i = 0
    while i != len(self.arr)-1:
      total+=self.arr[i][0]*self.arr[i+1][1]
      total-=self.arr[i+1][0]*self.arr[i][1]
      i+=1
    return abs(total +self.arr[-1][0]*self.arr[0][1] -self.arr[-1][-1]*self.arr[0][0])/2

Answer 4

Вот версия, которая использует половину умножения: /questions/23683196/kak-rasschitat-ploschad-2-go-mnogougolnika/23683202#23683202

Если вам нужна еще более высокая производительность, вы можете рассмотреть возможность сделать это в расширении Python C. C может быть значительно быстрее, чем Python, особенно для математических операций - иногда 100-1000x.

Answer 5

Еще один интересный подход (хотя и более медленный)

m = np.vstack([x,y])
result = 0.5 * np.abs(np.linalg.det(as_strided(m, (m.shape[1]-1, 2, 2), (m.itemsize, m.itemsize*m.shape[1], m.itemsize))).sum())

Answer 6

Попробуйте самый простой способ, формула сырого шнурка для треугольников и многоугольников:

def shoelace_formula(x1, y1, x2, y2, x3, y3, x4, y4, x5, y5):
      return abs(0.5 * (x1*y2 + x2*y3 + x3*y4 + x4*y5 + x5*y1
                        - x2*y1 - x3*y2 - x4*y3 - x5*y4 - y1*y5))

print(shoelace_formula(5, 0, 6, 4, 4, 5, 1, 5, 1, 0))

Answer 7

class Point //a new class for an any point a(X,Y), b(X,Y), c(X,Y), d(X,Y)
{
    //private int x, y;
    public int X { get; set; }
    public int Y { get; set; }

}

static class Geometry
{       

    public static void GerArea(Point a, Point b, Point c)
    {

        double area = 0.5 * ( (a.X * b.Y) + (b.X * c.Y) + (c.X * a.Y) - (b.X * a.Y) - (c.X * b.Y) - (a.X * c.Y) );

        Console.WriteLine(Math.Abs(area));
    }
    public static void GerArea(Point a, Point b, Point c, Point d)
    {
        double area = 0.5 * ((a.X * b.Y) + (b.X * c.Y) + (c.X * d.Y) + (d.X * a.Y) - (b.X * a.Y) - (c.X * b.Y) - (d.X * c.Y) - (a.X * d.Y ) );

        Console.WriteLine(Math.Abs(area));
    }
}
class Program
{
    static void Main(string[] args)
    {

        Point a = new Point() { X = -12, Y = 12 }; 
        Point b = new Point() { X = 15, Y = 15 };
        Point c = new Point() { X = -15, Y = -16 };
        Point d = new Point() { X = 16, Y = -15 };

        Console.WriteLine("****Shoelace formula****\n");


        Console.Write("Area of tringle: ");
        Geometry.GerArea(a, b, c);
        Console.Write("Area of quad: ");
        Geometry.GerArea(a, b, c, d);


        Console.ReadLine();

    }
}