Sortieren eines Polygons

[newnoise]

Hallo,

ich lese eine Datei ein, welche die Koordinaten eines Polygons beinhaltet. Leider stehen die Koordinaten nicht in der korrekten Reihenfolge in der Datei.
Gibt es eine Möglichkeit die Polygone zu sortieren? Also ein Algorithmus, der die Koordinaten so anordnet, dass sich keine Außenlinie des Polygons mehr schneidet. Da die Polygone konkav sind, ist es glaube ich nicht ganz trivial.

Kennt jemand nen bestehenden Algorithmus, oder kann man einen Denkanstoß geben?

Danke
noise

 

[Marco13]

Spontan klingt das irgendwie nach "im schlimmsten Fall muss man rumprobieren"...

 

[Ezra]

Wenn das Polygon konkav ist, ist es doch nicht mehr eindeutig aus den unsortierten Punkten wiederherstellbar. Du musst die Punkte schon sortiert speichern, sonst kannst Du nur raten, wie es aussehen soll.

 

[newnoise]

Müsste es nicht unter der Bedingung, dass sich hinterher keine Linie kreuzen darf doch eindeutig widerherstellen lassen? Würde wohl recht aufwendig, aber unmöglich ist es nicht?

noise

 

[Ezra]

Nein, eben nicht eindeutig.
Nimm Dir mal ein Blatt und mach ein paar Punkte drauf. Du wirst in den meisten Fällen mehrere Wege finden, diese zu verbinden, ohne dass sich die Linien kreuzen.

Sei es einfach, dass Du Eckpunkte eines Quadrates nimmst und in die Mitte noch einen Punkt setzt - von welchen Eckpunkten aus wird der mittlere nun verbunden?

 

[Marco13]

Eindeutig ist es (natürlich) nicht

      C   



A     B      D
|            |
|            |
|            |
|            |
|            |
X------------X

ABC oder CBD?

 

[newnoise]

Tatsache. Manchmal sollte man Dinge doch nicht nur versuchen zu denken. Malen hilft doch meist 🙂

Danke!

 

[newnoise]

soo.
Da ich die Polygone aus Kanten mit Start- und Endknoten zusammensetzen kann, funktioniert das mit dem sortieren doch. Leider aber noch nicht richtig 🙂
Mein Ergebnis sieht so aus (siehe Anhang).

Mein Code um die Kanten zu sortieren so:

   private List<OsmObject> sortMembers(List<OsmObject> unassigned,
	    Map<String, OsmWay> osmWays) {

	List<OsmWay> unassignedWays = new LinkedList<OsmWay>();
	List<OsmNode> unassignedNodes = new LinkedList<OsmNode>();
	List<OsmObject> assigned = new LinkedList<OsmObject>();
	int currentCount = 0;

	for (OsmObject object : unassigned) {
	    if (object instanceof OsmWay) {
		OsmWay newWay = (OsmWay) object;
		newWay.addNodes(osmWays.get(object.getId()).getNodes());
		unassignedWays.add(newWay);
	    } else {
		System.out.println("damn!");
	    }
	}

	OsmWay assi = null;
	                  
	try {
	    assigned.add(unassignedWays.get(0));
	    assi = (OsmWay) assigned.get(0);
	} catch (Exception e) {

	}

	for (int i = 0; i < unassignedWays.size(); i++) {
		if (!assigned.contains(unassignedWays.get(i))) {

		    if (unassignedWays.get(i).getNodes().get(0).getId().equals(assi.getNodes().get(assi.getNodes().size() - 1).getId())) {
			assigned.add(unassignedWays.get(i));
			assi = unassignedWays.get(i);
			i = -1;
		    } 
		    else if (unassignedWays.get(i).getNodes().get(unassignedWays.get(i).getNodes().size() - 1).getId().equals(assi.getNodes().get(assi.getNodes().size() - 1).getId())) {
			assigned.add(reverseWay(unassignedWays.get(i)));
			assi = unassignedWays.get(i);
			i = -1;
		    } 
		    
		}
	}
	
	System.out.println("assigned: " + assigned.size() + "\tunassigned: " + unassignedWays.size());

	return assigned;
    }

    private OsmObject reverseWay(OsmWay way) {
	List<OsmNode> rightNodes = new LinkedList<OsmNode>();

	for (OsmNode node : way.getNodes()) {
	    rightNodes.add(0, node);
	}

	way.setNodes(rightNodes);

	return way;
    }

Nodes gibt es in dem Fall nicht, daher ist die nicht Implementierung dessen nicht das Problem.

Übersehe ich was?

Danke!
noise