Dizideki karmaşık bir çokgenin köşe noktaları olan bir dizi nokta saat yönünde mi yoksa saat yönünün tersinde mi tanımlandı?

Question

DÜZENLEME: Yanıtla birlikte program'u güncelledim ve harika çalışıyor!

program (bunu denemek için çekinmeyin), kullanıcıların daha sonra üçgenlenecek çokgenler çizmelerini sağlar. Köşeleri eklemek için tıklayabilir ve üçgenlere girmek için girebilir. Her neyse, algoritma, saatlerin saat yönünde veya saatin tersi yönde çekilip çekilmediğini söyleyebildiğim sürece gayet iyi çalışıyor (şu anda sadece saat yönüne çokgenlerle çalışmak zorunda kaldım). Bunu günlerce çözmeye çalışıyorum, ancak noktaların saat yönünde mi yoksa saat yönünün tersine mi olduğunu belirleme konusunda hiçbir fikrim yok. Daha iyi bir fikir edinmek için daha önce bahsettiğim programla şekil çizmeye çalışın, daha iyi konuştuğum şeyi deneyimlemeyi deneyebileceğimden daha iyi deneyimleyebilirsiniz. Burada

noktaları tanımlanır nasıl:

:

Burada

saat yönünün tersine bir çokgenin bir görüntüdür: Burada

function Point(x, y) { 
    this.x = x; 
    this.y = y; 
} 

var vertices = []; 

// Called on click 
function addPoint(mouseX, mouseY) { 
    vertices.push(new Point(mouseX, mouseY)); 
} 

saat yönünde bir çokgen bir resimdir

Eğer noktaların "saat yönü" ni nasıl belirleyeceğimi anlamaya yardım ederseniz çok minnettar olurum!

Answer 1

Çokgen alanını shoelace formula kullanarak, ancak mutlak değer işareti olmadan hesaplayın. Sonuç pozitif ise, noktalar saat yönünün tersine, eğer negatif ise saat yönünde sıralanır.

function polygonArea() { 
    var area = 0; 
    for (var i = 0; i < vertices.length; i++) { 
     j = (i + 1) % vertices.length; 
     area += vertices[i].x * vertices[j].y; 
     area -= vertices[j].x * vertices[i].y; 
    } 
    return area/2; 
} 
var clockwise = polygonArea() > 0; 

Answer 2

Genel bir fikir, poligonunuzun dışbükey gövdesine bakıp oryantasyonu oradan tahmin etmektir. Bununla birlikte, yönelimi bulmak için tüm gövdeyi oluşturmanıza gerek olmadığını, ancak buna ait bir segmentin olduğunu düşünüyorum.

Yani:

• diğer tüm noktalar bu hattın bir tarafında bulunacak şekilde poligonlar iki puan bulun.
• Tüm noktalar solda ise (sadece noktalardan birini işaretleyin), saat yönünün tersine. Sağ taraftalarsa saat yönünde.

Örnek: Üst şekil üzerinde

: 4-5 Sağdaki figür verelim 5-11 sağdaki rakam verelim ... alt şekil üzerinde : 6- 7 soldaki şekle izin verin, 7-14 soldaki şekle izin verin, ...

Uyarı: Çokgenizde "yürürken", rakamı yeniden başlatmayın, aksi halde yanlış olur. En üstteki resimde, 4- (n-1), soldaki şekle izin verin!

Answer 3

Clockwisedness'ın sezgisel tanımınız iyi tanımlanmamış. Bir at nalı çizerseniz Örneğin,:

/---a-b--\ 
/ _d_c_ \ 
//  \ \ 
| |  | | 
| |  | | 
    \ \  // 
    \ \ // 
    --  -- 

0 = a < b < b < d Eğer ben a ve b bakmak Ben şekil saat yönünde çizilmiştir sizin açıklamasından sonuçlandırmak, ama 0 = c < d < a < b eğer şekil edildiği sonucuna varmak istiyorum saat yönünün tersine çekilmiş.Bu senaryoların her ikisi de noktaların çizildiği aynı doğrultuyu içerdiğinden, sadece farklı başlangıç ​​noktalarından, sadece tanımınızın eksik olduğu sonucuna varabilirim.

Çizdiğim at nalı en iyisi değil; Buradaki fikir, diğer tarafın zıt yöne çekilmesine izin vermek için, dipte küçük bir delik bulunan neredeyse bir dairedir. (Sonlu diğeri sonsuz)

iki ayrı bölüme uçağı ayıran gibi herhangi sonlu basit poligonu düşünüldüğünde: Eğer daha sıkı şeyler tanımlayan ilgileniyorsanız

, o zaman ben şu satırlar boyunca bir şey önermek Sonlu alanı her zaman poligonun iç kısmı olarak düşünebiliriz. Böyle bir senaryoda, sağ taraftaki dış tarafla koşulan noktaların sırasına göre saat yönünde olacak bir köşe sırası tanımlarız. Buna curve orientation denir.

Bu daha katı bir tanıma sahip olduğunuzda, uygulama, sarma numarasını saymak kadar basit olabilir. Sipariş edilen herhangi bir çiftin orta noktasını (0 ve 1) alın, sipariş edilen çiftin sağına (herhangi bir açıda, dik olarak) bir çizgi parçası alın ve diğer çizgi bölümleriyle kaç kesişme noktası olduğunu sayın: Eğri saat yönünde sayı tuhaf.

Bu, O(n) zamanında doğrusal uygulanması basittir ve O(1) sabit alanını ekler.

Answer 4

Bu OpenLayers için özelleştirilmiş bir işlev işlevi. Saat Yönünde Çokgen Durumunu Görebileceğiniz Gibi Alan Onayla. durumda birinin ShapeUtils Three.js kullanan

function IsClockwise(feature) 
{ 
if(feature.geometry==null)return -1; 
var vertices=feature.geometry.getVertices(); 
var area=0; 
for (var i = 0; i < (vertices.length); i++) 
    { 
    j = (i + 1) % vertices.length; 
    area += vertices[i].x * vertices[j].y; 
    area -= vertices[j].x * vertices[i].y; 
    // console.log(area); 
    } 
return (area < 0); 
} 

Answer 5

dahili hesaplanan alana işaretini belirlemek için area yöntemini kullanan bir dahili isClockWise yöntemi ile donatılmıştır.

isClockWise: function (pts) { 

    return ShapeUtils.area(pts) < 0; 

} 

ShapeUtils.isClockWise yöntem herebulunabilir.

area: function (contour) { 

    var n = contour.length; 
    var a = 0.0; 

    for (var p = n - 1, q = 0; q < n; p = q ++) { 

     a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y; 

    } 

    return a * 0.5; 

}, 

ShapeUtils.area yöntem herebulunabilir.