Нахождение внутренних точек выпуклой оболочки без предварительного вычисления корпуса

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 возвращает true, если точка 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

Вот моя точка класс

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

Конечно, вам также необходимо реализовать equals() а также hashCode() для Point учебный класс. Вы все еще будете делать много бесполезных вычислений.

Чтобы сделать код более эффективным, помимо поворота InsidePoints в Set Вы можете проверить, находится ли точка внутри каждого треугольника только один раз. Это означает, что j а также k должно начинаться со значения, которое больше предыдущего индекса, например:

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 для каждой итерации и убедитесь, что ни одна строка не является перестановкой другой.