package test;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
public class Test {
public static Punkt[] pkt;
public static Wolke[] wlk;
public static void main(String[] args) throws FileNotFoundException {
// Parameter
String dateiname = "punkte.txt";
int anzahlWolken = 50;
init(dateiname, anzahlWolken);
long start = System.nanoTime();
berechne();
long time = (System.nanoTime() - start) / 1000000;
System.out.println("Time taken: " + time + " ms");
ausgabe();
}
public static void init(String dateiname, int anzahlWolken) throws FileNotFoundException{
int x, y;
Random rn = new Random();
HashSet<Punkt> randomPoints = new HashSet<Punkt>();
Punkt tmp;
// Datenstrukturen anlegen (werden nur temporär genutzt
ArrayList<Punkt> Punkte = new ArrayList<Punkt>();
ArrayList<Wolke> Wolken = new ArrayList<Wolke>();
// Punktliste einlesen
Scanner scanner = new Scanner(new File(dateiname));
while (scanner.hasNextInt()) {
x = scanner.nextInt();
if (scanner.hasNextInt()) y = scanner.nextInt();
else break;
Punkte.add(new Punkt(x,y));
}
pkt = Punkte.toArray(new Punkt[0]); // in Array wandeln
// Wolkenzentrum zufällig setzen, Hashset nutzen damit kein Punkt doppelt als Zentrum gewählt wird
if (anzahlWolken > pkt.length) anzahlWolken = pkt.length; // mehr Wolken als Punkte machen keinen Sinn
while(randomPoints.size() < anzahlWolken){
randomPoints.add(pkt[rn.nextInt(pkt.length)]);
}
for (Iterator<Punkt> it = randomPoints.iterator(); it.hasNext(); ) {
tmp = it.next();
Wolken.add(new Wolke(tmp.x, tmp.y));
}
wlk = Wolken.toArray(new Wolke[0]); // in Array wandeln
}
public static void berechne(){
double minAbstand, abstand, diffX, diffY;
int j, i, minP;
// Berechnungsarrays for Wolken vorbereiten
double sumX[] = new double[wlk.length];
double sumY[] = new double[wlk.length];
int cnt[] = new int[wlk.length];
// Objekte auf Wolken verteilen
for (i = 0; i < pkt.length; ++i) {
minAbstand = Double.MAX_VALUE;
minP = 0;
for (j = 0; j < wlk.length; ++j) {
diffX = pkt[i].x - wlk[j].x;
diffY = pkt[i].y - wlk[j].y;
abstand = (diffX*diffX) + (diffY*diffY);
if (minAbstand > abstand) {
minP = j;
minAbstand = abstand;
}
}
pkt[i].wolke = minP;
}
boolean changed = true;
while(changed){
changed = false;
// Wolkenzentren neu berechnen
for (j = 0; j < wlk.length; ++j) {
sumX[j] = 0;
sumY[j] = 0;
cnt[j] = 0;
}
for (i = 0; i < pkt.length; ++i) {
sumX[pkt[i].wolke] += pkt[i].x;
sumY[pkt[i].wolke] += pkt[i].y;
++cnt[pkt[i].wolke];
}
for (j = 0; j < wlk.length; ++j) {
// hier sollte man noch abfangen wenn cnt = 0...weiß aber nicht was man dann tut
wlk[j].x = sumX[j] / cnt[j];
wlk[j].y = sumY[j] / cnt[j];
}
// Objekte neu auf Wolken verteilen
for (i = 0; i < pkt.length; ++i) {
minAbstand = Double.MAX_VALUE;
minP = 0;
for (j = 0; j < wlk.length; ++j) {
diffX = pkt[i].x - wlk[j].x;
diffY = pkt[i].y - wlk[j].y;
abstand = (diffX*diffX) + (diffY*diffY);
if (minAbstand > abstand) {
minP = j;
minAbstand = abstand;
}
}
if(pkt[i].wolke != minP){
changed = true;
pkt[i].wolke = minP;
}
}
}
}
public static void ausgabe(){
int i, j;
for (j = 0; j < wlk.length; ++j) {
System.out.println("\n\nWolke #" + j + " @ (" + wlk[j].x + "," + wlk[j].y + ")");
for (i = 0; i < pkt.length; ++i) {
if(pkt[i].wolke == j) System.out.println("(" + pkt[i].x + "," + pkt[i].y + ")");
}
}
}
}