Область многоугольника (рекурсивно использующая Python)

Я пытаюсь решить упражнение из изучения книги Python. Но, я думаю, я не понимаю концепции рекурсии. Я написал функцию Рекурсивно. Поэтому я знаю некоторые аспекты. Но у меня недостаточно опыта. И я перестал учиться программированию около года.

В любом случае, позвольте мне задать вам полный вопрос:

Многоугольник может быть представлен списком (x, y) пар, где каждая пара является кортежем: [(x1, y1), (x2, y2), (x3, y3), … (xn, yn)] , Напишите рекурсивную функцию для вычисления области многоугольника. Это может быть достигнуто путем «отсечения» треугольника, используя тот факт, что треугольник с углами (x1, y1), (x2, y2), (x3, y3) имеет площадь (x1y1 + x2y2 + x3y2 – y1x2 -y2x3 – y3x1) / 2.

Несмотря на то, что вопрос уже дал формулу, я использовал другую формулу. Потому что я сделал несколько исследований о области многоугольника. И если вы посмотрите здесь, то формула будет иной.

И описать мою программу шаг за шагом было бы лучше, чтобы объяснить, что я хочу. Хорошо, мне пришлось объявить глобальные области, из-за рекурсии:

area = 0 x = [0] * 3 y = [0] * 3 

И затем я создал рекурсивно функцию. В результате эта функция всегда возвращается в нуль. Поэтому моя настоящая проблема заключается в следующем:

 def areaofpolygon(polygon, i): global area, x, y # My variables try: # I prefered using try statement from using if-else statements. So it is the easier I guess. x[i], y[i] = polygon[i] # X and Y coordinates from tuple area += (x[i]*y[i+1] - x[i+1]*y[i]) #My formula except IndexError: return area/2 areaofpolygon(polygon, i+1) # Here, this is my weird recursion 

И моя главная функция:

  def main(): mypolygon = [(1,2), (2,5), (1,4)] # I declared polygon as tuples # I called my function and started to count from zero, and the result will be prompted. print(areaofpolygon(mypolygon,0)) return 0 if __name__ == '__main__': main() 

И вот мой полный код без комментариев:

 ''' Created on Feb 24, 2012 @author: msarialp ''' area = 0 x = [0] * 3 y = [0] * 3 def areaofpolygon(polygon, i): global area, x, y try: x[i], y[i] = polygon[i] area += (x[i]*y[i+1] - x[i+1]*y[i]) except IndexError: return area/2 areaofpolygon(polygon, i+1) def main(): mypolygon = [(1,2), (2,5), (1,4)] print(areaofpolygon(mypolygon,0)) return 0 if __name__ == '__main__': main() 

ИЗМЕНИТЬ

Прочитав ваши ответы, я понял, что не так с моим кодом. Поэтому я решил поделиться последней версией своей программы, чтобы получить некоторые другие советы. Опять же, мне пришлось объявлять глобальные переменные. Как я могу применить функцию (lop_triangle) из senderle

 area = 0 x = [0] * 3 y = [0] * 3 

Моя функция, которая делит кортеж и получает координаты x и y.

 def sides_of_polygon(polygon, i): global x, y try: x[i], y[i] = polygon[i] return sides_of_polygon(polygon, i+1) except IndexError: return x, y 

Моя функция вычисляет область многоугольника (такая же, как и раньше)

 def area_of_polygon(x, y, i): global area try: area += x[i]*y[i+1] - x[i+1]*y[i] return area_of_polygon(x, y, i+1) except IndexError: return area/2.0 

Моя основная функция …

 def main(): mypolygon = [(1,2), (2,5), (1,4)] dx, dy = sides_of_polygon(mypolygon, 0) print(area_of_polygon(dx,dy,0)) return 0 if __name__ == '__main__': main() 

Пожалуйста, помогите мне улучшить мой код, не давая полного решения.

EDIT Two

После обсуждения с senderle я понял, где проблема, и решение senderle лучше, чем мое, поэтому я предлагаю вам использовать его. Во всяком случае, Он помог мне сделать правильный код. И мне пришлось снова изменить формулу.

 area += x[i]*y[(i+1) % 3] - x[(i+1) % 3]*y[i] 

Он также добавил для более длинных полигонов 3 должен быть len (вершины). Спасибо всем за их время.

3 Solutions collect form web for “Область многоугольника (рекурсивно использующая Python)”

Суть рекурсии заключается в следующем:

  1. Определите простой базовый регистр и решите для этого.
  2. Задумайте процесс, который, когда повторяется, уменьшает более сложный случай в этом базовом случае.
  3. Примените процесс в №2 к проблеме, пока не дойдете до базового варианта.

В вашем случае первый шаг очень прост. Самый маленький полигон – это треугольник. Площадь треугольника равна (x1y2 + x2y3 + x3y1 – y1x2 –y2x3 – y3x1) / 2 . (Похоже, они ошиблись в проблеме, хотя …)

Второй шаг также прост, потому что оператор задачи дает вам это: заданный n-вершинный многоугольник, вычеркните треугольник, определите его площадь и добавьте его в область полученного (n-1) -вершинного многоугольника.

Мы разложим его на части. Во-первых, функция для решения # 1:

 def area_of_triangle(points): (x1, y1), (x2, y2), (x3, y3) = points return abs(x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1) / 2 

Легко. Теперь функция для решения # 2. Все, что нам нужно, это функция, которая перекрывает треугольник и возвращает как его, так и полученный меньший многоугольник:

 def lop_triangle(points): triangle = [points[0], points[-1], points[-2]] polygon = points[:-1] return triangle, polygon 

Если это не очевидно, это просто создает треугольник, используя первую и две последние точки многоугольника. Затем он удаляет последнюю точку многоугольника, которая теперь эквивалентна измельчению треугольника. (Нарисуйте n-многоугольник и назовите его вершины от 0 до n, чтобы увидеть, как он работает.) Итак, теперь у нас есть треугольник и более простой полигон.

Теперь давайте все вместе. Этот третий шаг в какой-то мере является самым сложным, но поскольку мы решили первые две проблемы, третий легче понять.

 def area_of_polygon(points): if len(points) == 3: return area_of_triangle(points) else: triangle, polygon = lop_triangle(points) return area_of_triangle(triangle) + area_of_polygon(polygon) 

Вся магия происходит в этой последней строке. Каждый раз, когда area_of_polygon получает треугольник, он просто возвращает область треугольника. Но когда он получает более крупный многоугольник, он перекрывает треугольник, занимает область этого треугольника и добавляет его в область меньшего полигона. Так говорят, что многоугольник имеет 5 вершин. Первый раз area_of_polygon вызывается (c1), он отбрасывает треугольник, берет его область и снова вызывает area_of_polygon (c2), но на этот раз с 4-вершинным многоугольником. Затем area_of_polygon lops треугольника и area_of_polygon (c3), но на этот раз с 3-вершинным многоугольником. И тогда ему не нужно area_of_polygon . Он просто возвращает область треугольника к предыдущему вызову (c2). Это суммирует результат с треугольником в (c2) и возвращает это значение в (c1). И тогда у вас есть свой ответ.

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

 def area_of_polygon(vertices): pairs = zip(vertices, vertices[1:] + vertices[0:1]) return sum(x1 * y2 - y1 * x2 for (x1, y1), (x2, y2) in pairs) / 2 

Внедрение вашей формулы является ошибочным. Он смотрит вперед на значения в ваших списках x, y, которые еще не были установлены (x[i]*y[i+1] - x[i+1]*y[i])

Если вы разместите оператор печати внутри своего блока try-except, вы увидите, что вы просто умножаетесь на нуль и получаете нулевую область:

 try: x[i], y[i] = polygon[i] area += (x[i]*y[i+1] - x[i+1]*y[i]) print x[i], y[i+1], x[i+1], y[i] except IndexError, e: return area/2 #1 0 0 2 #2 0 0 5 

Кроме того, вы не возвращаете результаты своего рекурсивного вызова в areaofpolygon, так что вы никогда не получите эту area/2 . Вы хотите: return areaofpolygon(polygon, i+1) . И убедитесь, что вы фактически разделите на 2.0, чтобы получить точность с плавающей точкой, так как ваши точки являются ints.

Попробуйте использовать формулу, найденную вами или предложенную в другом вопросе.

Обновить

Вот фиксированная версия вашего кода:

 #!/usr/bin/env python from random import randint from shapely.geometry import Polygon area = 0 def areaofpolygon(polygon, i): global area if i == 0: area = 0 try: x1, y1 = polygon[i] x2, y2 = polygon[i+1] area += (x1*y2) - (x2*y1) except IndexError, e: x1, y1 = polygon[0] x2, y2 = polygon[-1] area += (x2*y1) - (x1*y2) return abs(area/2.0) return areaofpolygon(polygon, i+1) def main(): mypolygon = [(randint(0, 100), randint(0, 100)) for _ in xrange(10)] print mypolygon area = areaofpolygon(mypolygon, 0) assert area == Polygon(mypolygon).area print "Test passed." return 0 if __name__ == '__main__': main() ### Output ### $ ./test.py [(29, 76), (85, 49), (27, 80), (94, 98), (19, 1), (75, 6), (55, 38), (74, 62), (0, 25), (93, 94)] Test passed. $ ./test.py [(13, 37), (98, 74), (42, 58), (32, 64), (95, 97), (34, 62), (34, 59), (21, 76), (55, 32), (76, 31)] Test passed. $ ./test.py [(38, 67), (66, 59), (16, 71), (53, 100), (64, 52), (69, 31), (45, 23), (52, 37), (27, 21), (42, 74)] Test passed. 

Обратите внимание, что вам не нужны глобальные списки x, y. И вы также пропустили последнюю часть уравнения, в которой вы используете последнюю точку и первую точку.

Используйте эту формулу.

https://upload.wikimedia.org/wikipedia/en/math/c/b/b/cbb6a25439b51061adb913c2a6706484.png

Вы выполняете свою задачу в одном цикле.

  • Процесс завершен кодом выхода -1073741571
  • Как вернуть последний индекс списка Python
  • Почему оптимизация хвостовой рекурсии быстрее, чем обычная рекурсия в Python?
  • Почему Python имеет максимальную глубину рекурсии?
  • Медленная рекурсия в python
  • Рекурсивные генераторы в Python
  • Как найти общие элементы в списке списков?
  • Подсчитайте все элементы в списке произвольного вложенного списка без рекурсии
  •  
    Interesting Posts for Van-Lav
    Python - лучший язык программирования в мире.