Programmieren lernen

package eu.gressly.hw.divide.abstaende;

import java.io.*;
import java.util.*;

/**
 * Findet aus einer Tabelle mit x/y-Koordinaten (Komma getrennt) die beiden
 * Punkte, die am nächsten beisammen liegen.
 * 
 * @author Philipp Gressly (phi@gressly.ch)
 */
/*
 * History: first Implementation: Mar 2, 2010 Bugs :
 */

class Punkt {
    double x, y;

    public double abstand(Punkt p2) {
        double dx = this.x - p2.x;
        double dy = this.y - p2.y;
        return Math.sqrt(dx * dx + dy * dy);    }

    @Override
    public String toString() {
        return "x=" + x + ", y=" + y;   }
    
}


class Punktepaar {
    Punkt p1, p2;

    public Punktepaar(Punkt p1, Punkt p2){
        this.p1 = p1;
        this.p2 = p2;   }

    public double abstand() {
        return p1.abstand(p2);   }

    public boolean besserAls(Punktepaar other) {
        return this.abstand() < other.abstand();   }

    @Override
    public String toString() {
        return "" + p1 + " abstand zu " + p2 + " = " + abstand();  }

}


public class FindeNaechsteNachbarn {

    public static void main(String[] args) {
        new FindeNaechsteNachbarn().top();   }

    void top() {
        try {
            ArrayList<Punkt> punkte = lesePunkte("Punkte.txt");
            Punktepaar naechsteNachbarn = naechsteNachbarn(punkte);
            System.out.println("Nächste Punkte: " + naechsteNachbarn);
        } catch (IOException e) {
            System.out.println("File Fehler: " + e);
            e.printStackTrace();
        }
    }

    private Punktepaar naechsteNachbarn(ArrayList<Punkt> punkte) {
        if (2 > punkte.size()) {
            return null;       }
        if (2 == punkte.size()) {
            return new Punktepaar(punkte.get(0), punkte.get(1));      }
        if (3 == punkte.size()) {
            Punktepaar p01 = new Punktepaar(punkte.get(0), punkte.get(1));
            Punktepaar p12 = new Punktepaar(punkte.get(1), punkte.get(2));
            Punktepaar p20 = new Punktepaar(punkte.get(2), punkte.get(0));
            if (p01.besserAls(p12) && p01.besserAls(p20)) {
                return p01;
            }
            if (p12.besserAls(p20) && p12.besserAls(p01)) {
                return p12;
            }
            if (p20.besserAls(p01) && p20.besserAls(p12)) {
                return p20;
            }
        }
        if (spannBreite(punkte) > spannHoehe(punkte)) {
            return findeNaechsteNachbarnDurchVertikalesHalbieren(punkte);       }
        return findeNaechsteNachbarnDurchHorizontaleHalbierung(punkte);
    }

    /**
     * S. analoger Code "vertikal"
     * 
     * @return
     */
    private Punktepaar findeNaechsteNachbarnDurchHorizontaleHalbierung(
            ArrayList<Punkt> punkte) {
        if (punkte.size() < 4) {
            throw new IndexOutOfBoundsException("Zu wenig Punkte zur Trennung");      }
        ArrayList<Punkt> punkteLinks = new ArrayList<Punkt>();
        ArrayList<Punkt> punkteRechts = new ArrayList<Punkt>();
        halbiereOptimalLinksRechts(punkte, punkteLinks, punkteRechts);

        Punktepaar punkteLinksMinimumPaar = naechsteNachbarn(punkteLinks);
        Punktepaar punkteRechtsMinimumPaar = naechsteNachbarn(punkteRechts);

        Punktepaar absMinPunktePaar;
        if (punkteLinksMinimumPaar.besserAls(punkteRechtsMinimumPaar)) {
            absMinPunktePaar = punkteLinksMinimumPaar;
        } else {
            absMinPunktePaar = punkteRechtsMinimumPaar;
        }

        double xTrennbreite = berechneBesteTrennBreite(punkteLinks
                .get(punkteLinks.size() - 1), punkteRechts.get(0));

        ArrayList<Punkt> streifenRechtsDerTrennlinie = extractSteifenRechtsDerTrennlinie(
                punkteRechts, absMinPunktePaar.abstand(), xTrennbreite);
        ArrayList<Punkt> streifenLinksDerTrennlinie = extractSteifenLinksDerTrennlinie(
                punkteLinks, absMinPunktePaar.abstand(), xTrennbreite);

        for (Punkt links : streifenLinksDerTrennlinie) {
            for (Punkt rechts : streifenRechtsDerTrennlinie) {
                if (links.abstand(rechts) < absMinPunktePaar.abstand()) {
                    absMinPunktePaar = new Punktepaar(links, rechts);
                }
            }
        }
        return absMinPunktePaar;
    }

    /**
     * Mit minimal 4 Punkten aufrufen
     * 
     * @return
     */
    private Punktepaar findeNaechsteNachbarnDurchVertikalesHalbieren(
            ArrayList<Punkt> punkte) {
        if (punkte.size() < 4) {
            throw new IndexOutOfBoundsException("Zu wenig Punkte zur Trennung");
        }
        ArrayList<Punkt> punkteUnten = new ArrayList<Punkt>();
        ArrayList<Punkt> punkteOben = new ArrayList<Punkt>();
        halbiereOptimalObenUnten(punkte, punkteUnten, punkteOben);

        Punktepaar punkteUntenMinimumPaar = naechsteNachbarn(punkteUnten);
        Punktepaar punkteObenMinimumPaar = naechsteNachbarn(punkteOben);

        Punktepaar absMinPunktePaar;
        if (punkteObenMinimumPaar.besserAls(punkteUntenMinimumPaar)) {
            absMinPunktePaar = punkteObenMinimumPaar;
        } else {
            absMinPunktePaar = punkteUntenMinimumPaar;
        }

        double yTrennhoehe = berechneBesteTrennHoehe(punkteUnten
                .get(punkteUnten.size() - 1), punkteOben.get(0));

        ArrayList<Punkt> streifenUeberTrennlinie = extractStreifenUeberTrennlinie(
                punkteOben, absMinPunktePaar.abstand(), yTrennhoehe);
        ArrayList<Punkt> streifenUnterTrennlinie = extractSteifenUnterTrennlinie(
                punkteUnten, absMinPunktePaar.abstand(), yTrennhoehe);

        for (Punkt oben : streifenUeberTrennlinie) {
            for (Punkt unten : streifenUnterTrennlinie) {
                if (oben.abstand(unten) < absMinPunktePaar.abstand()) {
                    absMinPunktePaar = new Punktepaar(oben, unten);
                }
            }
        }

        return absMinPunktePaar;
    }

    /**
     * Mittelwert zwischen unterstem Punkt in der oberen Teilmenge und oberstem
     * Punkt in den unteren Teilmenge.
     */
    private double berechneBesteTrennHoehe(Punkt obersterPunktUnten,
            Punkt untersterPuntkOben) {
        return (obersterPunktUnten.y + untersterPuntkOben.y) / 2;
    }

    /**
     * Wie TrennHoehe, jedoch bei vertikalem Trennschnitt
     */
    private double berechneBesteTrennBreite(Punkt rechtesterPunktLinks,
            Punkt linksterPunktRechts) {
        return (linksterPunktRechts.x + rechtesterPunktLinks.x) / 2;
    }

    /**
     * Finde alle Punkte unter der Trennlinie (also in "punkteUnten"), die max
     * "abstand" unter der "yTrennhoehe" sind.
     */
    private ArrayList<Punkt> extractSteifenUnterTrennlinie(
            ArrayList<Punkt> punkteUnten, double abstand, double yTrennhoehe) {
        ArrayList<Punkt> streifen = new ArrayList<Punkt>();
        for (int i = punkteUnten.size() - 1; i >= 0; i--) {
            Punkt akt = punkteUnten.get(i);
            if (yTrennhoehe - akt.y <= abstand) {
                streifen.add(akt);
            } else {
                return streifen; // kann keine weiteren geben, denn die Punkte
                                 // waren sortiert.
            }
        }
        return streifen;
    }

    /**
     * Finde alle Punkte über der Trennlinie (also in "punkteOben"), die max
     * "abstand" über der "yTrennhoehe" sind.
     */
    private ArrayList<Punkt> extractStreifenUeberTrennlinie(
            ArrayList<Punkt> punkteOben, double abstand, double yTrennhoehe) {
        ArrayList<Punkt> streifen = new ArrayList<Punkt>();
        for (Punkt p : punkteOben) {
            if (p.y - yTrennhoehe <= abstand) {
                streifen.add(p);
            } else {
                return streifen; // s. oben
            }
        }
        return streifen;
    }

    /**
     * s. oben
     */
    private ArrayList<Punkt> extractSteifenRechtsDerTrennlinie(
            ArrayList<Punkt> punkteRechts, double abstand, double xTrennbreite) {
        ArrayList<Punkt> streifen = new ArrayList<Punkt>();
        for (Punkt p : punkteRechts) {
            if (p.x - xTrennbreite <= abstand) {
                streifen.add(p);
            } else {
                return streifen; // s. oben
            }
        }
        return streifen;
    }

    /**
     * s. oben
     */
    private ArrayList<Punkt> extractSteifenLinksDerTrennlinie(
            ArrayList<Punkt> punkteLinks, double abstand, double xTrennbreite) {
        ArrayList<Punkt> streifen = new ArrayList<Punkt>();
        for (int i = punkteLinks.size() - 1; i >= 0; i--) {
            Punkt akt = punkteLinks.get(i);
            if (xTrennbreite - akt.x <= abstand) {
                streifen.add(akt);
            } else {
                return streifen; // s. oben
            }
        }
        return streifen;
    }

    private void halbiereOptimalObenUnten(ArrayList<Punkt> punkte,
            ArrayList<Punkt> punkteUnten, ArrayList<Punkt> punkteOben) {
        Collections.sort(punkte, new Comparator<Punkt>() {
            @Override
            public int compare(Punkt o1, Punkt o2) {
                return o2.y > o1.y ? 1 : -1;
            }
        });

        for (int i = 0; i < punkte.size(); i++) {
            if (i < punkte.size() / 2) {
                punkteUnten.add(punkte.get(i));
            } else {
                punkteOben.add(punkte.get(i));
            }
        }
    }

    private void halbiereOptimalLinksRechts(ArrayList<Punkt> punkte,
            ArrayList<Punkt> punkteLinks, ArrayList<Punkt> punkteRechts) {
        Collections.sort(punkte, new Comparator<Punkt>() {
            @Override
            public int compare(Punkt o1, Punkt o2) {
                return o2.x > o1.x ? -1 : 1;
            }
        });

        for (int i = 0; i < punkte.size(); i++) {
            if (i < punkte.size() / 2) {
                punkteLinks.add(punkte.get(i));
            } else {
                punkteRechts.add(punkte.get(i));
            }
        }
    }

    /**
     * Spannweite in die Breite.
     */
    private double spannBreite(ArrayList<Punkt> punkte) {
        if (2 > punkte.size()) {
            return 0.0;
        }
        double linkstes = Double.MAX_VALUE;
        double rechtstes = Double.MIN_VALUE;
        for (Punkt p : punkte) {
            if (linkstes > p.x) {
                linkstes = p.x;
            }
            if (rechtstes < p.x) {
                rechtstes = p.x;
            }
        }
        return rechtstes - linkstes;
    }

    /**
     * Spannweite in der Höhe
     */
    private double spannHoehe(ArrayList<Punkt> punkte) {
        if (2 > punkte.size()) {
            return 0.0;
        }
        double unterstes = Double.MAX_VALUE;
        double oberstes = Double.MIN_VALUE;
        for (Punkt p : punkte) {
            if (unterstes > p.y) {
                unterstes = p.y;
            }
            if (oberstes < p.y) {
                oberstes = p.y;
            }
        }
        return oberstes - unterstes;
    }

    /**
     * Lese Punkte ab File
     * 
     * @throws IOException
     *             when the File is not opened or can not be read.
     */
    ArrayList<Punkt> lesePunkte(String fileName) throws IOException {
        ArrayList<Punkt> punkte = new ArrayList<Punkt>();
        FileReader fr = new FileReader(fileName);
        LineNumberReader lnr = new LineNumberReader(fr);
        String line;
        while (null != (line = lnr.readLine())) {
            StringTokenizer st = new StringTokenizer(line, ",");
            String xStr = st.nextToken();
            String yStr = st.nextToken();
            Punkt p = new Punkt();
            p.x = Double.parseDouble(xStr);
            p.y = Double.parseDouble(yStr);
            punkte.add(p);
        }
        fr.close();
        return punkte;
    }

} // end of class FindeNaechsteNachbarn
                

import math
from operator import itemgetter, attrgetter
infinity = float('inf')
coord_list = []
# Koordinaten File einlesen
def read_coordinate_file(name):
    f = open(name, 'r')
    for line in f:
        tmp = line.split(',')
        x = float(tmp[0])
        y = float(tmp[1])
        coord = (x,y)
        coord_list.append(coord)
# kartesische Abstand
def abstand(a,b):
    return math.sqrt((a[0]-b[0])*(a[0]-b[0])+(a[1]-b[1])*(a[1]-b[1]))
# Jeden Punkt mit jedem Vergleichen aus der Liste Punkte
def bruteForcenaechsterNachbar(punkte):
    numPoints = len(punkte)
    if numPoints < 2:
        return infinity, (None, None)
    return min(((abstand(punkte[i], punkte[j]),(punkte[i], punkte[j]))
                 for i in range(numPoints-1)
                 for j in range(i+1,numPoints)),
                key=itemgetter(0))

def naechsterNachbar(punkte):
    # Punkte nach x und y sortieren
    xP = sorted(coord_list, key=lambda coord: coord[0])
    yP = sorted(coord_list, key=lambda coord: coord[1])
    return _naechsterNachbar(xP, yP)
 
def _naechsterNachbar(xP, yP):
    numPoints = len(xP)
    if numPoints <= 3:
        return bruteForcenaechsterNachbar(xP)
    Pl = xP[:numPoints/2]
    Pr = xP[numPoints/2:]
    Yl, Yr = [], []
    #xDivider = letzter xWert in der 1. Liste
    xDivider = Pl[-1][0]
    for p in yP:
        if p[0] <= xDivider:
            Yl.append(p)
        else:
            Yr.append(p)
    dl, pairl = _naechsterNachbar(Pl, Yl)
    dr, pairr = _naechsterNachbar(Pr, Yr)
    dm, pairm = (dl, pairl) if dl < dr else (dr, pairr)
    # Points within dm of xDivider sorted by Y coord
    closeY = [p for p in yP  if abs(p[0]-xDivider) < dm]
    numCloseY = len(closeY)
    if numCloseY > 1:
        # There is a proof that you only need compare a max of 7 next points
        closestY = min( ((abstand(closeY[i],closeY[j]), (closeY[i], closeY[j]))
                         for i in range(numCloseY-1)
                         for j in range(i+1,min(i+8, numCloseY))),
                        key=itemgetter(0))
        return (dm, pairm) if dm <= closestY[0] else closestY
    else:
        return dm, pairm

read_coordinate_file('punkte.txt')

print naechsterNachbar(coord_list)
#print bruteForcenaechsterNachbar(coord_list)