java - 无需先计算凸包即可找到凸包的内点

Question

我尝试使用四个嵌套的四个循环来计算凸包的内点。然而，这给了我正确的坐标，但这些坐标被重复了很多次。我不确定我做错了什么。

下面是我的方法

public final List<Point> interiorPoints(List<Point> TestPoints){
        int n = points.size();

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(j != i){
                    for(int k = 0; k < n; k++){
                        if(k != j && j != i && i != k){
                            for(int L = 0; L < n; L++){
                                if(L != k && k != j && j != i && i != k && L != i && L != j){
                                    if(pointIsInsideTriangle(points.get(i), points.get(j), points.get(k), points.get(L)) == true){
                                        InsidePoints.add(points.get(L));
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return InsidePoints;
    }

如果点 L 位于三角形 i,j,k 内，则 pointIsInside 方法返回 true

当我使用下面的一组点进行测试时:

        TestPoints.add(new Point(300,200));
        TestPoints.add(new Point(600,500));
        TestPoints.add(new Point(100,100));
        TestPoints.add(new Point(200,200));
        TestPoints.add(new Point(100,500));
        TestPoints.add(new Point(600,100));

我明白

(200.0, 200.0)
(200.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(200.0, 200.0)
(200.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(300.0, 200.0)
(200.0, 200.0)
(300.0, 200.0)

这意味着只有 (200.0, 200.0) 和 (300.0, 200.0)，但我不知道如何解决这个问题。

这是我实现此方法的伪代码。

Algorithm: INTERIOR POINTS
for each i do
      for each j = i do
           for each k = j = i do
       for each L = k = j = i do 
        if pL in triangle(pi, pj, pk)
            then pL is non extreme

这是我的积分等级

public class Point 
{
    private final double x, y;

    public Point(double x, double y)
    {
        this.x = x;
        this.y = y;
    }

    public double getX() 
    {
        return x;
    }

    public double getY()
    {
        return y;
    }

    public void setX(double x)
    {
        return this.x;
    }

    public void setY(double y)
    {
        return this.y;
    }

@Override
public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (obj == null) {
        return false;
    }
    if (!(obj instanceof Point)) {
        return false;
    }
    Point other = (Point) obj;
    EqualsBuilder equalsBuilder = new EqualsBuilder();
    equalsBuilder.append(x, other.x);
    equalsBuilder.append(y, other.y);
    return equalsBuilder.isEquals();
}

@Override
public int hashCode() {
    HashCodeBuilder hashCodeBuilder = new HashCodeBuilder();
    hashCodeBuilder.append(x);
    hashCodeBuilder.append(y);
    return hashCodeBuilder.toHashCode();
}
}

以下是我在类里面的观点

public boolean pointIsInsideTriangle(Point P, Point Q, Point r, Point t) {

        final double sum;
        //Area of triangle PQr
        double Area_PQr = AreaOfTriangle(P, Q, r);

        // Area of triangle PQr
        double Area_tQr = AreaOfTriangle(t, Q, r);

        // Area of triangle PQr
        double Area_Ptr = AreaOfTriangle(P, t, r);

        // Area of triangle PQr
        double Area_PQt = AreaOfTriangle(P, Q, t);

        // sum of Area_tQr, Area_Ptr and Area_PQt
        sum = Area_tQr + Area_Ptr + Area_PQt;

        if (Area_PQr == sum) {
            System.out.println("Point t Lies inside the triangle");
            return true;
        }

        System.out.println("Point t does not Lie inside the triangle");
        return false;
    }

感谢您的帮助。

Answer 1

在您的示例中，点 (200, 200) 位于由以下点定义的三个三角形内部:

[(100, 100), (100, 500), (300, 200)]
[(100, 100), (100, 500), (600, 100)]
[(100, 100), (100, 500), (600, 500)]

请注意，上述三角形的点的任何排列都将表示相同的三角形。这意味着每次 L == 3 以及 i、j 的值都会将 (200, 200) 添加到您的列表中 和 k 是以下内容的一些排列:

[2, 4, 0]
[2, 4, 5]
[2, 4, 1]

n 元素的排列数由 n! 给出，因此我们会有 6 + 6 + 6 = 18 种情况，其中(200, 200) 将被插入到 InsidePoints 列表中。如果您数一下，您将看到 18 正是 (200, 200) 在输出中出现的确切次数。同样的原理也适用于 (300, 200)。

如果您需要每个点在结果中仅出现一次，您可以通过将 InsidePoints 设为 Set 而不是 List 轻松实现此目的>:

Set<Point> InsidePoints = new HashSet<>();

当然，您还需要为 Point 类实现 equals() 和 hashCode()。但你仍然会做很多无用的计算。

为了使代码更高效，除了将 InsidePoints 转换为 Set 之外，您还可以仅检查一个点是否在每个三角形内部一次。这意味着 j 和 k 的起始值应比前一个索引大 1，如下所示:

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            for (int L = 0; L < n; L++) {
                if (L != i && L != j && L != k) {
                    if (pointIsInsideTriangle(
                            points.get(i),
                            points.get(j),
                            points.get(k),
                            points.get(L))) {
                        InsidePoints.add(points.get(L));
                    }
                }
            }
        }
    }
}

要检查其是否有效，您只需打印每次迭代的 i、j 和 k 的值，并验证是否没有一行是另一行的排列。