Я создал функцию, которая вычисляет полигон области со способом 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
Здесь версия, которая использует 1/2 как много умножений: fooobar.com/questions/34901/...
Если вам нужна еще большая производительность, вы можете подумать об этом в расширении Python C. C может быть значительно быстрее, чем Python, особенно для математических операций - иногда 100-1000x.
Попробуйте самый простой способ, формула сырого шнурка для треangularьников и многоangularьников:
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))
Еще один интересный подход (хотя и медленнее)
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())