2D şekilleri bir dikdörtgene verimli bir şekilde yerleştirme. Nasıl yaklaşırsın?

Question

Yedi internette çok fazla araştırdım ve boşuna geldim. İhtiyacım olana en yakın olan The cutting stock problem, sadece 2D olarak görünüyor (Vikipedi, bunun nasıl çözüleceğine dair herhangi bir talimat vermediği için hayal kırıklığı yaratıyor). Bir başka benzerlik sorunu UV unwrapping olacaktır. Orada çözümler var, ancak sadece çeşitli 3 boyutlu yazılımlarda eklentilerden aldığınızlar var.

Uzun konuşmayı kısaltma - istediğimin şudur: bilinen bir genişlik ve yükseklik dikdörtgeni verildiğinde, bilinen boyutlardaki (çoktan ilerde döndürülebilen) kaç şeklin (çokgen) olduğunu öğrenmem gerekiyor bu dikdörtgenin içinde.

Örneğin, T-şeklinde bir parça seçebilir ve aynı dikdörtgen I dikdörtgen başına 4 şekiller ile sonuçlanan

tarafından ve de bunları döşeme, etkin bir şekilde, her iki paket olabilir onların sınırlayıcı kutuları dayanarak dava hangi sadece ...

Ama tabii 3

, bu sadece bir örnektir sığabilir ve bu konuda çözmek için çok kullanım olacağını sanmıyorum parti cular case. Şu an düşünebildiğim tek yaklaşımlar ya karmaşıklıklarında geri dönüş yapmak ya da sadece bu problemin özel durumlarını çözmek gibi. Yani ... herhangi bir fikir?

Answer 1

Tetris (probleminizin bir alt kümesi) oyunu olan var mı?

Bu, packing problem olarak bilinir. Zamanın önünde ne tür şekillerde karşılaşacağınızı bilmeden, size en iyi cevabı verecek bir algoritma bulmak imkansız değilse çok zor olabilir. Çokgenleriniz "güzel" çokgenler (çemberler, kareler, eşkenar üçgenler, vb.) Olmadıkça, büyük olasılıkla, çoğu zaman size en iyi çözümü veren bir sezgiye yerleşmeniz gerekecektir.

Bir genel sezgisel (giriş poligonunun şekline bağlı olarak en uygun olmaktan uzak olsa da), çokgenin etrafına bir dikdörtgen çizerek, dikdörtgenin poligonu örtecek kadar büyük olacağı şekilde sorunu basitleştirmek olacaktır. (Şemada Örnek olarak biz mavi poligon etrafında kırmızı dikdörtgen çizin aşağıda.)

biz yaptıktan sonra, biz o zaman bu dikdörtgeni alıp içine dikdörtgenin gibi birçok uyacak şekilde deneyebilirsiniz mümkün olduğunca büyük dikdörtgen. Bu, sorunu çözmek ve kafanızı sarmak için daha kolay olan bir dikdörtgen paketleme problemine basitleştirir. Bunun için bir algoritmanın bir örneği aşağıdaki bağlantıdadır:

An Effective Recursive Partitioning Approach for the Packing of Identical Rectangles in a Rectangle.

Açıkçası, bu çok yönlülük, söz konusu çokgen bir dikdörtgen ile aynı şekle yakın olmadığında en uygun değil, özellikle, ne hakkında çok fazla bilginiz yoksa, çalışmak için minimum bir temel verir. poligonunuz gibi görünecek (veya poligonun neye benzeyeceği konusunda yüksek bir varyans var).Bu algoritma kullanılarak, çok gibi büyük dikdörtgen doldurmak:

Bu T-şekilli bir durum için ortalama:

ara dikdörtgenler olmadan aynı görüntüdür çokgenler, sezgisel olabileceği en iyi şey değildir (aslında bu önerilen yaklaşım için neredeyse en kötü durum senaryosu olabilir), ancak diğer çokgen türleri için çok iyi çalışır.

Answer 2

Diğer cevaplar t'nin bir kareye yerleştirilmesiyle söylenenleri düşünün, ancak bir kare olarak bırakmak yerine, şekilleri bir listede ayarlayın. Daha sonra iç içe geçmiş listeyi şekil olarak, yani T şekliniz için [[Doğru, Doğru, Doğru], [Yanlış, Doğru, Yanlış]] olarak doldurmak için Doğru ve Yanlış'ı kullanın. Daha sonra şekilleri ızgaraya yerleştirmek için bir işlev kullanın. Sonuçları optimize etmek için, yeni şekillerde kaç tane yanlışın, önceki şekillerde ızgarada bulunan truva'larla çakıştığına dikkat edecek bir izleyici oluşturun. Bu işlev şekli en fazla çakışan yere yerleştirir. Daha yüksek ve daha yüksek optimizasyonlar oluşturmak için modifikasyonlar olmalı, ama bu sizin aradığınız genel dayanaktır.