-2
Immer wenn ich versuche, diesen Code an mehr als 250 Punkten zu testen, führt dies zu einem Stack-Überlauffehler, alles unter 250 funktioniert perfekt. Irgendwelche Ideen, wie man mit größeren Zahlen arbeiten kann?Wie kann ich diesen Stack Overflow Fehler beheben?
public class Divide {
Point2D closest1;
Point2D closest2;
double Distance = Double.MAX_VALUE;
int CurrentPoint = 0;
int NextPoint = 0;
public Divide(Point2D[] RandArray){
SortArray s = new SortArray();
//Sort the array using SortArray class
RandArray = s.SortPointsX(RandArray);
SplitAndConquer(RandArray);
}
/**
* Recursively call itself to check the distance between the points
* sent in as parameters.
* @param a first point to be compared for distance.
* @param b second point to be compared for distance.
* @param s array of points that is being compared.
* @return The distance of the closest pair.
*/
private double ComparePoints(Point2D a, Point2D b, Point2D[] s){
//Checks to make sure two points aren't the same
if (a.getX() != b.getX() || a.getY() != b.getY()){
CheckDist(a, b);
}
// Increments the NextPoint if it's not the last point in the array
// and recursively calls the next point to compare current to.
if (b != s[s.length - 1]){
NextPoint++;
ComparePoints(s[CurrentPoint], s[NextPoint], s);
}
/* Sets the NextPoint to whatever the Current point is to prevent
* wasting comparisons between two points that have already been
* checked. Also increments the current point, and recursively
* calls the next point to compare it to.
*/
if (b == s[s.length - 1]){
if (a != s[s.length - 1]){
NextPoint = s.length - ((s.length - 1) - CurrentPoint);
CurrentPoint++;
ComparePoints(s[CurrentPoint], s[NextPoint], s);
}
}
//if the current point is the point at the end of the array it
//counters and returns the distance, ending the recursive calls
if (a == s[s.length - 1]){
CurrentPoint = 0;
NextPoint = 0;
return Distance;
}
return Distance;
}
/**
* Checks the distance between two points.
* @param a first point to be compared for distance.
* @param b second point to be compared for distance.
*/
private void CheckDist(Point2D a, Point2D b) {
//Checks the distance between two points
if (Distance > a.distance(b)){
Distance = a.distance(b);
//save the coordinates of the closest pair
closest1 = new Point2D.Double(a.getX(), a.getY());
closest2 = new Point2D.Double(b.getX(), b.getY());
}
}
/**
* Splits the array into two subsets and finds the closest pair among them.
* @param RandArray the array to be divided and searched.
*/
private void SplitAndConquer(Point2D[] RandArray){
//median of the array used to split the list into subsets
double median = RandArray[RandArray.length/2].getX();
//count used for splitting the array into subsets
int countS1 = 0;
int countS2 = 0;
//checks to see if the median is the point being sorted
boolean exact = false;
//Array to hold all points with x coordinate < median
Point2D[] s1 = new Point2D[RandArray.length/2];
//Array to hold all points with x coordinate > median
Point2D[] s2 = new Point2D[RandArray.length/2];
//Split the array comparing x coordinates and median
for (int i = 0; i < RandArray.length; i++){
if (RandArray[i].getX() < median){
s1[countS1] = RandArray[i];
countS1++;
}
else if (RandArray[i].getX() > median){
s2[countS2] = RandArray[i];
countS2++;
}
//alternates median value to ensure even subsets
else if (RandArray[i].getX() == median && exact == false){
s2[countS2] = RandArray[i];
exact = true;
countS2++;
}
else if (RandArray[i].getX() == median && exact == true) {
s1[countS1] = RandArray[i];
exact = false;
countS2++;
}
}
//Compares points if there are more than 2 points
if (s1.length > 2){
ComparePoints(s1[0], s1[1], s1);
ComparePoints(s2[0], s2[0], s2);
}else{
System.out.println
("One of the subsets does not contain enough points!");
}
//Checks the points that lie on the median
CheckMid(RandArray, Distance, median, CurrentPoint, NextPoint);
//Prints the closest pair
PrintClosest();
}
/**
* Prints the closest pairs found using Divide and Conquer
*/
private void PrintClosest() {
System.out.println("The closest pair found using Divide "
+ "And Conquer is at ("
+ closest1.getX() + " " + closest1.getY() + "), and ("
+ closest2.getX() + " " + closest2.getY() + ")");
System.out.println("The distance between the pairs is: " + Distance);
}
/**
* Checks the original array but only points located with the current
* distance from the median which was used to split for subsets.
* @param randArray Original array full of sorted points.
* @param d Current distance of the closest pair.
* @param m The median used to partition the array.
* @param current Current index of point being compared.
* @param next Index of the next point to be compared to current.
*/
private void CheckMid(Point2D[] randArray, double d, double m,
int current, int next) {
//temp array list to hold all the points within the median + distance
ArrayList<Point2D.Double> temp = new ArrayList<Point2D.Double>();
for(int i = 0; i < randArray.length; i++){
if(randArray[i].getX() > (m - d) &&
randArray[i].getX() < (m + d)){
temp.add((java.awt.geom.Point2D.Double) randArray[i]);
}
}
//Creates a new array to hold the values in the array list
Point2D[] MidArray = new Point2D[temp.size()];
for(int i = 0; i < temp.size(); i++)
{
MidArray[i] = temp.get(i);
}
//Makes sure the array list has enough points to be compared
if (MidArray.length >= 2){
if (MidArray[0] != null && MidArray[1] != null){
ComparePoints(MidArray[0], MidArray[1], MidArray);
}
}
}
}
1) Speicher erhöhen. 2) verwende keine Rekursion. –