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

请注意，上述三角形的点的任何排列都将代表同一个三角形。这意味着 (200, 200) 将在每次 L == 3 和 i、j 的值时添加到您的列表中 和 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 的值，并验证没有行是另一个的排列。