Verilen iki çokgenler:

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

Nasıl Birliği (kombine çokgen) hesaplayabilir miyim?

Dave's example SQL server birlik üretmek için kullanır, ama kodda aynı şeyi başarmak istiyorum. Gerçek matematik ortaya çıkaran herhangi bir dilde matematiksel formül veya kod örneği arıyorum. Ülkelerin dinamik bölgeleri birleştirmek haritalar üretmek için çalışıyorum. Ben ilgili bir soru sordu: http://stackoverflow.com/questions/2653812/grouping-geographical-shapes

Bu çok iyi bir soru. C aynı algoritmayı hayata# bir süre önce. Algoritma iki çokgen (delik olmadan bir birlik yani Yapıları) ortak bir kontur oluşturur. İşte burada.

Adım 1. Çokgenler açıklayan bir grafik oluşturun.

Giriş: çokgen (n puan), ikinci çokgen ilk (m puan). Çıkış: grafik. Köşe kesişme noktası poligon noktası.

Kavşak bulmalıyız. Hem çokgenler çokgen tüm tarafların, O (*m n)] arasında yineleme ve herhangi bir kavşak bulmak.

• Eğer bir kavşak bulunursa değil, sadece tepe noktaları eklemek ve onları bağlayın kenarına.

• Eğer herhangi bir kavşak bulunursa, bunların başlangıç noktasına uzunluğu göre sıralamak, eklemek tepe (başlangıç, bitiş ve kesişme noktaları) ve onları (zaten bağlanın sipariş sırasına göre) kenarına.

Adım 2. Grafik inşa kontrol edin

Eğer herhangi bir kesişme grafik inşa edildiğinde noktaları bulduk değilse, aşağıdaki koşullardan biri var:

1. Polygon1 polygon2 - dönüş polygon1 içerir
2. Polygon2 polygon1 - dönüş polygon2 içerir
3. Polygon1 ve polygon2 değil bilgisayar. Dönüş polygon1 VE polygon2.

Adım 3. -Sol alt köşe bulmak.

X ve y en az koordinatları () minx, miny bulabilirsiniz. Bulmak arasındaki minimum mesafe () minx, miny ve poligon noktaları. Bu nokta sol alt noktası olacaktır.

Adım 4. Ortak kontur oluşturmak.

Biz geçiş için sol alt noktasından grafiğin başlangıç ve biz geri dönene kadar devam eder. Başında edilmemiş gibi tüm kenarlarını işaretliyoruz. Her tekrarında bir sonraki nokta seçip de Ziyaret işaretlemeniz gerekir.

Bir sonraki nokta seçmek için, saat yönünün tersi yönde maksimum bir iç açısı ile bir kenar seçin.

Ben iki vektörün hesaplanması: her bir sonraki edilmemiş edge mevcut edge ve vector2 resim gösterildiği gibi) vector1.

Ben hesaplamak vektörler:

1. Skaler çarpımı (dot product). Bir değeri vektör arasındaki bir açı ile döndürür.
2. Vektörel çarpım (cross product). Yeni bir vektör verir. Z-koordinatı bu ise vektör ürün dik açı olarak bana verir olumlu, katı saat yönünün tersine yönü. Başka (z-koordinatı negatif olur), hesaplamak 360 derecelik açıdan skaler olarak vektör arasındaki açı olsun ürün.

Sonuç olarak bir kenar (ve bir karşılık gelecek) tepe noktası maksimum açı ile alıyorum.

Sonuç listesi köşe geçirilen her ekliyorum. Sonuç listesi sendika çokgen.

Açıklamalar

1. Bu algoritma bize çokgenler birden fazla birleştirmek için izin verir çokgenin çift ile tekrarlayarak uygulayın.
2. Eğer çok bezier eğrileri ve çizgilerden oluşan bir yolu varsa, bu yolu dümdüz.