Finden gemeinsamer Kanten: welche Datenstruktur ?

[blablaman]

Hallo,

ich habe hier eine Menge von zusammenhängenden Polygonen, wobei jedes Polygon aus einer Menge von Punkten besteht. Ich bin dabei, eine Klasse z uschreiben, die gemeinsame Kanten findet.

Ich habe mir Folgendes überlegt:
//Algorithmus
//1. beliebiges Startpolygon aus einer Startliste(ArrayList) von Polygonen auswählen, dessen Punkte in eine Liste(LinkedHashSet) einlesen
//2. Schnitt mit der Punktemenge des nächsten Polygons aus der Startlist bilden; falls nicht, das nächste Polygon aus der Startlist in einer zweiten Liste(unhandledPolygons) abspeichern
//3. Schnittemenge als PolygonPair(PolygonId, Point[]) abspeichern
//4. Differenzmengen vereinigen zu einem Polygonzug / einer Menge(LinkedHashSet), der dann den Umriss darstellt
//5. Diese Menge erneut als Startpolygon wählen und wieder bei 1. anfangen
//Wiederholung bis alle Polygone(Bsp.: List unhandledPolygon ist
//leer) betrachtet wurden

Ich möchte gern wissen, wie man das mit dem Abspeichern der Polygonen, die nicht benachbart sind mit dem aktuellen Polygon, am besten lösen kann.

Über Tipps würde ich mich freuen.


Grüße


blablaman

 

[function]

Wenn ich, das richtig verstanden habe sind in der Startliste doch alle Polygone gespeichert oder? Sagen wir mal du nimmst das 1. Polygon als Startpolygon und vergleichst es direkt mit dem Zweitem
-> Sie sind "benachbarte" Polygone zusammenfügen an Stelle 1 speichern, 2. Polygon aus der Liste löschen
-> Sie sind nicht "benachbart", erstes Polygon mit dem 3. vergleichen ggf. zusammenfügen und 3. löschen.
So sind alle Polygone vorhanden und beim zusammensetzen wird die Liste um 1 verringert.

Allerdings sehe ich evtl ein paar Probleme:
1. Sind wirklich alle Polygone der Liste zusammenhängend, also kann man aus allen Polygonen am Ende wirklich 1 "großes" Polygon bilden.
2. Was ist wenn 2 Polygone zwar zusammenhängen allerdings nicht über eine ganze Kantenlänge? Dann hänge sie zwar zusammen, aber können nicht durch einfaches entfernen einer Kante zusammengefügt werden...

 

[blablaman]

Hallo,

vielen Dank für deine Antwort.
Ich habe für die Liste LinkedList, die eigentlich die Operationen addFirst, removeFirst bereitstellt.
Ich kann die Methoden nicht aufrufen bzw, die sind nicht sichtbar. Ich benutzer Eclipse 3.5.1 und als JDK Compliance 1.4. Vllt kannst du mir da weiterhelfen.

Grüße


blablaman

 

[function]

also die Methoden sind aufjedenfall verfügbar. Java 2 Platform SE v1.4.2.
Du musst nur java.util.* bzw java.util.LinkedList importieren. Aber was heißt denn genau sind nicht sichtbar? Sagt Eclipse, dass die Methoden nicht existieren, oder bekommst du "nur" keinen Tooltip dafür?

 

[blablaman]

Hat sich erledigt.

Nun habe ich eine Endlosschleife im Code und blicke gerade nicht durch.

while( polygonsList.size() != 1 ){			
			//nächstes Polygon aus Liste holen
			nextPolygon = (Polygon) polygonsList.pop();
			
			//Punkt des Polygon herauslesen und abspeichern
			nextPolygonPoints = new LinkedHashSet( Arrays.asList( nextPolygon.getVertices() ) );
			
			//Schnittmenge mit Startpolygon bilden
			if( startPoints.retainAll(nextPolygonPoints) ){
				//Startpolygon und das als Nächstes zu betrachtenes Polygon sind benachbart
				intersectionPoints = startPoints;
				System.out.println("insectionPoints array length: " + intersectionPoints.size());
				//gemeinsame Kante als PolygonPair-Objekt speichern
				//TODO: PolygonId ???
				Point[] points = (Point[]) intersectionPoints.toArray( new Point[ intersectionPoints.size() ] );
				System.out.println("points array length: " + points.length);
				polyPair = 
					new PolygonPair( "id", 
									(Point[]) intersectionPoints.toArray( new Point[ intersectionPoints.size() ] ) );
				polyPairs.add(polyPair);
				
				//Startpolygon wieder neu definieren aus Vereinigung 
				//der Differenzmengen
				// A = {startPoints} / {currentPolygonPoints} 
				// B = {currentPolygonPoints} / {startPoints}  
				// A union B
				perimeterPoints.removeAll(nextPolygonPoints);
				nextPolygonPoints.removeAll(help);
				perimeterPoints.addAll(nextPolygonPoints);
				startPoints = perimeterPoints;
				
				points = (Point[]) perimeterPoints.toArray( new Point[ perimeterPoints.size() ] );
				Polygon newStartPolygon = new Polygon(points);
				polygonsList.addFirst(newStartPolygon);
			}else{
				System.out.println("insectionPoints array length: " + startPoints.size());
				//Startpolygon und das als Nächstes zu betrachtenes Polygon 
				//sind nicht benachbart: zu betrachtendes Polygon in einer Liste speichern
				polygonsList.addLast(nextPolygon);
			}			
			
		}

 

[Schumi]

Also was mir beim kurzen Übschauen nur auffällt, Du popst einmal etwas runter und sowohl im if als auch im else setzt Du wieder was in die Liste, dabei kann die doch nicht kleiner werden?

 

[Landei]

Ich hab nicht genau drübergeguckt, aber meistens läuft es bei solchen Endlosschleifen darauf hinaus, sich ein "HattenWirSchon"-Set anzulegen, wo alle abgehakten Kanten oder was auch immer reingepackt und beim nächsten mal entsprechend ignoriert werden.

 

[blablaman]

Erstmal danke für die Tipps. Ich habe nun keine Endlosschleife mehr.
Aber meine Schleife funktioniert trotzdem noch nicht richtig.
Und zwar habe ich eine Liste mit Polygonen, die ein zusammenhängendes Gebiet bilden.

Ich nehme das erste als Startpolygon, und nehme mir das zweite in der Liste und gucke ob sie benachbart sind, wenn nicht muss ich zum dritten, wenn nicht wieder zum vierten usw. Das Problem ist, wie komme ich dann wieder zurück zum zweiten und zum dritten Polygon, wenn ich das nächste benachbarte Polygon erst an Stelle n finde. Weil es kann ja sein, dass das n-te Polygon benachbart ist mit dem zweiten und dem dritten. Über Tipps würde ich mich freuen.

Grüße


blablaman

 

[blablaman]

Hallo,

ich würde gern fragen, ob ihr ein Paar Links oder Literaturhinweise für mich zum Thema "gemeinsame Kanten finden" hat.
Google habe ich auch schon besucht, vllt habt ihr ja ein Paar Links, die ich noch nciht kenne.

Grüße


blablaman

 

[newnoise]

Hallo,

das Thema ist zwar schon älter, aber sitze quasi vor dem gleichen Problem. Hast Du mittlerweile eine Lösung gefunden? Falls ja, magst Du mir mal deine Klasse zeigen?
Das wäre super!

Danke
noise