CODEWITHSUNDEEP
javaalgorithmlistconvex-hull
Lycon
Lycon

Reputation: 2499

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

Im trying to compute the interior points of a convex hull using four nested four loops. However, this gives me the right coordinates but these are duplicated so many times. Im not sure what I'm doing wrong.

Below is my method

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

The method pointIsInside returns true if a point L lies inside triangle i,j,k

When i test this using the set of points below:

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

I get 

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

This is meant to be only (200.0, 200.0) and (300.0, 200.0) only but I'm not sure how to solve this problem.

This is the pseudocode from which i implemented this method.

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

Here is my point 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();
}
}

Below is my point is inside 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;
    }

Thanks for your help.

Upvotes: 2

Views: 451

Answers (1)

Anderson Vieira
Anderson Vieira

Reputation: 9059

In your example, the point (200, 200) is inside of three triangles, defined by the points:

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

Note that any permutation of the points of the above triangles would represent the same triangle. This means (200, 200) will be added to your list every time L == 3 and the values of i, j, and k are some permutation of:

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

The number of permutations for n elements is given by n!, so we would have 6 + 6 + 6 = 18 cases where (200, 200) would be inserted in the InsidePoints list. If you count it, you will see that 18 is the exact number of times that (200, 200) appears in your output. The same rationale applies to (300, 200).

If you need each point to appear only once in the result, you can achieve this easily by making InsidePoints a Set instead of a List:

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

Of course you would also need to implement equals() and hashCode() for the Point class. You'd still be doing a lot of useless calculations though.

To make the code more efficient, in addition to turning InsidePoints into a Set, you could check if a point is inside each triangle only once. This means that j and k should start at a value one greater than the previous index, like this:

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

To check that this works, you can simply print the values of i, j, and k for each iteration and verify that no line is a permutation of another.

Upvotes: 2

Related Questions