# Punkte sortieren



## minimds (13. Aug 2007)

Hallo

habe ein Problem. Ich lese aus einer Datei Punkt koordinaten und will daraus ein Fläche generieren. Ich arbeite mit einem Canvas Objekt mit der Methode fillPolygon der ich ein xkoordinaten- und ykoordinatenArray (rechne dazu 3D-Punkte in 2D-Koordinaten um)übergeben muss. Damit diese Koordinaten zu einer ganz ausgefüllten Fläche werden müssen diese in Reihenfolge in das Array geschrieben werden(bei 4Eck z.B links oben, rechts oben, rechts unten, links unten). Mein Problem ist es dafür einen Algorithmus zu finden, der auch mit Flächen mit beliebig vielen Ecken zurechtkommt. 

```
public Vector<Point3d> punkteSortieren(Vector<Point3d> punkte){                
                Point3d[] temp=new Point3d[2];
		Vector<Point3d> erg = new Vector<Point3d>();
                //zuerst oberste finden
		temp[0]=punkte.get(0);
		temp[1]=punkte.get(1);
		for(int i=2;i<punkte.size();i++){
			if(punkte.get(i).y>temp[0].y){
				if(temp[0].y>temp[1].y)temp[1]=temp[0];
				temp[0]=punkte.get(i);
			}
			else if(punkte.get(i).y>temp[1].y)temp[1]=punkte.get(i);
		}
		//den linken davon zuerst adden
		if(temp[0].x<temp[1].x){
			erg.add(temp[0]);
			erg.add(temp[1]);
		}
		else{
			erg.add(temp[1]);
			erg.add(temp[0]);
		}
		punkte.remove(temp[0]);
		punkte.remove(temp[1]);
		
		//unterste Punkte finden
		temp[0]=punkte.get(0);
		temp[1]=punkte.get(1);
		for(int i=2;i<punkte.size();i++){
			if(punkte.get(i).y<temp[0].y){
				if(temp[0].y<temp[1].y)temp[1]=temp[0];
				temp[0]=punkte.get(i);
			}
			else if(punkte.get(i).y<temp[1].y)temp[1]=punkte.get(i);
		}
		
		//den rechten davon zuerst adden
		if(temp[0].x>temp[1].x){
			erg.add(temp[0]);
			erg.add(temp[1]);
		}
		else{
			erg.add(temp[1]);
			erg.add(temp[0]);
		}
		punkte.remove(temp[0]);
		punkte.remove(temp[1]);
		
		boolean links = false;
		//evtl 5. Punkt einsortieren
		while(punkte.size()!=0 && erg.size()==4){
			Point3d temp2=punkte.remove(0);
			if(temp2.x>=erg.get(1).x || temp2.x>=erg.get(2).x){
				erg.insertElementAt(temp2, 2);
			}
			else if(temp2.x<=erg.get(3).x || temp2.x<=erg.get(0).x){
				erg.insertElementAt(temp2, 0);
				links = true;
			}
			else System.out.println("Erg:\n"+erg+"\nPunkt:\n"+temp2);
		}
		
		//evtl 6. Punkt einsortieren
		while(punkte.size()!=0 && erg.size()==5){
			Point3d temp2=punkte.remove(0);
			if(links){
				erg.insertElementAt(temp2, 3);
			}
			else{
				erg.insertElementAt(temp2, 0);
			}
		}
		return erg;
}
```

Das wäre, was ich bisher zustande gebracht habe. Habe gedacht, dass mehr wie sechs Ecken nicht vorkommen. Dies ist aber doch der Fall. Außerdem gibts bestimmte Fälle in denen dieser Algo falsch sortiert.

Kann mir jemand helfen?


----------



## Marco13 (13. Aug 2007)

Du meintest, die Punkte müssen "in Reihenfolge" in das Array geshrieben werden. Nun. Versuch' doch mal das Gegenteil. (Ohne Reihenfolge?). Also, in WELCHER Reihenfolge müssen die Punkte dort rein? Es gibt da meistens mehrere Möglichkeiten.... 

Vielleicht hilft dir das hier weiter:
http://de.wikipedia.org/wiki/Graham_Scan

Wenn nicht, sag mal, welche Reihenfolge du dir vorstellst...


----------



## SlaterB (13. Aug 2007)

nenne doch mal ein Beispiel, was nicht funktioniert,
da kannst du gleich dazu sagen, wie es richtig sortiert aussehen soll,
und was das Kriterium dafür ist,


und was ist mit deinem Code, willst du den noch erklären,
oder soll der nur als Anschauung dienen, 'macht es bloß nicht so!'?


----------



## Guest (13. Aug 2007)

Das FünfEck in der Mitte hat es falsch sortiert. Es müssen halt immer zwei "nebenainander" liegende Punkte auch im Array nacheinander folgen. Und Ja ist vielleicht nicht der eleganteste Code. Mache sowas zum ersten mal.


----------



## jPat (13. Aug 2007)

Du solltes in der Klasse Punkt ein Kriterium setzen, zb: Comparable impementieren,  Methode: int 	compareTo(Punkt o). dann soltest du dir Klar machen wie herum du deine Fläche zeichnen willst (Im Uhrzeigersinn oder Entgegengesetzt?) nun soltest du nur noch wissen, welcher Punkt kleiner (also zuerst gezeichnet) als ein anderer ist, und deinen Vector so Erweitern, dass du Ihn sortieren kannst, das wird ein wenig übersichtlicher ... 

Sortierkriterium : Wer ist der weitere von Ursprung deines Koordinatensystem -> du bist größer als alle anderen ....


----------



## jPat (13. Aug 2007)

Meiner meinung nach kann es Mathematisch gesehen für dein Problem keine lösung geben, da wenn du im 3d Raum bist, max 4 punkte eine eindeutig geschloßene Fläche definieren.


----------



## jPat (13. Aug 2007)

Punkte:

*  *
  *      in der Mitte
*  *

Gezeichnet

---
\  |
/  |
---
oder
----
|   /
|   \
----

es gibt ja noch mehr möglichkeiten !!

Welches Muster möchtest du haben??

beachte -> dies ist 2d !!


----------



## minimds (13. Aug 2007)

Aber das Kriterium weiter weg vom Ursprung funktioniert doch auch nicht immer, da es ja durchaus Punkte geben kann, die den gleichen Abstand vom Ursprung(liegt) haben, aber an einem ganz anderen Ende der Fläche liegen, oder nicht?

Und wenn das nicht so sein sollte, wie komm ich dann von diesem Kriterium zu einer Sortierung im Uhrzeigersinn?


----------



## Marco13 (13. Aug 2007)

Er ist im 2D-Raum. Und ein Sortierkriterium, das auf dem Anstand vom Ursprung basiert, kann imho nicht funktionieren. Es gibt im 2D schon bei 5 Punkten mindestens 4 verschiedene Möglichkeiten:

```
X       X
 |\     /|
 | \   / |
 |  \ /  |
 |   X   |
 |       | 
 |       | 
 X-------X
```
(das ganze eben 3 x um 90° gedreht) (nur als Beispiel). Und die äußeren Punkte haben alle den gleichen Abstand vom Ursprung (in der Mitte)


----------



## Guest (13. Aug 2007)

***
| /
|\
***

Also so etwas kann es nicht geben

***
|    \
|    /
***

  ***
/      \
\      /
  ***

Sondern nur solche Flächen


----------



## Marco13 (13. Aug 2007)

Da war ich zu langsam. "Im Uhrzeigersinn" funktioniert aber auch nicht...


----------



## jPat (13. Aug 2007)

gleicher abstand bedeutet ja, dass sie auf einem Kreis um den Uhrsprung liegen. Wie gesagt, ist nur mal ein den denkansatz für ein Kriterium. Meiner meinung nach ist das ein sehr komplexes thema, und das wirst du so nicht hinbekommen. Wenn doch, Gratulation


----------



## minimds (13. Aug 2007)

Denn ich habe ursprünglich nur 4 Ecke die ich mit mit einer Ebene schneide


****/*
*  /   *
*/     *
/*****

Also so etwas zum Beispiel

wobei die Schnittlinie halt auch nach rechts oder links verschoben sein kann


----------



## Marco13 (13. Aug 2007)

Man kann wohl leicht "irgendwas" hinbekommen - die Frage ist, ob man das haben will, was dann da rauskommt. Ich denke, das Hauptproblem ist, dass es nie eindeutig lösbar sein wird, sondern immer nur irgendeine von vielen möglichen Lösungen rauskommt. Solange man nicht genau sagt (und formalisiert) welches Ergebnis man denn haben will...

Aber in bezug auf den letzten Beitrag: Bei so einfachen Fällen tut's schon das Uhrzeigersinn-Kriterium. Die Dinger sind ja immer konvex


----------



## jPat (13. Aug 2007)

Wenn man nur 4 Punkte hat, kann man auch nur 4 punkte zeichnen. evtl mußt du das über die Vectorechnung machen.
00 -> p1 -> p2 -> p3 -> .. -> pn dann projezieren auf 2d nach einer Projektionsformel ... die Sortierung der Punkte sollte erhalten bleiben. oder ??


----------



## minimds (13. Aug 2007)

Das Programm soll ein Flächenrückführungs programm für messpunkte werden. Ich les also aus einer Datei punktkoordinaten ein lege über diese punkte ein 4Eck Raster(funzt schon). bei diesen punkten sollte der z-Wert zwischen einer oberen und einer unteren toleranz liegen. ist dies nicht der fall dann versuch ich das betreffende viereck mit dieser Toleranzebene zu schneiden(funktioniert auch) und die Flächen dann je nachdem einzufärben. 

Ich habe also eine ausgangsfläche(bei der die punkte auch schon im Uhrzeigersinn sortiert sind) bekomme zwei schnittpunkte mit der Toleranzebene ertstelle mir zwei neue flächen. Das Problem ist jetzt bei diesen neuen flächen die Punkte im uhrzeigersinn einzusortieren.

Wenn man das nicht allgemein lösen kann dann versuch ich halt so viele Fälle wie möglich hinzupfuschen.


----------



## Marco13 (13. Aug 2007)

Wie gesagt: Das ist vermutlich nicht so schwer. Die entstehenden Flächen sind konvex, d.h. man die Punkte im Uhrzeigersinn sortieren, und damit sollte es dann stimmen.


----------



## jPat (13. Aug 2007)

Wenn ich das richtig versteh:
4 punkte ergeben eine Fläche
dann eine Ebene, die diese fläche schneidet, aber nicht unbedingt in der mitte dwer 4Punkte Fläche?

du solltest nun die Schnittgerade herausfinden, dann diese gerade als ausgangspunkt deiner berechnungen nehmen.

Kriterium könnte sein :

 alle Punkte die links von der Geraden liegen, gehöhren zusammen, alle punkte die Rechts von der Geraden liegen gehöhren auch zusammen.  
Ich glaub es gibt da so eine Formel, mit der du herausfinden kannst, ob ein punkt "links" oder "rechts" von einer geraden liegt.


----------



## minimds (13. Aug 2007)

Im Prinzip hast du recht der Extremfall wäre die Fläche schneidet die Toleranzebene in nur einem Punkt, dann berührt sie diese Ebene nur


----------



## minimds (13. Aug 2007)

@Marco13
"..d.h. man die Punkte im Uhrzeigersinn sortieren, und damit sollte es dann stimmen."

das ist ja gerade das Problem das ich versuche zu lösen


----------



## minimds (13. Aug 2007)

OK habe das Problem jetzt selber gelöst, indem ich die punkte gleich beim schneiden in zwei verschiedene vectoren speichere. wenn interesse besteht kann ich die funktion ja posten

p.s.:kann ich als gast dieses Thema als abgeschlossen markieren oder nicht?


----------



## jPat (14. Aug 2007)

nein


----------

