我的代码使用格雷厄姆算法找到凸包效果很好（它向我展示了它应该显示的多边形）但我可以看到它向我发送了一个额外的共线点（尽管我正在处理我的代码中的共线点) 这是我的代码：
public Collection<Coord> territoire()
{
double checkPoints;
Collection<Coord> sommets = new ArrayList<Coord>(this);
Stack<Coord> stackOfConvexHull = new Stack<Coord>();
ArrayList<Coord> thisToArrList = new ArrayList<Coord>();
for(Coord c : this)
thisToArrList.add(c);
//sorting the array by Y
ArrayList<Coord> sortedPointsByY = sortedArrayByY(thisToArrList);
//sorting the set of points with increasing order of angle
// they and the base point (basePoint) make with X axis
List<Coord> sortedPointsByAngle = new ArrayList<Coord>(sortPointsByAngle(sortedPointsByY));
if(sortedPointsByAngle.size() < 3)
System.out.println("the convex hull of less than 3 points is not possible");
if(collinear(sortedPointsByAngle))
System.out.println("can't make a convex hull of collinear points");
stackOfConvexHull.push(sortedPointsByAngle.get(0));
stackOfConvexHull.push(sortedPointsByAngle.get(1));
for (int i = 2; i < sortedPointsByAngle.size(); i++)
{
Coord p1 = sortedPointsByAngle.get(i);
Coord p2 = stackOfConvexHull.pop();
Coord p3 = stackOfConvexHull.peek();
checkPoints = ccw(p3, p2, p1);
// counter-clockwise
if(checkPoints > 0)
{
stackOfConvexHull.push(p2);
stackOfConvexHull.push(p1);
}
// collinear
if(checkPoints == 0)
stackOfConvexHull.push(p1);
// clockwise
else
i--;
}
// end of the hull
stackOfConvexHull.push(sortedPointsByAngle.get(0));
sommets = new ArrayList<Coord>(stackOfConvexHull);
return sommets;
}
//**********************************Auxiliary méthods****************************************************
//***** sorting points by Y and angles *****
//sorting the points by their y in ascending order
public ArrayList<Coord> sortedArrayByY(ArrayList<Coord> arrayOfPoints)
{
Coord temp = null;
for(int i = 0; i< arrayOfPoints.size(); i++)
{
for(int j = 0; j< arrayOfPoints.size()-1; j++)
{
if(arrayOfPoints.get(j+1).y < arrayOfPoints.get(j).y)
{
temp = arrayOfPoints.get(j+1);
arrayOfPoints.set(j+1, arrayOfPoints.get(j));
arrayOfPoints.set(j, temp);
}
}
}
return arrayOfPoints;
}
public Set<Coord> sortPointsByAngle(ArrayList<Coord> points)
{
int min = minYIndex(points);
final Coord basePoint = points.get(min);
TreeSet<Coord> set = new TreeSet<Coord>(new Comparator<Coord>()
{
public int compare(Coord a, Coord b) {
if(a == b || a.equals(b))
return 0;
double firstAngle = angle(basePoint, a);
double secondAngle = angle(basePoint, b);
if(firstAngle < secondAngle)
return -1;
else if(firstAngle > secondAngle)
return 1;
else
{
// collinear with the 'basePoint' point, let the point closest to it come first
double firstDistance = findDistance(basePoint, a);
double secondDistance = findDistance(basePoint, b);
if(firstDistance < secondDistance)
return -1;
else
return 1;
}
}
});
set.addAll(points);
return set;
}
// find the buttom most point (minimum Y)
// if If the lowest y-coordinate exists in
// more than one point in the set, the point with the one with the lowest x-coordinate
// will be chosen
public int minYIndex(ArrayList<Coord> sortedPointsByY)
{
int min = 0;
for ( int i = 1; i < sortedPointsByY.size(); i++ ) // O(n) => n number of points
{
if ( sortedPointsByY.get(i).y == sortedPointsByY.get(min).y)
{
if ( sortedPointsByY.get(i).x < sortedPointsByY.get(min).x)
min = i;
}
else if ( sortedPointsByY.get(i).y < sortedPointsByY.get(min).y)
min = i;
}
return min;
}
public double angle(Coord basePoint, Coord a)
{
return Math.atan2(a.y - basePoint.y, a.x - basePoint.x);
}
public double findDistance(Coord basePoint, Coord a)
{
return Math.sqrt(((basePoint.x - a.x) * (basePoint.x - a.x)) +
((basePoint.y - a.y) * (basePoint.y - a.y)));
}
//if the result is zero, the point is collinear
//if it is positive, the three points constitute left turn (counter clockwise)
//else the three points constitute right turn (clockwise)
public double ccw(Coord p1, Coord p2, Coord p3)
{
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
// check if the points are collinear
public boolean collinear(List<Coord> sortedPointsByAngle)
{
Coord a, b, c;
if(sortedPointsByAngle.size() < 2)
return true;
a = sortedPointsByAngle.get(0);
b = sortedPointsByAngle.get(1);
for(int i = 2; i < sortedPointsByAngle.size(); i++)
{
c = sortedPointsByAngle.get(i);
if(ccw(a, b, c) != 0)
return false;
}
return true;
}
我非常等待有一些提示来帮助我找到我的问题