Я написал java-программу, которая использует алгоритм «разделяй и властвуй», чтобы найти выпуклую оболочку многоугольника в декартовой координации. У меня есть класс Coord, который имеет два «двойных» поля X и y, а «это», для которого я использую метод, представляет собой набор координат (набор). мой метод должен возвращать корпус (коллекцию) многоугольника
Мой код такой:
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)
Я буду так рад, если вы скажете мне, где я сделал ошибку
