Hallo Frederik, ein schönes Optimierungsproblem (abgesehen vom Vergröbern bei den übergeordneten Grenzen). Ich versuchs erstmal ohne die "übergeordnete Grenze" mit verschiedenen iterativen Ansätzen[1], mal sehen, was am besten konvergiert.
Also, Problem: Die Punktanzahl des umschreibenden Polynoms bei bestmöglicher Anpassung an das Ursprungs-Polynom minimieren. Als Indikator für "Güte" nehme ich die Relation: 1 - Flächendifferenz beider Polynome / Originalfläche denk ich mal. Bei 1=100% hat man exakte Übereinstimmung, alles andere liegt unterhalb oder wird sogar negativ. Es gibt dann wohl einen Parameter, der geschmacks- oder situationsabhängig ist, ich nehme an, das ist genau diese Güte. Dann mach ich wohl am besten ein grafisches Programm mit Güte-Schieberegler, in das man Polygone einlesen[2] und gucken kann, wie die verschiedenen Güten im Zoom aussehen. Dann hast Du irgendwann den richtigen Kompromiß gefunden, der dann wohl für alle anderen Polygone auch so verwendet werden kann. Das einzige was jetzt zu fragen bleibt, ist: Was mache ich mit Mehrfach-Polygonen wie z.B. Faröer? Wenn man das in ein Polygon zusammenfaßt, was macht man dann z.B. mit Frankreich+Martinique+Korsika? Vielleicht darf das Polygon ja nur eine Grenze überschreiten, das wäre eine Möglichkeit. Dann wäre Korsika auf der Frankreich-Karte, aber nicht Martinique. Ich erstelle das für Linux und Windows, Mac hab ich nicht greifbar. Jochen On Vie 05 Feb 2010, Frederik Ramm wrote: > 6. Vereinfache das Polygon so, dass es maximal 500 Punkte hat und dass > die vereinfachte Version vollstaendig ausserhalb der Originalversion > liegt. Verwende diejenige aller moeglichen Vereinfachungen, die am > ehesten an der Originalflaeche liegt. Ausnahme: Dort, wo die Umrandung > des Polygons entweder eine Kuestenlinie ist oder mit der Umrandung des > hierarchisch darueberliegenden Polygons zusammenfaellt (also z.B. dort, > wo NRW an Belgien grenzt und die NRW-Grenze daher mit der D-Grenze > zusammenfaellt), darf das Grenzpolygon grosszuegig vereinfacht sein. [1] Newtonsches Gradientenverfahren, Simulated Annealing und "Threshold Accepting" fallen mir da spontan ein. [2] OSM XML, ASCII-Koordinatenzeilen mit Leerzeile für Polygon-Ende, oder GPX als Eingabeformat _______________________________________________ Talk-de mailing list [email protected] http://lists.openstreetmap.org/listinfo/talk-de
