Área de un polígono (Recursivamente usando Python)

Estoy tratando de resolver un ejercicio del libro Explorando Python. Pero, supongo que no entiendo el concepto de la recursión. He escrito algunas funciones recursivamente. Por eso conozco algunos de los aspectos. Pero, no tengo suficiente experiencia. Y he dejado de estudiar progtwigción por un año.

De todos modos, déjame darte la pregunta completa:

Un polígono se puede representar mediante una lista de pares (x, y) donde cada par es una tupla: [(x1, y1), (x2, y2), (x3, y3), … (xn, yn)] . Escribe una función recursiva para calcular el área de un polígono. Esto se puede lograr “cortando” un triángulo, usando el hecho de que un triángulo con esquinas (x1, y1), (x2, y2), (x3, y3) tiene área (x1y1 + x2y2 + x3y2 – y1x2 –y2x3 – y3x1) / 2.

A pesar del hecho de que, la pregunta ya daba la fórmula, usé otra fórmula. Porque, hice algunas investigaciones sobre el área de un polígono. Y si miras aquí la fórmula es diferente.

Y sería mejor describir mi progtwig paso a paso para explicar lo que quiero. OK, tuve que declarar los ámbitos globales, debido a la recursión:

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

Y luego, creé una función recursiva. Como resultado, esta función siempre devuelve cero. Así que mi verdadero problema es este:

 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 

Y mi función principal:

  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() 

Y aquí está mi código completo sin comentarios:

 ''' 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() 

EDITAR uno

Después de leer sus respuestas, he entendido lo que estaba mal con mi código. Así que decidí compartir la última versión de mi progtwig para obtener otras ayudas. Una vez más, tuve que declarar variables globales. ¿Cómo puedo aplicar la función (lop_triangle) desde el remitente?

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

Mi función que divide la tupla y para obtener las coordenadas x e 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 

Mi función calcula el área del polígono (igual que antes)

 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 

Mi función principal …

 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() 

Por favor, ayúdame a mejorar mi código sin dar una solución completa.

Editar dos

Después de conversar con Senderle, entendí dónde está el problema y la solución de Senderle es mejor que la mía, por lo que le sugiero que lo use. De todos modos, me ayudó a corregir mi código. Y tuve que cambiar mi fórmula nuevamente.

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

También agregó que para los polígonos más largos 3 debe ser len (vértices). Gracias a todos por su tiempo.

La esencia de la recursión es la siguiente:

  1. Identificar un caso base simple y resolver para eso.
  2. Considere un proceso que, cuando se repite, reduce un caso más complejo a ese caso base.
  3. Aplique el proceso en # 2 al problema hasta que llegue al caso base.

En tu caso, el primer paso es fácil. El polígono más pequeño es un triángulo. El área de un triángulo es (x1y2 + x2y3 + x3y1 – y1x2 –y2x3 – y3x1) / 2 . (Parece que lo declararon mal en el problema, aunque …)

El segundo paso también es fácil, porque la statement del problema se lo da a usted: dado un polígono n-vértice, corte un triángulo, determine su área y agréguela al área del polígono de vértice (n-1) resultante.

Lo dividiremos en partes. Primero, una función para resolver el # 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 

Fácil. Ahora una función para resolver el # 2. Todo lo que necesitamos es una función que corta un triángulo y lo devuelve tanto al polígono más pequeño resultante:

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

Si no es obvio, esto simplemente crea un triángulo utilizando los dos primeros y últimos puntos del polígono. Luego elimina el último punto del polígono, que ahora es equivalente a cortar el triángulo. (Dibuje un polígono n y etiquete sus vértices de 0 a n para ver cómo funciona). Ahora tenemos un triángulo y un polígono más simple.

Ahora, pongámoslo todo junto. Este tercer paso es, en cierto modo, el más difícil, pero como ya resolvimos los dos primeros problemas, el tercero es más fácil de entender.

 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) 

Toda la magia pasa en esa última línea. Cada vez que area_of_polygon obtiene un triángulo, simplemente devuelve el área de un triángulo. Pero cuando obtiene un polígono más grande, corta un triángulo, toma el área de ese triángulo y lo agrega a … el área de un polígono más pequeño. Así que digamos que el polígono tiene 5 vértices. La primera vez que se llama area_of_polygon (c1), corta un triángulo, toma su área y luego llama nuevamente a area_of_polygon (c2), pero esta vez con un polígono de 4 vértices. Luego, area_of_polygon salta de un triángulo y llama nuevamente a area_of_polygon (c3), pero esta vez con un polígono de 3 vértices. Y luego no tiene que volver a llamar a area_of_polygon . Simplemente devuelve el área de un triángulo a la llamada anterior (c2). Eso sum el resultado con el triángulo en (c2) y devuelve ese valor a (c1). Y luego tienes tu respuesta.

Además, para lo que vale, la fórmula de wolfram se puede escribir con gran claridad en tres líneas:

 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 

La implementación de su fórmula es defectuosa. Mira hacia adelante a los valores en sus listas x, y que aún no se han establecido con (x[i]*y[i+1] - x[i+1]*y[i])

Si coloca una statement de impresión dentro de su bloque try-except, verá que simplemente está multiplicando por cero y obteniendo un área cero:

 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 

Además, no está devolviendo los resultados de su llamada recursiva al área de polígono, por lo que nunca obtendrá esa area/2 . Desea: return areaofpolygon(polygon, i+1) . Y asegúrese de dividir realmente entre 2.0 para que obtenga precisión de flotación, ya que sus puntos son ints.

Intente usar la fórmula que encontró o que se sugirió en otra pregunta.

Actualizar

Aquí hay una versión fija de su código:

 #!/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. 

Tenga en cuenta que no necesita las listas globales de x, y. Y también te perdiste la última parte de la ecuación donde usaste el último punto y el primer punto.

Usa esta fórmula.

http://sofes.miximages.com/area/cbb6a25439b51061adb913c2a6706484.png

Usted cumple su tarea en uno para bucle.