Programmieren lernen

/****************************************************************************
 * class: Kreis.java
 ****************************************************************************/
 
 package eu.gressly.hw.divide.maler;


import java.text.DecimalFormat;

import eu.gressly.gui.turtle.Turtle;

public class Kreis {
  double x, y; // Mittelpunkt
  double r;    // radius
  
  static DecimalFormat df = new DecimalFormat("#.000");
  @Override
  public String toString() {   
      return "(x,y): " + "(" + df.format(x) + "," + df.format(y) + ") r=" + df.format(r);  }


  public boolean schneidet(Kreis andererKreis) {
    double abstand = this.mittelpunktsAbstand(andererKreis);
    return (abstand < this.r + andererKreis.r); }


  double mittelpunktsAbstand(Kreis andererKreis) {
    double dx = this.x - andererKreis.x;
    double dy = this.y - andererKreis.y;
    return Math.sqrt(dx * dx + dy * dy); }

  public void zeichne(Turtle t) {
    t.moveTo(x,y);
    t.setDirection(r, 0);
    t.move();
    t.setDirection(0, 2 * r * Math.PI / 32);
    for(int i = 0; i < 32; i ++) {
        t.draw();
        t.turnLeft(360.0 / 32);  }
  }

} // end of class Kreis

/****************************************************************************
 * class: Wand.java
 ****************************************************************************/

package eu.gressly.hw.divide.maler;

import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;

import eu.gressly.gui.turtle.Turtle;

public class Wand {
    double   x     ,     y; // Koordinaten x: nach rechts, y: nach oben
    double   breite, hoehe; // breite->nach rechts; hoehe->nach oben

    ArrayList<Kreis> kreise;

    /**
     * @param wand
     */
    public Wand(Wand wand){
        this.rechteckKlonen(wand);   }

    public Wand(int x, int y, int breite, int hoehe){
        this.x      =      x;
        this.y      =      y;
        this.breite = breite;
        this.hoehe  =  hoehe;   }

    void rechteckKlonen(Wand w) {
        this.x      = w.x;
        this.y      = w.y;
        this.breite = w.breite;
        this.hoehe  = w.hoehe;  }
    
    public int anzahlKreise() {
        if(null == kreise) {
            return 0;  }
        return kreise.size(); }

    void kreisHinzufuegen(Kreis k) {
        if (null == kreise) {
            kreise = new ArrayList<Kreis>();
        }
        kreise.add(k); }
 
    void zeichne(Turtle t) {
        for (Kreis k : kreise) {
            k.zeichne(t); }
    }
    
    public void setColor(Turtle t, String string) {
        t.setColor(string);   }

  

    public Wand[] teileWand() {
        Wand w1 = new Wand(this);
        Wand w2 = new Wand(this);
        if(breiterAlsHoch()) {
            w1.breite =     breite / 2;
            w2.breite =     breite / 2;
            w2.x      = x + breite / 2;  }
        else {
            w1.hoehe  =     hoehe / 2;
            w2.hoehe  =     hoehe / 2;
            w2.y      = y + hoehe / 2;
        }
        for(Kreis k : this.kreise) {
            if(w1.enthaeltMittelpunkt(k)) {
                w1.kreisHinzufuegen(k);
            }
            if(w2.enthaeltMittelpunkt(k)) {
                w2.kreisHinzufuegen(k);
            }
        }
        return new Wand [] {w1, w2};    
    }

    boolean breiterAlsHoch() {
        return breite > hoehe; }
    
    void uebernimmKreiseMitMitterpunktInWand(Wand w) {
        for(Kreis k : this.kreise) {
            if(w.enthaeltMittelpunkt(k)) {
                w.kreisHinzufuegen(k);   }
        }
    }

    boolean enthaeltMittelpunkt(Kreis k) {
        if(k.x < x)          { return false; }
        if(k.x > x + breite) { return false; }
        if(k.y < y)          { return false; }
        if(k.y > y + hoehe)  { return false; }
        return true;  }

    public void entferne(Kreis kreis) {
       this.kreise.remove(kreis);
       if(0 == this.kreise.size()) {
           kreise = null;   }
    }

   
    public boolean linksVon(Wand w2) {
        return x < w2.x;    }
   
    public boolean unter(Wand w2) {
        return this.y < w2.y;    }

    /**
     * @param kante "rechts", "links", "oben", "unten"
     */
    public boolean lugtHeraus(Kreis kreis, String kante) {
        if("rechts".equals(kante)) {
            return kreis.x + kreis.r > x + breite;
        }
        if("links".equals(kante)) {
            return kreis.x - kreis.r < x;
        }
        if("oben".equals(kante)) {
            return kreis.y + kreis.r > y + hoehe;
        }
        if("unten".equals(kante)) {
            return kreis.y - kreis.r < y;
        }
        System.out.println("Fehler: kann nur rechts, links, oben oder unten rauskucken");
        return false;
    }

    
    public boolean enthaelt(Kreis k) {
        if(null == this.kreise)
            return false;
        return kreise.contains(k);  }

    /**
     * TODO document Method
     * @param teilwaende
     */
    public void setKreise(Wand[] teilwaende) {
        this.kreise = new ArrayList<Kreis>();
        for(Wand w : teilwaende) {
            if(null != w.kreise) {
                this.kreise.addAll(w.kreise);   }
        }
    }

   
    public void printKreiseToFile() {
        try {
            FileWriter fw = new FileWriter("Kreise.txt");
            for(Kreis k : kreise) {
                printKreis(fw, k);
            }
            fw.close(); }
        catch (IOException iox) {
            System.err.println("Fehler im File " + iox); }
    }

    void printKreis(FileWriter fw, Kreis k) throws IOException {
        fw.write("" + k + "\n");      }

} // end of class Wand

/****************************************************************************
 * class: Maler.java
 ****************************************************************************/

package eu.gressly.hw.divide.maler;

import java.util.ArrayList;

import eu.gressly.gui.turtle.*;

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

   
  Turtle malerMeistersPinsel = SideNeckedTurtle.createTurtle();
 
   
  void top() {
      Wand w = new Wand(0, 0, 2000, 1000);
      int i = 1;
      while(i <= 10000) {
          Kreis k = zufallsKreis(w);
          w.kreisHinzufuegen(k);
          i = i + 1;
      }
      w.printKreiseToFile();
      w.zeichne(malerMeistersPinsel);
      eliminiereUeberschneidungen(w);
      w.setColor(malerMeistersPinsel, "green");
      w.zeichne(malerMeistersPinsel);  }
   
   
  boolean vieleKreise(Wand w) {
       return w.anzahlKreise() > 10;  }

   
  void eliminiereUeberschneidungen(Wand w) {
     if(vieleKreise(w)) {
        Wand [] teilwaende = w.teileWand();
        eliminiereUeberschneidungen(teilwaende[0]);
        eliminiereUeberschneidungen(teilwaende[1]);
        eliminiereUeberschneidungenAnKante(teilwaende[0], teilwaende[1]); 
        w.setKreise(teilwaende); }
     else {
        eliminiereWenige(w); }
  }

  void eliminiereWenige(Wand w) {
     if(0 == w.anzahlKreise()) return;
     ArrayList<Kreis> zuEntfernen = new ArrayList<Kreis>();
     for(Kreis k1 : w.kreise) {
        // TODO: Hier können noch 50% herausgeholt werden, wenn k2 kein k1 ist, das bereits vorkam.
        for(Kreis k2 : w.kreise) {
            if(k1 != k2) {
                if(k1.schneidet(k2)) {
                    // eliminiere den größeren
                    if(k1.r > k2.r) {
                        zuEntfernen.add(k1); }
                    else {
                        zuEntfernen.add(k2);  }
                }
            }
        }
     }
     for(Kreis k : zuEntfernen) {
        w.entferne(k);  }  
  } // end "eliminiereWenige()"

   
  void eliminiereUeberschneidungenAnKante(Wand w1, Wand w2) {
    if(0 == w1.anzahlKreise() || 0 == w2.anzahlKreise()) {return;} 
    if(w1.linksVon(w2)) {
        eliminiereKante(w1, w2, "rechts");
        eliminiereKante(w2, w1, "links" );  }
    else if (w1.unter(w2)) {
        eliminiereKante(w1, w2, "oben"  );
        eliminiereKante(w2, w1, "unten" );  }
  }
   
  
  void eliminiereKante(Wand w1, Wand w2, String kante) {
    ArrayList<Kreis> zuEliminieren = new ArrayList<Kreis>();
    if(w1.anzahlKreise() <= 0) return;
    if(w2.anzahlKreise() <= 0) return;
    for(Kreis k1 : w1.kreise) {
        if(w1.lugtHeraus(k1, kante)) {
            for(Kreis k2 : w2.kreise) {
                if(k1.schneidet(k2)) {
                    zuEliminieren.add(groessereKreisVon(k1, k2)); }
            }
        } 
    }
    for(Kreis k : zuEliminieren) {
        if(w1.enthaelt(k)) {
            w1.entferne(k);  }
        if(w2.enthaelt(k)) {
            w2.entferne(k); }
    }    
  } // end Method eliminiereKante()

  
  Kreis groessereKreisVon(Kreis k1, Kreis k2) {
    if(k1.r > k2.r) {
        return k1; }
    else {
        return k2;  }
  }

  
  Kreis zufallsKreis(Wand w) {
    double min = Math.min(w.breite, w.hoehe);
    Kreis k = new Kreis();
    k.r = Math.random() * (min / 2);
    k.x = k.r + Math.random() * (w.breite - 2 * k.r);
    k.y = k.r + Math.random() * (w.hoehe  - 2 * k.r);
    //System.out.println("Kreis:"  + k);
    return k; }

} // end of class Maler
                

#Brute Force
import os
import math
import turtle

#Kreise einlesen
def lese_datei(name):
    kreise = []
    f = open(name, 'r')
    for line in f:
        l1 = line.split()
        k = l1[1]
        r = l1[2]
        k1 = k.rstrip(')')
        k2 = k1.lstrip('(')
        l2 = k2.split(',')
        x = float(l2[0])
        y = float(l2[1])
        r2 = r.lstrip('r=')
        r3 = float(r2)
        tmp = {'x':x,'y':y,'r':r3}
        kreise.append(tmp)
    return kreise

def zeichneKreis(x0,y0,r,n):
    winkel=360.0/n
    l = 2.0*r*math.sin(winkel/2.0*math.pi/180)
    # Vom Mittelpunkt zum Kreisrand ohne zu Zeichnen
    turtle.up()
    turtle.setpos(x0,y0)
    turtle.setheading(0)
    turtle.fd(r)
    turtle.setheading(90+winkel/2.0)
    turtle.down()
    # Kreis zeichnen
    for i in range(n):
        turtle.fd(l)
        turtle.left(winkel)
    # Zurueck zur Mitte    
    turtle.setheading(0)
    turtle.up()
    turtle.bk(r)
    turtle.down()

# überprüfen ob sich zwei Kreise schneiden
def schneidenKreise(kreis1,kreis2):
    global anzahlVergleiche # Globale Variable als Zähler
    # abstand im Quadrat: ((x1-x2)^2+(y1-y2)^2)
    dx = kreis1['x']-kreis2['x']
    dy = kreis1['y']-kreis2['y']
    abstand2 = dx*dx+dy*dy
    # r = (r1+r2)^2
    r2 = (kreis1['r']+kreis2['r'])*(kreis1['r']+kreis2['r'])    
    #Vergleiche zählen:
    anzahlVergleiche = anzahlVergleiche + 1
    if r2 < abstand2:
        return False  
    else:
        return True

def eliminiereKreise(kreise):
    neueKreise=[]
    while (len(kreise)>0):
        k1 = kreise.pop(0)
        # letzter Kreis in der Liste:
        flag = True
        i = 0
        while(i < len(kreise) and flag):
            k2 = kreise[i]
            if schneidenKreise(k1,k2):
                if k1['r']<k2['r']:
                    kreise.remove(k2)
                else:
                    flag = False
            else:
                i = i + 1
        if flag:
            neueKreise.append(k1)
    return neueKreise


# Grafik initialisieren
turtle.clear()
turtle.setpos(0,0)
turtle.pencolor("brown")
turtle.speed(10)
turtle.screensize(2000,1000)

kreise=lese_datei('kreise.txt')

anzahlVergleiche=0
zkreise=eliminiereKreise(kreise)
print 'Es wurden '+str(len(zkreise))+' Kreise gefunden.'
print 'Dazu wurden '+str(anzahlVergleiche)+' Kreise miteinander verglichen, ob sie sich schneiden'


# Kreise zeichnen
for kreis in zkreise:
    zeichneKreis(kreis['x']-1000,kreis['y']-500,kreis['r'],18)

                

# Mit Rekursion
import os
import math
import turtle

#Kreise einlesen
def lese_datei(name):
    kreise = []
    f = open(name, 'r')
    for line in f:
        l1 = line.split()
        k = l1[1]
        r = l1[2]
        k1 = k.rstrip(')')
        k2 = k1.lstrip('(')
        l2 = k2.split(',')
        x = float(l2[0])
        y = float(l2[1])
        r2 = r.lstrip('r=')
        r3 = float(r2)
        tmp = {'x':x,'y':y,'r':r3}
        kreise.append(tmp)
    return kreise

def zeichneKreis(x0,y0,r,n):
    winkel=360.0/n
    l = 2.0*r*math.sin(winkel/2.0*math.pi/180)
    # Vom Mittelpunkt zum Kreisrand ohne zu Zeichnen
    turtle.up()
    turtle.setpos(x0,y0)
    turtle.setheading(0)
    turtle.fd(r)
    turtle.setheading(90+winkel/2.0)
    turtle.down()
    # Kreis zeichnen
    for i in range(n):
        turtle.fd(l)
        turtle.left(winkel)
    # Zurueck zur Mitte    
    turtle.setheading(0)
    turtle.up()
    turtle.bk(r)
    turtle.down()

# überprüfen ob sich zwei Kreise schneiden
def schneidenKreise(kreis1,kreis2):
    global anzahlVergleiche # Globale Variable als Zähler
    # abstand im Quadrat: ((x1-x2)^2+(y1-y2)^2)
    dx = kreis1['x']-kreis2['x']
    dy = kreis1['y']-kreis2['y']
    abstand2 = dx*dx+dy*dy
    # r = (r1+r2)^2
    r2 = (kreis1['r']+kreis2['r'])*(kreis1['r']+kreis2['r'])    
    #Vergleiche zählen:
    anzahlVergleiche = anzahlVergleiche + 1
    if r2 < abstand2:
        return False  
    else:
        return True

def eliminiereKreise(kreise):
    neueKreise=[]
    while (len(kreise)>0):
        k1 = kreise.pop(0)
        # letzter Kreis in der Liste:
        flag = True
        i = 0
        while(i < len(kreise) and flag):
            k2 = kreise[i]
            if schneidenKreise(k1,k2):
                if k1['r']<k2['r']:
                    kreise.remove(k2)
                else:
                    flag = False
            else:
                i = i + 1
        if flag:
            neueKreise.append(k1)
    return neueKreise

def kreisSchneidetWand(kreis,kord,pos):
    if (pos < kreis[kord]+kreis['r']) and (pos>kreis[kord]-kreis['r']):
        return True
    else:
        return False   

def eliminiereAusZweiListen(k1,k2):
    i=0
    while(i < len(k1)):
        kreis1=k1[i]
        j=0
        while(j < len(k2)):
            kreis2=k2[j]
            if schneidenKreise(kreis1,kreis2):
                if kreis1['r']>kreis2['r']:
                    k1.remove(kreis1)
                    break
                else:
                    k2.remove(kreis2)
            else:
                j=j+1
        i=i+1
    
# Hier werden die Kreise von zwei Nachbarwänden zusammengefügt.
# Kreise die überschneiden werden eliminiert
def fuegeZusammen(w1,w2,kord,pos):
    kreise = w1.getKreise()
    kreise2 = w2.getKreise()
    # Alle Kreise aus w1 die schneiden
    kschneidet =[]
    i =0
    while(i < len(kreise)):
        kreis = kreise[i]
        if kreisSchneidetWand(kreis,kord,pos):
            kschneidet.append(kreis)
            kreise.remove(kreis)
        else:
            i =i+1
            
    # Alle Kreise aus w2 die schneiden
    kschneidet2=[]
    i =0
    while(i < len(kreise2)):
        kreis = kreise2[i]
        if kreisSchneidetWand(kreis,kord,pos):
            kschneidet2.append(kreis)
            kreise2.remove(kreis)
        else:
            i=i+1

    # Alle Kreise, welche schneiden mit anderer Region vergleichen
    eliminiereAusZweiListen(kschneidet,kreise2) 

    # Alle Kreise, welche schneiden mit anderer Region vergleichen
    eliminiereAusZweiListen(kschneidet2,kreise)

    # Die beiden Schnittmengen vergleichen
    eliminiereAusZweiListen(kschneidet2,kschneidet)

    #Die bereinigeten Listen zusammenfügen        
    kreise.extend(kreise2)
    kreise.extend(kschneidet)
    kreise.extend(kschneidet2)
    return kreise
 
# Die Klasse Wand kann sich teilen und die richtigen Kreis zuordnen
class Wand:
    def __init__(self,x0,y0,breite,hoehe,kreise):
        self.x0=x0
        self.y0=y0
        self.breite=breite
        self.hoehe=hoehe
        self.kreise=None
        #print self
        if (len(kreise) > 50):
            self.teileWand(kreise)
        else:
            self.kreise=eliminiereKreise(kreise)
    
    def __str__(self):
        return 'x:'+str(self.x0)+' y:'+str(self.y0)+' b:'+str(self.breite)+' h:'+str(self.hoehe)

    def getKreise(self):
        return self.kreise

    def teileWand(self,kreise):
        kreise1=[]
        kreise2=[]
        if self.hoehe > self.breite:
            hneu = self.hoehe/2
            w2y  = self.y0+hneu
            for kreis in kreise:
                if kreis['y']<w2y:
                    kreise1.append(kreis)
                else:
                    kreise2.append(kreis)
            #zeichneWand(self.x0,w2y,self.breite,0)        

            w1 = Wand(self.x0,self.y0,self.breite,hneu,kreise1)
            w2 = Wand(self.x0,w2y,self.breite,hneu,kreise2)
            self.kreise = fuegeZusammen(w1,w2,'y',w2y)
            
        else:
            bneu = self.breite/2
            w2x =self.x0+bneu
            for kreis in kreise:
                if kreis['x']<w2x:
                    kreise1.append(kreis)
                else:
                    kreise2.append(kreis)
            #zeichneWand(w2x,self.y0,self.hoehe,90) 

            w1 = Wand(self.x0,self.y0,bneu,self.hoehe,kreise1)
            w2 = Wand(w2x,self.y0,bneu,self.hoehe,kreise2)
            self.kreise = fuegeZusammen(w1,w2,'x',w2x)      


# Grafik initialisieren
turtle.clear()
turtle.setpos(0,0)
turtle.pencolor("brown")
turtle.speed(10)
turtle.screensize(2000,1000) 

kreise=lese_datei('kreise.txt')

anzahlVergleiche=0
m = Wand(0.0,0.0,2000.0,1000.0,kreise)
zkreise = m.getKreise()
print 'Es wurden '+str(len(zkreise))+' Kreise gefunden.'
print 'Dazu wurden '+str(anzahlVergleiche)+' Kreise miteinander verglichen, ob sie sich schneiden'

# Kreise zeichnen
for kreis in zkreise:
    zeichneKreis(kreis['x']-1000,kreis['y']-500,kreis['r'],18)
                

<!-- Dieses Beispiel läuft nur in Firefox ab 3.6, wegen dem File API -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "DTD/xhtml1-strict.dtd"> 
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="de" lang="de"> 
<head> 
    <meta http-equiv="Content-Type" content="text/html; CHARSET=UTF-8" /> 
    <title>Circle</title> 
    
	<script type="text/javascript">
	
	$ = function(id) { return document.getElementById(id); }

	function drawcircle(cxt,x0,y0,r){
		cxt.beginPath();
		cxt.arc(x0,y0,r,0,Math.PI*2,true);
		cxt.closePath();
		cxt.stroke();
	}	
     </script>
		
</head> 
<body> 
<input type="file" id="file4" name="file4" /> Kreise.txt 
<span class="readBytesButtons">
  <button>Daten Laden</button>
</span>
<br><br>
<div id="progress"></div>
<br>
<canvas id="myCanvas" width="2000" height="1000" style="border:1px solid #c3c3c3;">
Your browser does not support the canvas element.
</canvas>

<script type="text/javascript">
var c=document.getElementById("myCanvas");
var cxt=c.getContext("2d");

// Leeres Array mit Kreisen
kreise=new Array()

// überprüfen ob sich zwei Kreise schneiden
	function schneidenKreise(k1,k2){
		// abstand im Quadrat: ((x1-x2)^2+(y1-y2)^2)
		dx = k1['x']-k2['x']
		dy = k1['y']-k2['y']
		abstand2 = dx*dx+dy*dy
		// r = (r1+r2)^2
		r2 = (k1['r']+k2['r'])*(k1['r']+k2['r'])    
		if (r2 < abstand2){
			return false  
		}else{
			return true
		}
	}

	function eliminiereKreise(){
		var neueKreise= new Array()
		while(kreise.length>0){
			k1 = kreise.pop()
			flag = true
			var i = 0;
			a_getestet=false
			while(kreise.length>0&&!a_getestet){
				k2 = kreise.shift()
				if (schneidenKreise(k1,k2)){
					if (k1['r']<k2['r']){
						flag=true
					}else{
						kreise.push(k2)
						flag=false
						break
					}
				}else{
					kreise.push(k2)
				}
				i = i +1
				if (i >= kreise.length){
					a_getestet=true
				}
			}
			if (flag){
				neueKreise.push(k1)
				anz=neueKreise.length
				document.getElementById('progress').textContent = ['gefundene Kreise: ', anz].join('');
			}
		}
		// Alle Kreise kopieren
		while(kreise.length>0){
			k = kreise.pop()
			neueKreise.push(k)
		}
		return neueKreise
	}

// Einlesen der Kreise und Abspeichern im Array kreise    
	function parseData(s){
		lines=s.split('\n')
		for ( var i=0, len=lines.length; i<len; ++i ){
			line =lines[i]
			
			words = line.split(' ')
			koords = words[1].split(',')
			x = parseFloat(koords[0].substring(1,koords[0].length));
			y = parseFloat(koords[1].substring(0,koords[1].length-1));
			r = parseFloat(words[2].substring(2,words[2].length));
			
			var koord= new Object()
			koord["x"]=x;
			koord["y"]=y;
			koord["r"]=r;
			
			kreise.push(koord)	
		
		}

		zkreise=eliminiereKreise()

		//lösche Canvas
		cxt.clearRect (0, 0,  2000, 1000);

		// Zeichne Kreise
		while(zkreise.length>0){
			k = zkreise.pop()
			drawcircle(cxt,k['x'],k['y'],k['r'])	
		}

	}

	function readData(f) {
		var files = f;
		if (!files.length) {
			alert('Please select a file!');
			return;
		}
		var file = files[0];
		var reader = new FileReader();

		// If we use onloadend, we need to check the readyState.
		reader.onloadend = function(evt) {
			if (evt.target.readyState == FileReader.DONE) { // DONE == 2
				parseData(evt.target.result)
			}
		};
    
		reader.readAsBinaryString(file);
	}

// Start nach dem drücken des Knopfes Daten Laden
document.querySelector('.readBytesButtons').addEventListener('click', function(evt) {
    if (evt.target.tagName.toLowerCase() == 'button') {
      readData($('file4').files);
    }
  }, false);	
</script>

</body>
</html>
                

Lösung von: Martin Guggisberg (Universität Basel / PH FHNW)