Finde das maximale Flächenpolygon, das in ein größeres Polygon eingeschrieben ist
Ich möchte die Rotation und den Ort für ein Polygon finden, das maximiert, wie groß es innerhalb der Einschränkungen der Anpassung innerhalb eines größeren Polygons vergrößert werden kann.
Gegenwärtige Idee ist, scipy Optimierungsroutinen zu verwenden, um Positions- und Rotationsparameter zu optimieren, um das Maximum zu maximieren Skalierungsparameter und formschön , um eine Abhängigkeit hinzuzufügen, die das Polygon enthält. Dies scheint, als wäre es langsam und nicht besonders elegant.
Andere Ideen?
2 Antworten
Dieses Problem klingt nach NP-Hard. Angesichts einer Kandidatenlösung kann man nicht wirklich sicher sein, dass es die beste Lösung ist. Es scheint, als müssten Sie versuchen, eine inkrementelle randomisierte Suche zu verwenden.
Wenn das interne Polygon maximal skaliert ist, dann gibt es mindestens 4 Paare "interne Ecke - externe Kante" oder "externe Ecke - interne Kante", wo die Ecke an der Kante ist.
Nehmen wir alle 4s der Ecken-Kanten-Paare. Für jeden berechnen wir das System der linearen Gleichungen für die Koordinaten der beiden Bezugspunkte. Wenn es eine Lösung gibt, überprüfen wir, dass es keine Überschneidungen gibt, und wenn OK, erinnern wir uns an die Koordinaten und die Größe des internen Polygons.
Das ist eine exakte Lösung, aber es ist langsam. Auf der anderen Seite finden scipy Optimierungsroutinen wahrscheinlich ein lokales Maximum, das nicht das globale ist.