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

im trying compute interior points of convex hull using 4 nested 4 loops. however, gives me right coordinates these duplicated many times. im not sure i'm doing wrong.

below method

public final list<point> interiorpoints(list<point> testpoints){         int n = points.size();          for(int = 0; < n; i++){             for(int j = 0; j < n; j++){                 if(j != i){                     for(int k = 0; k < n; k++){                         if(k != j && j != && != k){                             for(int l = 0; l < n; l++){                                 if(l != k && k != j && j != && != k && l != && 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 point l lies inside triangle i,j,k

when test using 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

(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 meant (200.0, 200.0) , (300.0, 200.0) i'm not sure how solve problem.

this pseudocode implemented method.

algorithm: interior points each       each j =            each k = j =        each l = k = j =          if pl in triangle(pi, pj, pk)             pl non extreme 

here 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 point 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 , area_pqt         sum = area_tqr + area_ptr + area_pqt;          if (area_pqr == sum) {             system.out.println("point t lies inside triangle");             return true;         }          system.out.println("point t not lie inside triangle");         return false;     } 

thanks help.

in example, point (200, 200) inside of 3 triangles, defined points:

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

note permutation of points of above triangles represent same triangle. means (200, 200) added list every time l == 3 , values of i, j, , k permutation of:

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

the number of permutations n elements given n!, have 6 + 6 + 6 = 18 cases (200, 200) inserted in insidepoints list. if count it, see 18 exact number of times (200, 200) appears in output. same rationale applies (300, 200).

if need each point appear once in result, can achieve making insidepoints set instead of list:

set<point> insidepoints = new hashset<>(); 

of course need implement equals() , hashcode() point class. you'd still doing lot of useless calculations though.

to make code more efficient, in addition turning insidepoints set, check if point inside each triangle once. means j , k should start @ value 1 greater previous index, this:

for (int = 0; < n; i++) {     (int j = + 1; j < n; j++) {         (int k = j + 1; k < n; k++) {             (int l = 0; l < n; l++) {                 if (l != && 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 works, can print values of i, j, , k each iteration , verify no line permutation of another.