Dışbükey olmayan bir çokgende geniş bir köşe kümesi verildiğinde, kenarları nasıl bulabilirim?

Question

Bir dizi köşem var (A adı verilen) ve tüm kenarlık köşelerini bulmak istiyorum, böylece bu kenarlık çizgileri kümenin şeklidir.

A'daki köşe noktalarının çoğu gereksizdir, çünkü bunlar şekil içinde olduğundan, bu köşelerden kurtulmak istiyorum.

Soruma Best Algorithm to find the edges (polygon) of vertices benzer, ancak bir dışbükey çokgen durumda çalışmak için ona ihtiyacım var.

DÜZENLEME: Açıklama: Aşağıdaki görüntü içbükey bir çokgendir. Bu, dışbükey olmayan tarafından kastım. Üzerinde bir dışbükey gövde algoritması çalıştırırsam, poligonun içbükey kısmını koruyamazdım (yanılmadıkça).

içimde ve poligonun sınırında köşe bir dizi var: O kadar setini azaltmak isteyen [[x1, y1], [x2, y2] ...] Köşeler sadece şeklin sınır çizgisidir.

Answer 1

Bu sıcak bir konu gibi görünüyor .. https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

Bu yazı iyi gibi görünüyor. Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

Answer 2

Açıklamaunuz biraz belirsiz ancak bir dizi nokta için Convex Hull oluşturmak üzere algoritmayı aramanız mümkündür. Basitçe söylemek gerekirse, dışbükey gövde, tüm köşelerin etrafına lastik bir bant yerleştirirseniz elde ettiğiniz şekli alır. 2D olarak bir dışbükey algoritma yazmak
korkunç zor değil ve sen hangi bir özel durum gibi görünüyor bağlantı qhull

(Bu cevap da söz konusu verilir gibi yapmak bazı kütüphaneler vardır senin soru)

Answer 3

Bu eski, belki de terkedilmiş bir sorudur, ama beni düşünmeme sebep oldu. Dışbükey bir gövde aramıyorsunuz, çokgen şeklini korumak istiyorsunuz, ancak bir çizgi boyunca "kenarlar" arasında yer alan noktalardan kurtulmak istiyorsunuz. Solüsyon, komşu noktalardan geçerek birinci ve ikinci çizginin doğrusal eğimini hesaplayabilir, sonra bu eğim değerini kaydedebilir, eğer pt1-pt2'nin eğimi buna eşit ise ikinci ve üçüncü eğimi hesaplayabilir. pt2-pt3'ün daha sonra pt2, çizginin oluşturulmasında gereksizdir ve bu şekilde çıkarılabilir. Pt1'e geri dönene kadar içeride tutun.

Bu, içbükey şeklin korunmasını sağlar ancak alakasız ekstra noktalar kaldırılır.