在不先计算外壳的情况下找到凸包的内部点

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;
    }

方法 pointIsInside returns 如果点 L 位于三角形 i,j,k 内部则为真

当我使用以下一组点对此进行测试时：

        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

这是我的观点class

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

下面是我的观点在里面class

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 时都会将 (200, 200) 添加到您的列表中，并且 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 class 实现 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 的值，并验证没有一行是另一行的排列。

在不先计算外壳的情况下找到凸包的内部点

Finding the interior points of a convex hull without computing the hull first

java

algorithm

list

convex-hull