Hallo Leute,
ich habe durch die Suchfunktion nichts gefunden was für mich nützlich war und ich denke mein Problem ist sehr speziell. Ich muss für die Schule ein Programm schreiben, welches eine Art Feld erzeugt auf dem man Punkte hinzufügen, löschen und ausgeben lassen kann. Die wichtigste Funktion des Programms ist die Berechnung des dichtesten Punktepaares. Dabei muss man wie folgt vorgehen:
Man muss das Feld in so viele Teilfelder teilen bis nur noch 2 oder 3 Punkte in dem Feld vorhanden sind.
Anschließend berechnet man von diesen 2-3 Punkten das dichteste Paar. Danach nimmt man 2 nebeneinander liegende Teilfelder und schaut ob sich im Bereich vor oder hinter der Trennlinie, die beide Felder trennt, Punkte befinden, die dichter als die dichtesten Paare der Teilfelder sind.Wenn nein schaut man welches der beiden dichtesten Paare dichter als das andere ist.Kurz: Man findet das dichteste Paar in den Teilfeldern. Dies soll solange geschehen, bis letztendlich das dichteste Paar gefunden wurde.
Die Kommandos zum hinzufügen, löschen ausgeben und zum berechnen des dichtesten Paares laufen über einen BufferedReader;
Eigentlich müsste der Code stimmen, jedoch gibt es 2 Probleme :
1.Das nicht so schlimme Problem ist, dass immer wenn ich das Kommando für die Berechnung des dichtesten Paares eingebe, die help() Methode ausgeführt wird, obwohl das nirgendwo im Code steht
2.Das größere Problem ist, dass die Methode zum Berechnen des dichtesten Punktepaares erst gar nicht aufgerufen wird bzw. es das dichteste Paar nicht berechnet.
Hier sind die einzelnen Klassen:
Shell.java - Kommunikation mit dem Benutzer
Point.java - Punkteklasse
Pair.java - Die Klasse für die Punktepaare
Field.java - Das Feld auf dem die Punkte liegen
Separator.java - Berechnung des dichtesten Paares
IdentDistPairs.java - Speiern des dichtesten Punktepaares
Es wäre nett, wenn jemand die 2.Fehler finden würde(von der Art und Weise der Implementierung mal abgesehen).Ich habe nicht mehr soviel Zeit, da ich es zuerst meine Freunde, die sich damit auskennen, gefragt habe, aber sie konnten mir auch nichts sagen.
ich habe durch die Suchfunktion nichts gefunden was für mich nützlich war und ich denke mein Problem ist sehr speziell. Ich muss für die Schule ein Programm schreiben, welches eine Art Feld erzeugt auf dem man Punkte hinzufügen, löschen und ausgeben lassen kann. Die wichtigste Funktion des Programms ist die Berechnung des dichtesten Punktepaares. Dabei muss man wie folgt vorgehen:
Man muss das Feld in so viele Teilfelder teilen bis nur noch 2 oder 3 Punkte in dem Feld vorhanden sind.
Anschließend berechnet man von diesen 2-3 Punkten das dichteste Paar. Danach nimmt man 2 nebeneinander liegende Teilfelder und schaut ob sich im Bereich vor oder hinter der Trennlinie, die beide Felder trennt, Punkte befinden, die dichter als die dichtesten Paare der Teilfelder sind.Wenn nein schaut man welches der beiden dichtesten Paare dichter als das andere ist.Kurz: Man findet das dichteste Paar in den Teilfeldern. Dies soll solange geschehen, bis letztendlich das dichteste Paar gefunden wurde.
Die Kommandos zum hinzufügen, löschen ausgeben und zum berechnen des dichtesten Paares laufen über einen BufferedReader;
Eigentlich müsste der Code stimmen, jedoch gibt es 2 Probleme :
1.Das nicht so schlimme Problem ist, dass immer wenn ich das Kommando für die Berechnung des dichtesten Paares eingebe, die help() Methode ausgeführt wird, obwohl das nirgendwo im Code steht
2.Das größere Problem ist, dass die Methode zum Berechnen des dichtesten Punktepaares erst gar nicht aufgerufen wird bzw. es das dichteste Paar nicht berechnet.
Hier sind die einzelnen Klassen:
Shell.java - Kommunikation mit dem Benutzer
Java:
/**
* Programm, welches das dichteste Punktepaar auf einem Feld findet. Die Punkte
* können gelöscht, hinzugefügt und ausgegeben werden.
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
public class Shell {
// Erstellt ein Feld, welches schon beim Programmstart vorhanden sein wird
public static Field field = new Field();
// Konstruktor
public Shell(){
}
// Hauptmethode
public static void main(String[] args) {
createBufferedReader();
}
// Erzeugt ein BufferedReader-Objekt, welches notwendig ist um etwas
// einzugeben und einzulesen. Falls die eingegebene Zeile nicht leer ist
// wird die Methode checkInput() mit der Zeile als Parameter ausgeführt
public static void createBufferedReader(){
System.out.println("Bitte machen Sie Ihre Eingabe");
try{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String line = br.readLine();
if(line != null){
checkInput(line);
}
}catch(IOException e) {
e.printStackTrace();
}
}
// Überprüft die Eingaben des Benutzers und führt je nach dem was eingegeben
// wurde eine spezielle Methode aus
public static void checkInput(String input){
String [] tokens = input.split(" ");
switch(tokens[0]){
case "NEW":
field = new Field();
field.reset();
case "ADD":
if (tokens.length == 3) {
int xPos = Integer.parseInt(tokens[1]);
int yPos = Integer.parseInt(tokens[2]);
Field.points.add(new Point(xPos, yPos));
Collections.sort(Field.points);
}
createBufferedReader();
case "REMOVE":
if (tokens.length == 3) {
int xPos = Integer.parseInt(tokens[1]);
int yPos = Integer.parseInt(tokens[2]);
field.removePoint(xPos, yPos);
}
createBufferedReader();
case "PRINT":
Point.print();
createBufferedReader();
case "DISTANCE":
if (field.points.size() > 2) {
Separator.findNearestPair();
}else if(field.points.size() == 2){
System.out.println("Das dichteste Punktepaar ist zwischen " +
field.points.get(0).toString() + " und " +
field.points.get(1).toString());
}else{
System.out.println("Error!Es befinden sich zu wenige Punkte" +
" auf dem Feld!");
}
case "HELP":
help();
createBufferedReader();
case "QUIT":
System.exit(0);
case "help":
help();
createBufferedReader();
case "quit":
System.exit(0);
case "h":
help();
createBufferedReader();
case "q":
System.exit(0);
case "H":
help();
createBufferedReader();
case "Q":
System.exit(0);
case "":
createBufferedReader();
}
}
// Gibt einen Hilfetext mit der Funktion des Programmes und einer Liste aller
// Kommandos/Befehle für dieses Programm aus
public static void help(){
System.out.println("Mit diesem Programm können Sie einem Feld " +
"Punkte hinzufügen, löschen, ausgeben lassen und das \n" +
"dichteste Paar berechnen. Dazu haben Sie folgende " +
"Kommandos, welche Sie eingeben können: \n 'NEW' - Erzeugt " +
"ein neues Feld \n 'ADD x y' - Erstellt einen neuen Punkt" +
" mit den Koordinaten (x,y) \n 'REMOVE x y' - Löscht den " +
"Punkt mit den Koordinaten (x,y) \n 'PRINT' - Gibt alle" +
" Punkte nach Koordinaten aufsteigend aus \n 'DISTANCE' - " +
"Gibt den Abstand des dichtesten Punktepaar aus, bei " +
"mehreren nach Koordinaten aufsteigend \n 'HELP' - Gibt " +
"diesen Hilfetext aus, Groß/Kleinschreibung irrelevant" +
"; erster Buchstabe des Kommandos genügt \n 'QUIT' - " +
"Schließt das Programm,, Groß/Kleinschreibung irrelevant" +
"; erster Buchstabe des Kommandos genügt");
}
}
Point.java - Punkteklasse
Java:
// Klasse Point, welche das Interface Comparable mit dem Generic Point
// implementiert
public class Point implements Comparable<Point>{
// Attribute sind die x und y Koordinaten des Punktes
public int x, y;
// Konstruktor
public Point(int x, int y){
this.x = x;
this.y = y;
}
// Methode, welche prüft ob ein Punkt mit einem anderen übereinstimmt
public boolean equals(Point p){
if((this.x == p.x) && (this.y == p.y)){
return true;
}
return false;
}
// Methode, welche alle Punkte auf dem Feld ausgibt
public static void print(){
for (int i = 0; i < Field.points.size(); i++) {
System.out.print("Punkt" + (1 + i) +
Field.points.get(i).toString());
}
}
// String-Repräsentation eines Punktes
public String toString(){
return "(" + x + ", " + y + ") " ;
}
// Methode zum Vergleichen von zwei Punkten
public int compareTo(Point other) {
if (this.x < other.x) {
return -1;
} else if (this.x > other.x) {
return +1;
} else {
if (this.y < other.y) {
return -1;
} else if (this.y > other.y) {
return +1;
} else {
return 0;
}
}
}
}
Pair.java - Die Klasse für die Punktepaare
Java:
//Klasse Pair, welche das Interface Comparable mit dem Generic Pair
//implementiert
public class Pair implements Comparable<Pair>{
// Attribute der Klasse Pair sind 2 Punkte und deren Distanz
public Point p, q;
public double distance;
// Konstruktor; der niedrigere Punkt ist p der hoehere q
public Pair(Point p, Point q){
if (p != null && q != null) {
if(p.compareTo(q) < 0){
this.p = p;
this.q = q;
}else{
this.p = q;
this.q = p;
}
distance = Math.hypot((p.x - q.x), (p.y - q.y));
}else{
distance = 0.00;
}
}
// Vergleicht 2 Paare
public int compareTo(Pair other) {
if (p.compareTo(other.p) < 0) {
return -1;
} else if (p.compareTo(other.p) > 0) {
return +1;
} else if (q.compareTo(other.q) < 0) {
return -1;
} else if (q.compareTo(other.q) > 0) {
return +1;
} else {
return 0;
}
}
}
Java:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Field {
// Erstellt eine Liste in der alle Punkte des jeweiligen Feldes eingespeichert
// werden
public static List<Point> points = new ArrayList<Point>();;
// Konstruktor
public Field(){
}
// Methode, welche einen Punkt mit den Koordinaten (x, y) löscht
public void removePoint(int xPos, int yPos){
for(int i = 0; i < points.size(); i++){
if((points.get(i).x == xPos) && (points.get(i).y == yPos)){
points.remove(i);
return;
}
}
System.out.println("Error!Dieser Punkt existiert nicht!");
}
// Methode, welche das Feld zurücksetz, also alle Punkte auf dem feld löscht
public void reset(){
for(int i = 0; i < points.size(); i++){
points.remove(i);
}
Shell.createBufferedReader();
}
}
Java:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Separator {
// Attribute der Klasse Separator
public static List<Integer> dividingLines = new ArrayList<Integer>();
public static List<Double> critdistance = new ArrayList<Double>();
public static List<Pair> pair = new ArrayList<Pair>();
// Konstruktor
public Separator(){
}
// Trennt das Feld in Teilfelder bis nur 2 bis 3 Punkte im Teilfeld vorhanden
// sind
public static void divideField(int start, int end){
if(!dividingLines.contains(start)){
dividingLines.add(start);
Collections.sort(dividingLines);
}else if(!dividingLines.contains(end)){
dividingLines.add(end);
Collections.sort(dividingLines);
}else if(!checkArea(start, end)){
int mid = divideInHalf(start, end);
divideField(start, mid);
divideField(mid, end);
}
}
// Findet das dichteste Paar
public static void findNearestPair() {
divideField(Field.points.get(0).x,
Field.points.get(Field.points.size() - 1).x);
checkEveryPart(dividingLines.get(0),
dividingLines.get(dividingLines.size() - 1) , 0 ,
dividingLines.size() - 1);
searchNearestPair();
}
// Sucht das dichteste Paar indem die Paarliste durchgegangen wird
// anschließend wird das kleinstePaar zu IdentDistPairs.pairs hinzugefügt
// und die Methode outputPoints() in der Klasse IdentDistPairs ausgeführt
private static void searchNearestPair(){
if (pair.size() > 0) {
List<Pair> nearestPairs = new ArrayList<Pair>();
Pair pair1 = pair.get(0);
for (int i = 0; i < pair.size(); i++) {
if(pair.get(i).distance <= pair1.distance){
if(checkDistance(nearestPairs, pair.get(i).distance)){
Pair one = pair.get(i);
nearestPairs.removeAll(pair);
nearestPairs.add(one);
}else{
nearestPairs.add(pair.get(i));
}
}
}
IdentDistPairs.pairs = nearestPairs;
IdentDistPairs.outputPoints();
}
}
// Durchsucht rekursiv das Feld nach dem dichtesten Paar
private static void checkEveryPart(int start, int end, int index1, int
index2){
if (index1 + 2 < dividingLines.size() && index2 - 2 > -1) {
if (index1 == 0 && index2 == dividingLines.size() - 1) {
checkCriticArea(start, dividingLines.get(index1 + 2),
pair.get(index1), pair.get(index1 + 1));
checkCriticArea(dividingLines.get(index2 - 2), end,
pair.get(index2), pair.get(index2 - 1));
index1 += 2;
index2 -= 2;
checkEveryPart(0, 0, index1, index2);
} else if (index1 == index2) {
return;
} else if (index1 + 1 == index2 - 1) {
checkCriticArea(dividingLines.get(index1),
dividingLines.get(index2), pair.get(index1),
pair.get(index2));
} else {
checkCriticArea(dividingLines.get(index1),
dividingLines.get(index1 + 2), pair.get(index1),
pair.get(index1 + 1));
checkCriticArea(dividingLines.get(index2 - 2),
dividingLines.get(index2), pair.get(index2),
pair.get(index2 - 1));
index1 += 2;
index2 -= 2;
checkEveryPart(0, 0, index1, index2);
}
}
}
// Prüft die kritischen Knoten
private static void checkCriticArea(int start, int end, Pair p1,
Pair p2){
int area = 0;
if(p1.distance < p2.distance){
area = (int) p1.distance;
}else if(p2.distance < p1.distance){
area = (int) p2.distance;
}
int mid = (end - start) / 2;
for (int j = Field.points.size() - 1; j > -1; j++) {
for (int i = 0; i < Field.points.size(); i++) {
if(isInCriticArea(Field.points.get(i), mid - area, mid + area)
&& isInCriticArea(Field.points.get(j), mid - area, mid
+ area)){
Pair p3 = new Pair(Field.points.get(i),
Field.points.get(j));
if(findMinPair(p1, p2, p3) != p1 || findMinPair(p1, p2, p3)
!= p2){
pair.add(p3);
critdistance.add(p3.distance);
Collections.sort(pair);
}
}
}
}
}
// Findet das dichteste Paar unter 3 Paaren
private static Pair findMinPair(Pair p1, Pair p2, Pair p3){
if(p1.distance > p2.distance && p2.distance < p3.distance){
return p2;
}else if(p1.distance > p3.distance && p3.distance < p2.distance){
return p3;
}else if(p2.distance > p1.distance && p1.distance < p3.distance){
return p2;
}
return null;
}
// Prüft ob ein Punkt in einem bestimmten Bereich ist
private static boolean isInCriticArea(Point point, int start, int end){
for (int i = 0; i < Field.points.size(); i++) {
if (Field.points.get(i).x >= start
&& Field.points.get(i).x <= end) {
return true;
}
}
return true;
}
// Findet für jedes Teilfeld das dichteste Paar
private void findMinInAllParts(){
for(int i = 0; i < dividingLines.size(); i++){
if(i < dividingLines.size() - 1){
findMin(getPoints(dividingLines.get(i),
dividingLines.get(i + 1)));
}
}
}
// Finden des dichtesten Pärchens von 3 Punkten
public static void findMin(Point[] p){
Pair a = null;
Pair b = null;
Pair c = null;
if (p.length >= 3) {
a = new Pair(p[0], p[1]);
b = new Pair(p[1], p[2]);
c = new Pair(p[0], p[2]);
if(p[2] == null){
Pair p1 = new Pair(p[0], p[1]);
pair.add(p1);
critdistance.add(p1.distance);
Collections.sort(pair);
return;
}
}
if(a.distance > b.distance && b.distance < c.distance){
pair.add(b);
critdistance.add(b.distance);
Collections.sort(pair);
return;
}else if(a.distance > c.distance && c.distance < b.distance){
pair.add(c);
critdistance.add(c.distance);
Collections.sort(pair);
return;
}else if(b.distance > a.distance && a.distance < c.distance){
pair.add(a);
critdistance.add(a.distance);
Collections.sort(pair);
return;
}
}
// Gibt die Punkte in dem Bereich zwischen start und end aus
private static Point[] getPoints(int start, int end){
Point [] p = new Point[3];
for(int i = 0; i < p.length; i++){
if(Field.points.get(i).x >= start && Field.points.get(i).x <= end){
p[i] = Field.points.get(i);
}
}
return p;
}
// Methode zur Teilung des in der Mitte
public static int divideInHalf(int start, int end) {
int half = 0;
if(Field.points.size() % 2 != 0){
for (int j = Field.points.size() - 1; j > -1; j--) {
for (int i = 0; i < Field.points.size(); i++) {
if(j == i){
half = Field.points.get(j).x;
}
}
}
}else{
for (int j = Field.points.size() - 1; j > -1; j--) {
for (int i = 0; i < Field.points.size(); i++) {
if(j == i + 1 && i == j - 1){
half = half(Field.points.get(i).x,
Field.points.get(j).x);
}
}
}
}
return half;
}
private static int half(int one, int two){
if(one > two){
two += (one - two)/2;
return two;
}else{
one += (two - one)/2;
return one;
}
}
// Prüft ob sich ein Paar mit niedrigerer Distanz als das ein anderes in der
// Liste befindet
private static boolean checkDistance(List<Pair> list, double value){
boolean isThere = false;
for(int i = 0; i < list.size(); i++) {
if(list.get(i).distance > value){
isThere = true;
}
}
return isThere;
}
// Prüft ob nur noch 2 oder 3 Punkte im Feld zwischen start und end sind und
// gibt true zurück, wenn es stimmt und false, wenn nicht
private static boolean checkArea(int start, int end) {
long count = 0;
for (int i = 0; i < Field.points.size(); i++) {
if (Field.points.get(i).x >= start
&& Field.points.get(i).x <= end) {
count++;
}
}
if(count > 3){
return false;
}else if(count == 2 || count == 3){
return true;
}
return true;
}
}
IdentDistPairs.java - Speiern des dichtesten Punktepaares
Java:
import java.util.ArrayList;
import java.util.List;
public class IdentDistPairs {
// Attribute
public static List<Pair> pairs = new ArrayList<Pair>();
public static double minimalDistance = 0;
// Konstruktor
public IdentDistPairs(){
}
// Ausgabe des dichtesten Punktepaares
public static void outputPoints(){
if(pairs.size() > 1){
System.out.println("Der kleinste Abstand zwischen 2 Punkten ist " +
minimalDistance + " und zwar zwischen folgenden " +
"Punktenpaaren:");
for(int i = 0; i < pairs.size(); i++){
if(i != pairs.size() - 1) {
System.out.print(" " + pairs.get(i).p.toString() + " und "
+ pairs.get(i).q.toString() + ", ");
}else{
System.out.print(" " + pairs.get(i).p.toString() + " und "
+ pairs.get(i).q.toString());
}
}
}else if(pairs.size() == 1){
System.out.println("Der kleinste Abstand zwischen 2 Punkten ist " +
minimalDistance + " und zwar zwischen " +
pairs.get(0).p.toString() + " und " +
pairs.get(0).q.toString());
}else{
System.out.println("Error!Es existieren keine Punkte auf diesem " +
"Feld!");
}
Shell.createBufferedReader();
}
}
Es wäre nett, wenn jemand die 2.Fehler finden würde(von der Art und Weise der Implementierung mal abgesehen).Ich habe nicht mehr soviel Zeit, da ich es zuerst meine Freunde, die sich damit auskennen, gefragt habe, aber sie konnten mir auch nichts sagen.