我编写了一个Java程序，该程序使用分而治之算法在笛卡尔坐标系中查找多边形的凸包。
我有一个Coord类，它具有两个“双”字段X和y，而我正在使用该方法的“this”是一组坐标(集合)。
我的方法应该返回多边形的外壳(集合)
我的代码是这样的:
public Collection<Coord> territoire()
{
Collection<Coord> sommets = new ArrayList<Coord>();
ArrayList<Coord> thisToArrList = new ArrayList<Coord>();
for(Coord c : this)
thisToArrList.add(c);
ArrayList<Coord> sortedPointsByX = new ArrayList<Coord>();
int n = this.size();
if (n <= 2)
return this;
//sorting the points by their X coordinates
sortedPointsByX = sortedArrayByX(thisToArrList);
//>>>>>>>>>>>>>>>>>> works good till here <<<<<<<<<<<<<<<<<<<<<<<<
// now sortedPointsByX array contains the points with increasing X
// splitting the sortedPointsByX into two arrays
ArrayList<Coord> firstPart = new ArrayList<Coord>();
ArrayList<Coord> secondPart = new ArrayList<Coord>();
// if the number of the points is prime, the leftmost and the rightmost half
// both have same number of points
if(sortedPointsByX.size() % 2 == 0)
{
for(int i = 0; i < sortedPointsByX.size()/2; i++)
{
firstPart.add(sortedPointsByX.get(i));
}
for(int i = sortedPointsByX.size()/2; i < sortedPointsByX.size(); i++)
{
secondPart.add(sortedPointsByX.get(i));
}
}
//>>>>>>>>>>>>>>>>>>>>>works good till here<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
// if the number of points is odd, the leftmost half have the extra points
else
{
for(int i = 0; i < sortedPointsByX.size()/2+1; i++)
{
firstPart.add(sortedPointsByX.get(i));
}
for(int i = sortedPointsByX.size()/2+1; i < sortedPointsByX.size(); i++)
{
secondPart.add(sortedPointsByX.get(i));
}
}
//>>>>>>>>>>>>>>>>>>>>>>>works good till here<<<<<<<<<<<<<<<<<<<<<<<<<
CoordSet firstSet = new CoordSet(firstPart);
CoordSet secondSet = new CoordSet(secondPart);
// converting the arrays to list of coordinates in order to use recursion over them
//recursion for sub coordsets
Collection<Coord> firstSetSommet = firstSet.territoire();
Collection<Coord> secondSetSommet = secondSet.territoire();
ArrayList<Coord> firstHull = new ArrayList<Coord>(firstSetSommet);
ArrayList<Coord> secondHull = new ArrayList<Coord>(secondSetSommet);
sommets = mergeHulls(firstHull, secondHull);
return sommets;
}
public Collection<Coord> mergeHulls(ArrayList<Coord> firstHull, ArrayList<Coord> secondHull)
{
Collection<Coord> pointsInside = new ArrayList<Coord>();
Collection<Coord> sommets = new ArrayList<Coord>();
//********************upper tangent***************
//find the highest point of the leftmost part
Coord firstPartHighestPoint = getMaxY(firstHull);
//find the highest point of the rightmost part
Coord secondPartHighestPoint = getMaxY(secondHull);
for(int i = 0; i< firstHull.size(); i++)
{
// check if the points lie on the line between highest point in leftmost and in rightmost
// if true, the current point is above the line
if(isCollinear(firstPartHighestPoint, secondPartHighestPoint, firstHull.get(i))>0)
{
// the current point is above the line
firstPartHighestPoint = firstHull.get(i);
}
pointsInside.add(firstPartHighestPoint);
}
for(int i = 0; i < secondHull.size(); i++)
{
if(isCollinear(firstPartHighestPoint, secondPartHighestPoint, secondHull.get(i))>0)
{
// the current point is above the line
secondPartHighestPoint = secondHull.get(i);
}
pointsInside.add(secondPartHighestPoint);
}
//******************lower tangent***************
//find the lowest point of the leftmost part
Coord firstPartLowestPoint = getMinY(firstHull);
// find the lowest point of the rightmost part
Coord secondPartLowestPoint = getMinY(secondHull);
for(int i = 0; i< firstHull.size(); i++)
{
// check if the points lie on the line between highest point in leftmost and in rightmost
// if true, the current point is above the line
if(isCollinear(firstPartLowestPoint, secondPartLowestPoint, firstHull.get(i)) < 0)
{
// the current point is above the line
firstPartLowestPoint = firstHull.get(i);
}
pointsInside.add(firstPartLowestPoint);
}
for(int i = 0; i < secondHull.size(); i++)
{
if(isCollinear(firstPartLowestPoint, secondPartLowestPoint, secondHull.get(i)) < 0)
{
// the current point is above the line
secondPartLowestPoint = secondHull.get(i);
}
pointsInside.add(firstPartLowestPoint);
}
sommets.addAll(firstHull);
sommets.addAll(secondHull);
sommets.removeAll(pointsInside);
return sommets;
}
//**********************************Auxiliary méthods****************************************************
// if the equation is equal to 0, the points are collinear
// the method returns the determinant of the point matrix
// This determinant tells how far point 'c' is from vector ab and on which side
// it is
// < 0 if the point 'c' is below the line (assumption : horizontal line)
// > 0 if the point 'c' is above the line
public double isCollinear(Coord a, Coord b, Coord c)
{
return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x));
}
//************************************** line equation ************************************************
// find the slope of the line between two points
public static double findSlope(Coord point1, Coord point2)
{
return (point2.y - point1.y)/(point2.x-point1.x);
}
// finding the constant 'b' of the line equation y = xm + b
public static double constantB(Double slope, Coord point)
{
return point.y - slope* point.x;
}
//*************************************** Minimum and Maximum "Y" *****************************************
// the point with maximum Y
public static Coord getMaxY(ArrayList<Coord> points)
{
double maxY = points.get(0).y; // start with the first value
Coord maxPoint = points.get(0);
for (int i=1; i<points.size(); i++) {
if (points.get(i).y > maxY)
{
maxY = points.get(i).y; // new maximum
maxPoint = points.get(i);
}
}
return maxPoint;
}
// a method to find the Point with the minimum y
public static Coord getMinY(ArrayList<Coord> points)
{
double minValue = points.get(0).y;
Coord minPoint = points.get(0);
for(int i=1;i<points.size();i++){
if(points.get(i).y < minValue)
{
minPoint = points.get(i);
minValue = points.get(i).y;
}
}
return minPoint;
}
//************************************** sorting the points ********************************************
//sorting the points by their x in ascending order
public static ArrayList<Coord> sortedArrayByX(ArrayList<Coord> arrayOfPoints)
{
//double minval = arrayOfPoints[0].x;
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).x < arrayOfPoints.get(j).x)
{
temp = arrayOfPoints.get(j+1);
arrayOfPoints.set(j+1, arrayOfPoints.get(j));
arrayOfPoints.set(j, temp);
}
}
}
return arrayOfPoints;
}
我不知道为什么在运行程序时出现以下消息:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
at java.util.ArrayList.rangeCheck(ArrayList.java:604)
at java.util.ArrayList.get(ArrayList.java:382)
at miniprojet2.CoordSet.getMaxY(CoordSet.java:270)
at miniprojet2.CoordSet.mergeHulls(CoordSet.java:154)
at miniprojet2.CoordSet.territoire(CoordSet.java:139)
at miniprojet2.CalculeTerritoire.main(CalculeTerritoire.java:36)
如果您告诉我我犯了一个错误，我会很高兴
最佳答案
注意:我假设您的代码在firstPart.add(sortedPointsByX.get(i))上失败。如果您发布SSCCE，我可以提供更好的帮助。sortedPointsByX的大小为零。
您的代码:
for(int i = 0; i < sortedPointsByX.size()/2+1; i++) {
firstPart.add(sortedPointsByX.get(i));
}
因此评估为:
for (int i=0; i<(0 / 2) + 1; i++) {
firstPart.add(sortedPointsByX.get(i));
}
这是:
for (int i=0; i<1; i++) {
firstPart.add(sortedPointsByX.get(i));
}
依次等于:
firstPart.add(sortedPointsByX.get(0));
但是，您无法获得
sortedPointsByX的zeroeth元素，因为它为空。您可以从错误中看出所有这些:
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
at java.util.ArrayList.rangeCheck(ArrayList.java:604)
IndexOutOfBoundsException表示您尝试访问一些索引i，例如i < 0或i >= size()。该错误报告大小为零，并且您尝试访问索引0。因此，0 ≥ 0和您的代码失败。