0

我需要用两条垂直线切割一个凸的非简单多边形，将其分成 4 个相等（面积）的部分。

例子

我写了一个程序，但它没有通过测试。

  • 我认为原因是舍入误差或我计算面积的函数。
  • 请检查一下，是否正确？
  • 我使用鞋带算法和苍鹭公式

这是代码：

double calcArea() {
    double result = 0;
    if (size() > 4) {
        int j = size() - 1;
        for (int i = 0; i < size() - 1; i++) {
            result += (points.get(i).getX() + points.get(j).getX())
                    *
                    (points.get(j).getY() - points.get(i).getY());
            j = i;
        }
        result = result / (result >= 0 ? 2. : -2.);
    }  else if(size() == 3) {
        double c,a,b, p;
        c = Math.sqrt(Math.pow(points.get(0).getY()-points.get(1).getY(),2)+Math.pow(points.get(0).getX()-points.get(1).getX(),2));
        a = Math.sqrt(Math.pow(points.get(1).getY()-points.get(2).getY(),2)+Math.pow(points.get(1).getX()-points.get(2).getX(),2));
        b = Math.sqrt(Math.pow(points.get(0).getY()-points.get(2).getY(),2)+Math.pow(points.get(0).getX()-points.get(2).getX(),2));
        p = (a + b + c) / 2.;
        return Math.sqrt(p*(p-a)*(p-b)*(p-c));

    }


    return result;
}

我在做什么：

  • 寻找point(x, y)切割多边形。
  • 我把它剪了x = a in [ min(x), max(x)]
  • 并计算S'（从 x=min(x) 到 x=a 的多边形的一部分）
  • 如果S' = S/2，我拿来a计算价值(a, *)
  • 然后与y = bwhere相同b in [min(y), max(y)]
  • 有没有更快的方法？
4

0 回答 0