Punkte sortieren

Status
Nicht offen für weitere Antworten.
M

minimds

Gast
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.
Code:
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

Top Contributor
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...
 
S

SlaterB

Gast
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!'? ;)
 
G

Guest

Gast
thumbnail


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

Bekanntes Mitglied
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

Bekanntes Mitglied
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

Bekanntes Mitglied
Punkte:

* *
* in der Mitte
* *

Gezeichnet

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

es gibt ja noch mehr möglichkeiten !!

Welches Muster möchtest du haben??

beachte -> dies ist 2d !! :D
 
M

minimds

Gast
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

Top Contributor
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:
Code:
 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)
 
G

Guest

Gast
***
| /
|\
***

Also so etwas kann es nicht geben

***
| \
| /
***

***
/ \
\ /
***

Sondern nur solche Flächen
 

jPat

Bekanntes Mitglied
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 :)
 
M

minimds

Gast
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

Top Contributor
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

Bekanntes Mitglied
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 ??
 
M

minimds

Gast
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

Top Contributor
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

Bekanntes Mitglied
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.
 
M

minimds

Gast
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
 
M

minimds

Gast
@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
 
M

minimds

Gast
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?
 
Status
Nicht offen für weitere Antworten.

Ähnliche Java Themen


Oben