Finden Sie maximale Fläche Polygon in größeren Polygon eingeschrieben

Question

Ich möchte die Rotation und die Position für ein Polygon, das maximiert, wie groß es innerhalb der Einschränkungen der Anpassung in einem größeren Polygon skaliert werden kann.

Aktuelle Idee ist scipy optimization routines zur Optimierung der Position und Rotationsparametern zu verwenden, um den Skalierungsparameter zu maximieren und shapely eine Einschränkung hinzuzufügen, die das Polygon enthalten ist. Dies scheint, als wäre es langsam und nicht besonders elegant.

Andere Ideen?

Answer 1

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.

Answer 2

Wenn die interne Polygon maximal skaliert wird, dann gibt es mindestens 4 Paare „internal vertice - Außenkante“ oder „externe vertice - internal edge“, wo die vertice am Rande ist.

Nehmen wir alle 4s der Vertice- Kantenpaare. Für jeden berechnen wir das System der linearen Gleichungen für die Koordinaten der beiden Bezugspunkte. Wenn es eine Lösung gibt, verifizieren wir, dass es keine Schnittpunkte gibt, und wenn OK, erinnern wir uns an die Koordinaten und die Größe des internen Polygons.

Dies ist eine genaue Lösung, aber es ist langsam. Auf der anderen Seite finden scipy Optimierungsroutinen wahrscheinlich ein lokales Maximum, das nicht das globale ist.