将迭代方法更改为递归以计算多边形面积

Question

我在 Java 中编写了一些代码来计算多边形的面积。在我的代码中，我使用迭代 "for" 来获取 ArrayList 中 X 和 Y 的坐标值的输入。我的代码计算运行成功，我确实得到了正确的输出。

我的问题是我想更改我的代码以使用递归，以便可以递归调用 computeArea(ArrayList c, int size) 并且我不想在此方法中使用迭代 "for" .

如果有人能告诉我如何将此方法从迭代更改为递归，我将不胜感激。

谢谢。

下面是我的 Polygon.java

代码

import java.awt.geom.Point2D;
import java.util.ArrayList;

public class Polygon
{
private ArrayList<Point2D.Double> corners;
private double area;
private double adding;
private double minus;
private double exAdding;
private double exMinus;

public Polygon()
{
    corners = new ArrayList<Point2D.Double>();
    area = 0;
    adding = 0;
    minus = 0;
    exAdding = 0;
    exMinus = 0;
}

//add point to the array
public void add (Point2D.Double p)
{
    corners.add(p);
}

//computes area of polygon
public double getArea()
{
    return computeArea(corners, corners.size());
}

public double computeArea(ArrayList<Point2D.Double> c, int size)
{
    if (size < 0)
    {
        return 0;
    }

    else
    {
        for (int i = 0; i < size-1; i++)
        {
            double xA = c.get(i).getX();
            double yA = c.get(i).getY();
            double xB = c.get(i+1).getX();
            double yB = c.get(i+1).getY();

            exAdding = c.get(size-1).getX()*c.get(size-size).getY();
            adding = adding + xA*yB; 

            exMinus = c.get(size-1).getY()*c.get(size-size).getX();
            minus = minus + yA*xB;

            //System.out.println("test adding : " + adding);
        }
        //System.out.println("extra adding : " + exAdding);
        area = Math.abs((adding+exAdding) - (minus+exMinus));

        return area/2;
    }
}

}

这是我的 PolygonTester.java

代码

import java.awt.geom.Point2D;

public class PolygonTester
{
public static void main (String[] args)
{
    //create square
    Polygon p = new Polygon();
    p.add(new Point2D.Double(10, 20));
    p.add(new Point2D.Double(20, 20));
    p.add(new Point2D.Double(20, 10));
    p.add(new Point2D.Double(10, 10));

    System.out.println("Area : " + p.getArea());
    System.out.println("Expected : 100");


    //create square
    Polygon p1 = new Polygon();
    p1.add(new Point2D.Double(3, 4));
    p1.add(new Point2D.Double(5, 11));
    p1.add(new Point2D.Double(12, 8));
    p1.add(new Point2D.Double(9, 5));
    p1.add(new Point2D.Double(5, 6));

    System.out.println("Area : " + p1.getArea());
    System.out.println("Expected : 30");

    //regular hexagon with radius 1
    p = new Polygon();

    for (int i = 0; i < 6; i++)
    {
        p.add(new Point2D.Double(Math.sin(i*Math.PI/3), Math.cos(i*Math.PI/3)));
    }

    System.out.println("Area : " + p.getArea());
    System.out.println("Expected : " + 3*Math.sqrt(3)/2);
}

}

Answer 1

将此方法添加到您的程序中

    public void recursionMethod(ArrayList<Point2D.Double> c, int size, int count){
      if(count<size-1){
        double xA = c.get(count).getX();
        double yA = c.get(count).getY();
        double xB = c.get(count+1).getX();
        double yB = c.get(count+1).getY();

        exAdding = c.get(size-1).getX()*c.get(size-size).getY();
        adding = adding + xA*yB; 

        exMinus = c.get(size-1).getY()*c.get(size-size).getX();
        minus = minus + yA*xB;
        recursionMethod(c, size, count+1);
       }
    }

并调用此方法而不是 for 循环

recursionMethod(c, size, 0);

Answer 2

我怀疑您可能遗漏了递归点。虽然大多数迭代方法确实可以用递归代替，反之亦然，但在许多情况下，一种或另一种技术自然适合您的问题。在您的情况下，这自然是一个迭代问题：多边形由其顶点定义，计算面积涉及连续访问每个顶点。

如果您想练习递归，我建议您选择一个更自然的递归问题。一般来说递归的形式是：

result recursiveproblem(context)
    if context is simple enough to have obvious answer
        return obvious answer
    else
        break context into smaller pieces
        call recursive problem on each of the smaller pieces
        combine the answers

因此这适合存在具有明显答案的自然简单状态以及分解和组合答案的方法的情况。

典型的例子是阶乘。根据定义 factorial(0) = 1 和 factorial(n) = n * factorial(n - 1)

这看起来已经很自然地递归了，而计算面积却没有。

Answer 3

我刚刚一直在研究使用递归来计算质心。我为 Centroids of Polygons 的维基百科页面中列出的方程编写了以下递归解。您将看到您需要使用列表中的前两个 2D 点来计算面积等，然后添加到应用于 2D 点列表其余部分的相同函数。在我看来，这似乎符合 "sprinter" 设定的标准（但也许我遗漏了一些东西）。

以下 F# 代码生成一个包含多边形面积和两个质心的元组：

let AddTuple3 (a, b, c) (d, e, f) = (a+d,b+e,c+f)
let Comb3 (X1, Y1) (X2, Y2) = 
   let A = (X1 * Y2 - X2 * Y1) / 2.0
   (A, (X1 + X2) * A / 3.0, (Y1 + Y2) * A / 3.0)

let SecProp2D PtLst = 
   let rec RecSecProp2D PtLst = 
      match PtLst with 
      | [A] -> (0.0, 0.0, 0.0)
      | B::C -> AddTuple3 (Comb3 B C.Head) (RecSecProp2D C)
      | _ -> (0.0, 0.0, 0.0)
   let (A, B, C) = RecSecProp2D PtLst
   (A, B/A, C/A)

// Testing...
let PtLst1 = [(0.0,0.0);(2.0,0.0);(2.0,5.0);(0.0,5.0);(0.0,0.0)] // 2x5 rectangle
printfn "Recursive Area, Cx & Cy are %A" (SecProp2D PtLst1)

您可以在 dotnetFiddle 上玩它。

将迭代方法更改为递归以计算多边形面积

Change iteration method to recursion to calculate Polygon area

java

recursion

polygon

arraylist