Kreiskontur durch Rechtecke abdecken
-
Hallo Forum!
Ich hätte - mal wieder - eine Frage im Zusammenhang mit Rechtecken.
Gegeben sei im 2-dimensionalen Raum in einem kartesischen X,Y-Koordinatensystem ein Kreis mit dem Mittelpunkt x_k, y_k und dem Radius r.
Die Aufgabe besteht nun darin, die Kontur des Kreises mit den Koordinaten
x=r*cos(phi)+x_k ; y=r*sin(phi)+y_k
vollständig mit einer Anzahl von Rechtecken abzudecken.
Jedes Rechteck ist achsenparallel und hat die Breite b und die Hoehe h.
Dabei müssen sich zwei Rechtecke immer um mindestens U überlappen, und zwar ENTWEDER in X- oder in Y-Richtung.
Die Mittelpunkte der Rechtecke können auf der Kreiskontur liegen, müssen dies aber nicht.
Hat jemand eine Idee zur Anordnung der Rechtecke?
Vielen Dank im Voraus fuer alle Beitraege.
-
Gibts da noch ein Optimalitätskriterium? Sonst ist die Aufgabe trivial mit Rechtecken von (x_k - r, y_k - r ) bis (x_k + r, y_k + r ) zu lösen.
P.S.: Gibts 'nen tieferen Grund, den Text so zu zerhacken?
Bye, TGGC (Dem beste BdT)
-
Optimal ist eine möglichst geringe Überlappung, die aber mindestens gleich U ist, d.h. möglicht wenige Rechtecke.
-
Das Rechteck (x_k - r, y_k - r ) bis (x_k + r, y_k + r ) ist eine optimale Lösung.
Bye, TGGC (Dem beste BdT)
-
Korrekt, aber jedes Rechteck soll ja eine Breite b und eine Höhe h haben. Die vorgeschlagene Lösung ist nur dann möglich, wenn b und h größer als 2*r sind.
-
Dann setze b=h= 2r.
Bye, TGGC (Dem beste BdT)
-
Kleines Missverständnis: b und h sind vorgegeben und i.A. kleiner als r.
-
Ok, man kann also nur die Positionen der Rechtecke wählen kann.
Erstmal sollten die Rechtecke möglichst nah am Mittelpunkt des Kreises liegen, also mit der Außenseite den Kreis berühren. Hat man eine gültige Konfiguration, wo das nicht so ist, so kann man die Rechtecke alle nach innen schieben, wobei die Überlappung höchstens größer wird. D.h. existiert eine optimale Lösung, bei der nicht alle Rechtecke ganz innen liegen, existiert auch eine korrespondierende optimale Lösung, bei der dies so ist.
Meine Idee wäre nun mit einem solchen Rechteck zu beginnen und dies dann am Kreis "herumzuschieben", bis die Überlappung gerade noch ausreicht (also das Minimum erreicht). Beim "Herumschieben" beginnt man z.b. indem man den oberen linken Punkt des Rechtecks, auf den höchstens Punkt des Kreises legt. Nun lässt man diesen Eckpunkt auf den Kreis im Uhrzeigersinn wandern, bis der gegenüberliegenden Eckpunkt außerhalb des Kreises liegt. Ab dem Moment legst man diesen Eckpunkt auf den Kreis und läufst weiter bis zum rechten Punkt im Kreis (quasi 3 Uhr). Jetzt wird das Rechteck noch um h heruntergeschoben. Die weiteren Viertel werden analog abgehandelt.
Bleibt nur noch die Frage, mit welchem Rechteck begonnen werden soll.
Bye, TGGC (Dem beste BdT)
