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

Я сделал функцию, которая вычисляет площадь многоугольника с помощью 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

python performance area polygon
person Guilhain    schedule 10.12.2016    source источник
comment
Использование numpy должно помочь. stackoverflow.com/a/30408825/5666087   -  person jakub    schedule 10.12.2016
comment
@Якуб. Я пытаюсь с numpy, с той же производительностью.   -  person Guilhain    schedule 10.12.2016
comment
Попробуйте со многими координатами. Когда я пробовал обе ваши функции с 500 парами координат, shoelace_formula_3 работал в два раза быстрее (115 микросекунд), чем shoelace_formula (321 микросекунда).   -  person jakub    schedule 10.12.2016
comment
И если вы выполняете x, y = zip(*polygonBoundary) вне функции и включаете x и y в качестве параметров функции, она выполняется за 93,7 микросекунды. И импортируйте numpy вне функции.   -  person jakub    schedule 10.12.2016
comment
Быстрее: 0.5 * np.abs(np.dot(x[:-1], y[1:]) + x[-1]*y[0] - np.dot(y[:-1], x[1:]) - y[-1]*x[0])   -  person Ariel    schedule 08.08.2019
comment
MikeD в блоге Джона Кука предположил, что координаты должны быть переведены относительно одной из точек многоугольника, чтобы свести к минимуму потерю точности, когда абсолютные значения координат намного больше, чем вычисляемая площадь.   -  person syockit    schedule 26.01.2021

Ответы (5)


arrow_upward
2
arrow_downward

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

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
person Mustaqim Khan    schedule 23.10.2019
comment
Добро пожаловать в СО! Когда вы отвечаете на вопрос, и есть некоторые другие ответы, укажите минусы и плюсы вашего ответа по сравнению с остальными. - person David García Bodego; 23.10.2019

arrow_upward
0
arrow_downward

Вот версия, в которой используется 1/2 умножения: https://stackoverflow.com/a/717367/763269

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

person Chris Johnson    schedule 12.12.2016
comment
Большое спасибо. Это лучше, но решение numpy самое быстрое! - person Guilhain; 14.12.2016

arrow_upward
0
arrow_downward

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

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))
person 2RMalinowski    schedule 16.11.2018

arrow_upward
0
arrow_downward

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

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())
person Ariel    schedule 08.08.2019

arrow_upward
0
arrow_downward

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

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
person harshit bhalla    schedule 04.02.2021