Çokgen içinde hangi noktaların bulunup bulunmadığı (çok sayıda nokta) nasıl belirlenir?

Question

bir 2-boyutlu numpy dizisi (: X koordinatları, 2. sütun: y koordinatları 1. sütun) saklanan veri noktaları (100.000) büyük bir set var. Ayrıca her veri noktası için ek bilgi depolayan birçok 1 boyutlu dizi var. Şimdi sadece belirli bir çokgende bulunan noktaları içeren bu 1D dizilerinin alt kümelerinden grafikler oluşturmak istiyorum.

#XY is the 2D array. 
#A is one of the 1D arrays. 
#poly is a matplotlib.patches.Polygon 

mask = np.array([bool(poly.get_path().contains_point(i)) for i in XY]) 

matplotlib.pylab.hist(A[mask], 100) 
matplotlib.pylab.show() 

bu kodu geliştirmek için bana yardım eder misiniz:

ben zarif ya da hızlı değil ise aşağıdaki çözüm geldi? Liste kavraması yerine np.vectorize ile oynamaya çalıştım ama çalışmayı başaramadı. çok etkili bir test uygular

Answer 1

kullanın matplotlib.nxutils.points_inside_poly.

Örnekler ve matplotlib FAQ bu 40 yaşındaki bir algoritmanın başka bir açıklama.

Güncelleştirme: Matplotlib'nin 1.2.0 sürümünden bu yana points_inside_poly kullanımdan kaldırıldığını unutmayın. Bunun yerine matplotlib.path.Path.contains_points kullanın.

Answer 2

Korkarım ki kullandığınız kütüphanelere aşina değilim, ama kullanabileceğim algoritma için makul bir fikrim olduğunu düşünüyorum ve bunu vanilya python'la nasıl uygulayacağımı düşünüyorum. o zaman bunu geliştirebilir ve bu kütüphaneleri kullanarak uygulayabilirsiniz. Ayrıca, bunun bunu başarmanın en iyi yolu olduğunu iddia etmiyorum, ama cevabımı oldukça hızlı bir şekilde almak istedim, işte burada.

---

Şimdi, bir fikir, örneğin nokta kümesinin konveks dizi bulmak için algoritmalar iki vektörün çapraz ürünün kullanımından gelen Graham's Scan. iki puan p1 ve sırasıyla (x1, y1) ve (X2, Y2) kökenli (0,0), nokta vektörlerini p1 ve p2 tanımlayan p2, bildirmektedir. p1 x p2 enine ürün üçüncü vektörünün her ikisi de p1 ve p2 dik olan ve vektörler tarafından sınırlanan paralelkenar alanı tarafından belirli bir büyüklüğe sahip p3 verir. x2 * y1 vektörü p3 büyüklüğünü verir ve işaret p3 olmadığını gösterir -

Çok faydalı bir sonuç x1 * y2 olan matrisin

/ x1, x2 \ 
\ y1, y2/

... belirleyicisi olmasıdır, "düzlemden" çıkıyor veya "içeri giriyor". Buradaki en önemli nokta bu büyüklüğü p2 sonra pozitif isep1 ait "sola" olduğu ve daha sonra p2 negatif isep1 arasında "sağ" dir.

Umarım bu ASCII sanatı örneği yardımcı olacaktır:

. p2(4, 5) 
/
/
/
/_ _ _ _ _. p1(5, 0) 

x1 * y2 - x2 * y1 = 5 * 4-0 * 5 = 20 ve böylece p2p1 "sola" dir

Niçin bu bizim için neden yararlıdır! Poligonun bir köşesi ve grafikteki diğer noktaların bir listesi varsa, poligonun her kenarı için bu kenarın vektörünü elde edebiliriz. Ayrıca, başlangıç ​​noktasını grafiğin tüm diğer noktalarına birleştiren vektörleri elde edebiliriz ve bunların her bir kenar için bazı noktaları elemine edebilecek kenarın sağına mı yoksa sağa mı olduğunu test edebiliriz. İşlemin sonunda kaldırılmamış olanların hepsi poligonun içindeki noktalardır. Her neyse, bu biraz daha mantıklı olmak için bazı kodlara!

poly = [(1, 1), (4, 2), (5, 5), (3, 8), (0, 4)]

:

---

örneğin bazı beşgen olabilir, bir karşı saat yönünde onları çizim olsaydı onları ziyaret ediyorum sırayla poligonun köşe bir listesini alın Grafikteki diğer tüm noktaları içeren bir set alın, bu setteki geçersiz noktaları aşamalı olarak kaldıracağız. İşlemin sonunda kalanlar tam olarak poligonun içindeki noktalardır.

points = set(['(3, 0), (10, -2), (3,3), ...])

kodunun kendi ana bit aslında nasıl çalıştığı hakkında yazmamı aldı ne kadar süre için oldukça kompakt. to_right, vektörleri temsil eden iki tupl alır ve v2v1'un sağında True döndürür. Döngüler daha sonra poligonun tüm kenarlarından geçer ve kenarlardan herhangi birinin sağında yer alırlarsa çalışma setindeki noktaları kaldırırlar.

def to_right(v1, v2): 
    return (v1[0]*v2[1] - v1[1]*v2[0]) < 0 

for i in range(len(poly)): 
    v1 = poly[i-1] 
    v2 = poly[i] 
    for p in points: 
     if(to_right(v2-v1, p-v1)): 
      points.remove(p) 

düzenleme: onlar sol çokgenin köşe belirtilen sırayla bağlıdır aksine sağa ise kaldırıldıkları gerçeği açıklığa kavuşturmak için. Saat yönünde olduklarında, bunun yerine sol-yalan noktalarını ortadan kaldırmak isteyeceksiniz. Şu anda bu konu için özellikle harika bir çözümüm yok.

---

Her neyse, umarım bu konuda da haklıyım ve OP'den olmasa bile birilerine yardımcı olur. Bu algoritmanın asimptotik karmaşıklığı, O (mn) 'dir, burada n, grafikteki noktaların sayısıdır ve m, poligonun köşe noktalarının sayısı, en kötü durumda tüm noktalar poligonun içinde yer alır ve her noktayı kontrol etmek zorundayız. Her kenar için, hiç çıkartılmamış.