Bagaimana cara menentukan apakah daftar titik poligon berurutan searah jarum jam?

260

Memiliki daftar poin, bagaimana saya menemukan jika mereka berada dalam urutan searah jarum jam?

Sebagai contoh:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

akan mengatakan bahwa itu berlawanan arah jarum jam (atau berlawanan arah jarum jam, bagi sebagian orang).

Stécy
sumber
5
TOLONG DICATAT: Jawaban yang diterima, dan banyak jawaban setelahnya, membutuhkan banyak penambahan dan penggandaan (mereka didasarkan pada perhitungan area yang berakhir negatif atau positif; misalnya "formula tali sepatu"). Sebelum menerapkan salah satu dari itu, pertimbangkan jawaban lhf , yang lebih sederhana / lebih cepat - berdasarkan wiki - orientasi poligon sederhana .
ToolmakerSteve
Saya selalu memikirkannya dalam hal produk silang dari dua vektor yang berdekatan. Jika saya berjalan di sekeliling poligon, kepala saya menunjuk keluar dari pesawat. Saya menyilangkan vektor bidang ke vektor arah berjalan untuk mendapatkan arah ketiga dalam sistem koordinat saya. Jika titik vektor sehingga interior di sebelah kiri saya berlawanan arah jarum jam; jika interior di sebelah kanan saya searah jarum jam.
duffymo

Jawaban:

416

Beberapa metode yang disarankan akan gagal dalam kasus poligon non-cembung, seperti bulan sabit. Berikut ini adalah salah satu yang sederhana yang akan bekerja dengan poligon non-cembung (bahkan akan bekerja dengan poligon berpotongan sendiri seperti angka delapan, memberi tahu Anda apakah sebagian besar searah jarum jam).

Jumlahkan ujung-ujungnya, (x 2 - x 1 ) (y 2 + y 1 ). Jika hasilnya positif kurva searah jarum jam, jika negatif maka kurva berlawanan arah jarum jam. (Hasilnya adalah dua kali area tertutup, dengan konvensi +/-.)

point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4
point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18
point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30
point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0
point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0
                                         ---
                                         -44  counter-clockwise
Beta
sumber
28
Itu kalkulus diterapkan pada kasus sederhana. (Saya tidak memiliki keterampilan untuk memposting gambar.) Area di bawah segmen garis sama dengan tinggi rata-rata (y2 + y1) / 2 kali panjang horisontal (x2-x1). Perhatikan konvensi tanda di x. Coba ini dengan beberapa segitiga dan Anda akan segera melihat cara kerjanya.
Beta
72
Peringatan kecil: jawaban ini mengasumsikan sistem koordinat Cartesian normal. Alasan yang layak disebutkan adalah bahwa beberapa konteks umum, seperti kanvas HTML5, menggunakan sumbu Y terbalik. Maka aturan harus dibalik: jika area negatif , kurva searah jarum jam.
LarsH
8
@ Mr.Qbs: Jadi metode saya berfungsi, tetapi jika Anda melewatkan bagian penting , maka itu tidak berhasil. Ini bukan berita.
Beta
11
@ Mr.Qbs: Anda harus selalu menautkan titik terakhir ke yang pertama. Jika Anda memiliki N poin yang dinomori dari 0 hingga N-1, maka Anda harus menghitung: Sum( (x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]) )untuk i = 0 hingga N-1. Yaitu, harus mengambil indeks Modulo N ( N ≡ 0) Rumus hanya berfungsi untuk poligon tertutup . Poligon tidak memiliki tepi imajiner.
Olivier Jacot-Descombes
4
Blog.element84.com/polygon-winding.html ini menjelaskan dalam bahasa Inggris sederhana mengapa solusi ini berfungsi.
David Zorychta
49

Produk silang mengukur tingkat tegak lurus dua vektor. Bayangkan bahwa setiap tepi poligon Anda adalah vektor dalam bidang xy dari ruang xyz tiga dimensi (3-D). Maka produk silang dari dua sisi yang berurutan adalah vektor dalam arah-z, (arah-z positif jika segmen kedua searah jarum jam, minus arah-z jika berlawanan arah jarum jam). Besarnya vektor ini sebanding dengan sinus sudut antara dua tepi asli, sehingga mencapai maksimum ketika mereka tegak lurus, dan berangsur-angsur menghilang ketika ujung-ujungnya adalah collinear (paralel).

Jadi, untuk setiap titik (titik) poligon, hitung besarnya produk-silang dari dua sisi yang bersebelahan:

Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)

Jadi beri label pada tepinya secara berurutan seperti
edgeAsegmen dari point0ke point1dan
edgeBantara point1ke point2
...
edgeEadalah antara point4dan point0.

Kemudian Vertex A ( point0) berada di antara
edgeE[Dari point4ke point0]
edgeA[Dari point0ke `titik1 '

Kedua tepi ini sendiri adalah vektor, yang koordinat x dan y dapat ditentukan dengan mengurangi koordinat titik awal dan akhir mereka:

edgeE= point0-point4 = (1, 0) - (5, 0)= (-4, 0) dan
edgeA= point1- point0= (6, 4) - (1, 0)= (5, 4) dan

Dan produk silang dari dua tepi ini berdampingan dihitung dengan menggunakan determinan dari matriks berikut, yang dibangun dengan menempatkan koordinat dua vektor di bawah simbol yang mewakili tiga sumbu koordinat ( i, j, & k). Koordinat bernilai-ketiga (nol) ada karena konsep produk silang adalah konstruk 3-D, jadi kami memperluas vektor 2-D ini menjadi 3-D untuk menerapkan produk-silang:

 i    j    k 
-4    0    0
 1    4    0    

Mengingat bahwa semua produk silang menghasilkan vektor tegak lurus terhadap bidang dua vektor yang dikalikan, penentu matriks di atas hanya memiliki kkomponen, (atau sumbu z).
Rumus untuk menghitung besarnya kkomponen sumbu z adalah
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16

Besarnya nilai ini ( -16), adalah ukuran sinus sudut antara 2 vektor asli, dikalikan dengan produk dari besarnya 2 vektor.
Sebenarnya, formula lain untuk nilainya adalah
A X B (Cross Product) = |A| * |B| * sin(AB).

Jadi, untuk kembali ke ukuran sudut yang Anda butuhkan untuk membagi nilai ini, ( -16), dengan produk dari besarnya dua vektor.

|A| * |B| = 4 * Sqrt(17) =16.4924...

Jadi ukuran dosa (AB) = -16 / 16.4924 =-.97014...

Ini adalah ukuran apakah segmen berikutnya setelah simpul telah membungkuk ke kiri atau ke kanan, dan seberapa banyak. Tidak perlu minum arc-sinus. Yang akan kita pedulikan hanyalah besarnya, dan tentu saja tandanya (positif atau negatif)!

Lakukan ini untuk masing-masing 4 poin lainnya di sekitar jalur tertutup, dan tambahkan nilai-nilai dari perhitungan ini di setiap titik.

Jika jumlah akhir positif, Anda bergerak searah jarum jam, negatif, berlawanan arah jarum jam.

Charles Bretana
sumber
3
Sebenarnya, solusi ini adalah solusi yang berbeda dari solusi yang diterima. Apakah mereka setara atau tidak adalah pertanyaan yang saya selidiki, tapi saya kira mereka tidak ... Jawaban yang diterima menghitung luas poligon, dengan mengambil perbedaan antara area di bawah tepi atas poligon dan area di bawah tepi bawah poligon. Yang satu akan negatif (yang Anda lewati dari kiri ke kanan), dan yang lainnya negatif. Saat melintasi searah jarum jam, Tepi atas dilalui dari kiri ke kanan dan lebih besar, sehingga totalnya positif.
Charles Bretana
1
Solusi saya mengukur jumlah sinus dari perubahan sudut tepi di setiap titik. Ini akan menjadi positif ketika melintasi searah jarum jam dan negatif ketika melintasi berlawanan arah jarum jam.
Charles Bretana
2
Tampaknya dengan pendekatan ini Anda perlu mengambil arcsin, kecuali jika Anda menganggap cembung (dalam hal ini Anda hanya perlu memeriksa satu titik)
agentp
2
Anda harus mengambil arcsin. Cobalah pada sekelompok poligon non-cembung acak, dan Anda akan menemukan tes akan gagal untuk beberapa poligon jika Anda tidak mengambil arcsin.
Luke Hutchison
1
@CharlesBretana - sementara saya belum menjalankan tes Luke, saya percaya dia benar. Itulah sifat penjumlahan yang dikombinasikan dengan skala nonlinear [tanpa arcsin vs dengan arcsin]. Pertimbangkan apa yang disarankan marsbear, yang Anda tolak dengan benar. Dia menyarankan agar Anda "hanya menghitung", dan Anda menunjukkan bahwa beberapa nilai besar bisa lebih besar daripada sejumlah besar nilai kecil. Sekarang pertimbangkan arcsin dari setiap nilai vs tidak. Bukankah masih kasus bahwa gagal untuk mengambil arcsin memberikan bobot yang salah untuk masing-masing nilai, karena itu memiliki cacat yang sama (meskipun jauh lebih buruk)?
ToolmakerSteve
47

Saya kira ini adalah pertanyaan yang cukup lama, tapi saya akan membuang solusi lain, karena itu mudah dan tidak intensif secara matematis - itu hanya menggunakan aljabar dasar. Hitung area poligon yang sudah ditandatangani. Jika negatif, poin berada dalam urutan searah jarum jam, jika positif mereka berlawanan arah jarum jam. (Ini sangat mirip dengan solusi Beta.)

Hitung area yang ditandatangani: A = 1/2 * (x 1 * y 2 - x 2 * y 1 + x 2 * y 3 - x 3 * y 2 + ... + x n * y 1 - x 1 * y n )

Atau dalam pseudo-code:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2

Perhatikan bahwa jika Anda hanya memeriksa pemesanan, Anda tidak perlu repot membaginya dengan 2.

Sumber: http://mathworld.wolfram.com/PolygonArea.html

Sean the Bean
sumber
Apakah itu salah ketik pada rumus area yang Anda tandatangani di atas? Itu berakhir dengan "xn * y1 - x1 * yn"; ketika saya percaya itu harus "x_n y_ {n + 1} - y_n x_ {n-1}" (setidaknya di LaTeX). Di sisi lain, sudah sepuluh tahun sejak saya mengambil kelas aljabar linear.
Michael Eric Oberlin
Nggak. Jika Anda memeriksa sumbernya , Anda akan melihat bahwa rumus tersebut pada kenyataannya mereferensikan titik pertama lagi dalam istilah terakhir (y1 dan x1). (Maaf, saya tidak terlalu terbiasa dengan LaTeX, tapi saya memformat langganan untuk membuatnya lebih mudah dibaca.)
Sean the Bean
Saya menggunakan solusi ini dan itu berfungsi dengan baik untuk saya gunakan. Perhatikan bahwa jika Anda dapat merencanakan ke depan dan menyimpan dua ekstra vektor dalam array Anda, Anda dapat menyingkirkan perbandingan (atau%) dengan menambahkan vektor pertama di ujung array. Dengan begitu, Anda hanya mengulang semua elemen, kecuali yang terakhir (panjang-2 bukannya panjang-1).
Eric Fortier
2
@EricFortier - FWIW, daripada mengubah ukuran array yang mungkin besar, alternatif yang efisien adalah untuk setiap iterasi untuk menyimpan poinnya previousPointuntuk iterasi berikutnya. Sebelum memulai loop, setel previousPointke titik terakhir larik. Trade off adalah salinan variabel lokal ekstra tetapi lebih sedikit akses array. Dan yang paling penting, tidak perlu menyentuh array input.
ToolmakerSteve
2
@MichaelEricOberlin - perlu untuk menutup poligon, dengan memasukkan segmen garis dari titik terakhir ke titik pertama. (Perhitungan yang benar akan sama, tidak peduli titik mana yang memulai poligon tertutup.)
ToolmakerSteve
38

Temukan simpul dengan y terkecil (dan x terbesar jika ada ikatan). Biarkan simpul menjadi Adan simpul sebelumnya dalam daftar menjadi Bdan simpul berikutnya dalam daftar menjadi C. Sekarang hitung tanda produk silang dari ABdan AC.


Referensi:

lhf
sumber
7
Ini juga dijelaskan dalam en.wikipedia.org/wiki/Curve_orientation . Intinya adalah bahwa titik yang ditemukan harus pada cembung cembung, dan itu hanya perlu untuk melihat secara lokal pada satu titik pada cembung cembung (dan tetangga terdekatnya) untuk menentukan orientasi seluruh poligon.
M Katz
1
Terkejut dan kagum ini belum menerima lebih banyak suara. Untuk poligon sederhana ( yang merupakan poligon terbanyak di beberapa bidang ), jawaban ini menghasilkan O(1)solusi. Semua jawaban lain menghasilkan O(n)solusi untuk njumlah poin poligon. Untuk optimisasi yang lebih dalam, lihat sub Pertimbangan Praktis dari artikel orientasi Kurva Wikipedia yang fantastis .
Cecil Curry
8
Klarifikasi: solusi iniO(1)hanya jika salah satu (A) poligon ini adalah cembung (dalam hal mana setiap vertex sewenang-wenang berada di cembung cembung dan karenanya cukup) atau (B) Anda sudah tahu titik dengan koordinat Y terkecil. Jika ini bukan masalahnya (yaitu, poligon ini non-cembung dan Anda tidak tahu apa-apa tentang itu),O(n)pencarian diperlukan. Karena tidak ada penjumlahan yang diperlukan, bagaimanapun, ini masih jauh lebih cepat daripada solusi lain untuk poligon sederhana.
Cecil Curry
1
@CecilCurry Saya pikir komentar kedua Anda menjelaskan mengapa ini belum menerima lebih banyak upvotes. Ini menghasilkan jawaban yang salah dalam skenario tertentu, tanpa menyebutkan keterbatasan itu.
LarsH
24

Berikut ini adalah implementasi algoritma C # sederhana berdasarkan jawaban ini .

Mari kita asumsikan bahwa kita memiliki Vectortipe Xdan Yproperti tipe double.

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

%adalah modulo atau operator sisa yang melakukan operasi modulo yang ( menurut Wikipedia ) menemukan sisanya setelah pembagian satu angka dengan yang lain.

Olivier Jacot-Descombes
sumber
6

Mulai dari salah satu simpul, dan hitung sudut yang digantikan oleh setiap sisi.

Yang pertama dan yang terakhir akan menjadi nol (jadi lewati itu); untuk selebihnya, sinus sudut akan diberikan oleh produk silang dari normalisasi ke satuan panjang (titik [n]-titik [0]) dan (titik [n-1]-titik [0]).

Jika jumlah nilai-nilai itu positif, maka poligon Anda digambar dalam arti anti-searah jarum jam.

Steve Gilham
sumber
Melihat bagaimana produk silang pada dasarnya bermuara pada faktor penskalaan positif dikalikan dengan sudut, mungkin lebih baik untuk hanya melakukan produk silang. Ini akan lebih cepat dan tidak rumit.
ReaperUnreal
4

Untuk apa nilainya, saya menggunakan mixin ini untuk menghitung urutan berliku untuk aplikasi Google Maps API v3.

Kode memanfaatkan efek samping dari area poligon: urutan simpul berliku searah jarum jam menghasilkan area positif, sedangkan urutan berliku berlawanan arah jarum jam dari titik yang sama menghasilkan area yang sama dengan nilai negatif. Kode juga menggunakan semacam API pribadi di perpustakaan geometri Google Maps. Saya merasa nyaman menggunakannya - gunakan dengan risiko Anda sendiri.

Penggunaan sampel:

var myPolygon = new google.maps.Polygon({/*options*/});
var isCW = myPolygon.isPathClockwise();

Contoh lengkap dengan unit test @ http://jsfiddle.net/stevejansen/bq2ec/

/** Mixin to extend the behavior of the Google Maps JS API Polygon type
 *  to determine if a polygon path has clockwise of counter-clockwise winding order.
 *  
 *  Tested against v3.14 of the GMaps API.
 *
 *  @author  [email protected]
 *
 *  @license http://opensource.org/licenses/MIT
 *
 *  @version 1.0
 *
 *  @mixin
 *  
 *  @param {(number|Array|google.maps.MVCArray)} [path] - an optional polygon path; defaults to the first path of the polygon
 *  @returns {boolean} true if the path is clockwise; false if the path is counter-clockwise
 */
(function() {
  var category = 'google.maps.Polygon.isPathClockwise';
     // check that the GMaps API was already loaded
  if (null == google || null == google.maps || null == google.maps.Polygon) {
    console.error(category, 'Google Maps API not found');
    return;
  }
  if (typeof(google.maps.geometry.spherical.computeArea) !== 'function') {
    console.error(category, 'Google Maps geometry library not found');
    return;
  }

  if (typeof(google.maps.geometry.spherical.computeSignedArea) !== 'function') {
    console.error(category, 'Google Maps geometry library private function computeSignedArea() is missing; this may break this mixin');
  }

  function isPathClockwise(path) {
    var self = this,
        isCounterClockwise;

    if (null === path)
      throw new Error('Path is optional, but cannot be null');

    // default to the first path
    if (arguments.length === 0)
        path = self.getPath();

    // support for passing an index number to a path
    if (typeof(path) === 'number')
        path = self.getPaths().getAt(path);

    if (!path instanceof Array && !path instanceof google.maps.MVCArray)
      throw new Error('Path must be an Array or MVCArray');

    // negative polygon areas have counter-clockwise paths
    isCounterClockwise = (google.maps.geometry.spherical.computeSignedArea(path) < 0);

    return (!isCounterClockwise);
  }

  if (typeof(google.maps.Polygon.prototype.isPathClockwise) !== 'function') {
    google.maps.Polygon.prototype.isPathClockwise = isPathClockwise;
  }
})();
Steve Jansen
sumber
Mencoba ini, saya mendapatkan hasil yang sebaliknya, sebuah poligon yang digambar dengan urutan searah jarum jam menghasilkan area negatif, sementara satu penghitung yang ditarik searah jarum jam menghasilkan positif. Dalam kedua kasus ini, cuplikan ini masih sangat berguna selama 5 tahun, terima kasih.
Cameron Roberts
@CameronRoberts Norma (lihat IETF khususnya untuk geoJson) adalah mengikuti 'aturan kanan'. Saya kira Google mengeluh. Dalam hal ini cincin luar harus berlawanan arah jarum jam (menghasilkan area positif), dan cincin bagian dalam (lubang) berliku searah jarum jam (area negatif yang akan dihapus dari area utama).
allez l'OM
4

Implementasi jawaban Sean dalam JavaScript:

function calcArea(poly) {
    if(!poly || poly.length < 3) return null;
    let end = poly.length - 1;
    let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
    for(let i=0; i<end; ++i) {
        const n=i+1;
        sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
    }
    return sum;
}

function isClockwise(poly) {
    return calcArea(poly) > 0;
}

let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];

console.log(isClockwise(poly));

let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];

console.log(isClockwise(poly2));

Cukup yakin ini benar. Tampaknya berfungsi :-)

Poligon tersebut terlihat seperti ini, jika Anda bertanya-tanya:

Mpen
sumber
3

Ini adalah fungsi yang diimplementasikan untuk OpenLayers 2 . Kondisi untuk memiliki poligon searah jarum jam adalah area < 0, itu dikonfirmasi oleh referensi ini .

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);
}
MSS
sumber
Openlayers adalah pustaka manajemen peta berbasis javascript seperti googlemaps dan ini ditulis dan digunakan dalam openlayers 2.
MSS
Bisakah Anda jelaskan sedikit apa yang kode Anda lakukan, dan mengapa Anda melakukannya?
nbro
@nbro kode ini mengimplementasikan jawaban lhf . Sangat mudah untuk menjaga bagian non OpenLayer dalam fungsi javascript murni dengan memiliki simpul langsung sebagai parameter. Ini berfungsi dengan baik, dan bisa disesuaikan dengan kasus multiPolygon .
allez l'OM
2

Jika Anda menggunakan Matlab, fungsi ispolycwmengembalikan true jika simpul poligon berada dalam urutan searah jarum jam.

Frederick
sumber
1

Sebagaimana juga dijelaskan dalam artikel Wikipedia ini , orientasi Kurva , diberikan 3 poin p, qdan rdi pesawat (yaitu dengan koordinat x dan y), Anda dapat menghitung tanda dari penentu berikut

masukkan deskripsi gambar di sini

Jika penentu negatif (yaitu Orient(p, q, r) < 0), maka poligon berorientasi searah jarum jam (CW). Jika penentu positif (yaitu Orient(p, q, r) > 0), poligon berorientasi berlawanan arah jarum jam (CCW). Determinan adalah nol (yaitu Orient(p, q, r) == 0) jika poin p, qdan ryang collinear .

Dalam rumus di atas, kami menambahkan yang di depan koordinat p, q dan rkarena kami menggunakan koordinat homogen .

Ian
sumber
@tibetty Bisakah Anda menjelaskan mengapa metode ini tidak berfungsi dalam banyak situasi jika poligon cekung?
nbro
1
Silakan lihat tabel terakhir dalam referensi item wiki di posting Anda. Mudah bagi saya untuk memberikan contoh yang salah tetapi sulit untuk membuktikannya.
tibetty
1
Silakan lihat tabel terakhir dalam referensi item wiki di posting Anda. Mudah bagi saya untuk memberikan contoh yang salah tetapi sulit untuk membuktikannya.
tibetty
1
@tibetty benar. Anda tidak bisa hanya mengambil tiga poin di sepanjang poligon; Anda mungkin berada di daerah cembung atau cekung dari poligon itu. Membaca wiki dengan hati-hati, seseorang harus mengambil tiga titik di sepanjang cembung yang menutupi poligon . Dari "pertimbangan praktis": "Seseorang tidak perlu membangun cembung cembung poligon untuk menemukan titik yang sesuai. Pilihan yang umum adalah titik poligon dengan koordinat X terkecil. Jika ada beberapa dari mereka, satu dengan koordinat Y terkecil diambil. Dijamin akan menjadi [a] puncak cembung poligon. "
ToolmakerSteve
1
Karenanya jawaban awal lhf , yang serupa, dan merujuk pada artikel wiki yang sama, tetapi menjelaskan hal tersebut. [Tampaknya tidak masalah apakah seseorang mengambil yang terkecil atau terbesar, x atau y, selama seseorang menghindari berada di tengah; secara efektif seseorang bekerja dari satu ujung kotak pembatas di sekitar poligon, untuk menjamin di wilayah cekung.]
ToolmakerSteve
0

Saya pikir agar beberapa poin diberikan searah jarum jam, semua sisi harus positif, bukan hanya jumlah sisi. Jika satu sisi negatif dari setidaknya 3 poin diberikan berlawanan arah jarum jam.

daniel
sumber
Benar, tetapi Anda salah memahami konsep urutan belitan poligon (searah atau berlawanan arah jarum jam). Dalam poligon yang sepenuhnya cembung, sudut di semua titik akan searah jarum jam atau semua akan berlawanan arah jarum jam [seperti dalam kalimat pertama Anda]. Dalam poligon dengan daerah cekung, "gua" akan berada di arah yang berlawanan, tetapi poligon secara keseluruhan masih memiliki interior yang terdefinisi dengan baik, dan dianggap searah jarum jam atau berlawanan arah jarum jam. Lihat en.wikipedia.org/wiki/…
ToolmakerSteve
0

Solusi C # / LINQ saya didasarkan pada saran lintas produk dari @charlesbretana di bawah ini. Anda dapat menentukan referensi normal untuk belitan. Ini harus bekerja selama kurva sebagian besar di bidang didefinisikan oleh vektor atas.

using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace SolidworksAddinFramework.Geometry
{
    public static class PlanePolygon
    {
        /// <summary>
        /// Assumes that polygon is closed, ie first and last points are the same
        /// </summary>
       public static bool Orientation
           (this IEnumerable<Vector3> polygon, Vector3 up)
        {
            var sum = polygon
                .Buffer(2, 1) // from Interactive Extensions Nuget Pkg
                .Where(b => b.Count == 2)
                .Aggregate
                  ( Vector3.Zero
                  , (p, b) => p + Vector3.Cross(b[0], b[1])
                                  /b[0].Length()/b[1].Length());

            return Vector3.Dot(up, sum) > 0;

        } 

    }
}

dengan tes unit

namespace SolidworksAddinFramework.Spec.Geometry
{
    public class PlanePolygonSpec
    {
        [Fact]
        public void OrientationShouldWork()
        {

            var points = Sequences.LinSpace(0, Math.PI*2, 100)
                .Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0))
                .ToList();

            points.Orientation(Vector3.UnitZ).Should().BeTrue();
            points.Reverse();
            points.Orientation(Vector3.UnitZ).Should().BeFalse();



        } 
    }
}
bradgonesurfing
sumber
0

Ini solusi saya menggunakan penjelasan di jawaban lain:

def segments(poly):
    """A sequence of (x,y) numeric coordinates pairs """
    return zip(poly, poly[1:] + [poly[0]])

def check_clockwise(poly):
    clockwise = False
    if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
        clockwise = not clockwise
    return clockwise

poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False

poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True
Gianni Spear
sumber
1
Bisakah Anda menentukan jawaban mana yang tepat berdasarkan jawaban ini?
nbro
0

Metode yang jauh lebih sederhana secara komputasi, jika Anda sudah tahu titik di dalam poligon :

  1. Pilih segmen garis mana saja dari poligon asli, titik, dan koordinatnya dalam urutan itu.

  2. Tambahkan titik "di dalam" yang diketahui, dan bentuk segitiga.

  3. Hitung CW atau CCW seperti yang disarankan di sini dengan tiga poin itu.

Venkata Goli
sumber
Mungkin ini berfungsi jika poligon sepenuhnya cembung. Ini pasti tidak dapat diandalkan jika ada daerah cekung - mudah untuk memilih titik yang ada di sisi "salah" dari salah satu tepi gua, lalu hubungkan ke tepi itu. Akan mendapatkan jawaban yang salah.
ToolmakerSteve
Ini bekerja bahkan jika poligon itu cekung. Poinnya harus berada di dalam poligon cekung itu. Namun saya tidak yakin tentang poligon kompleks (tidak diuji.)
Venkata Goli
"Ini bekerja bahkan jika poligon itu cekung." - Contoh tandingan: poli (0,0), (1,1), (0,2), (2,2), (2,0). Segmen baris (1,1), (0, 2). Jika Anda memilih titik interior dalam (1,1), (0,2), (1,2) untuk membentuk segitiga -> (1,1), (0,2), (0,5,1,5)), Anda mendapatkan berlawanan gulungan daripada jika Anda memilih titik interior dalam (0,0), (1,1), (1,0)> (1,1), (0,2), (0,5,0,5). Keduanya merupakan interior dari poligon asli, namun memiliki belitan yang berlawanan. Karena itu, salah satunya memberikan jawaban yang salah.
ToolmakerSteve
Secara umum, jika poligon memiliki wilayah cekung, pilih segmen di wilayah cekung. Karena cekung, Anda dapat menemukan dua titik "interior" yang berada di sisi berlawanan dari garis itu. Karena mereka berada di sisi yang berlawanan dari garis itu, segitiga yang dibentuk memiliki belitan yang berlawanan. Akhir dari bukti.
ToolmakerSteve
0

Setelah menguji beberapa implementasi yang tidak dapat diandalkan, algoritma yang memberikan hasil memuaskan mengenai orientasi CW / CCW di luar kotak adalah yang diposkan oleh OP di utas ini ( shoelace_formula_3).

Seperti biasa, angka positif mewakili orientasi CW, sedangkan angka negatif CCW.

Marjan Moderc
sumber
0

Inilah solusi cepat 3.0 berdasarkan jawaban di atas:

    for (i, point) in allPoints.enumerated() {
        let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
        signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
    }

    let clockwise  = signedArea < 0
Toby Evetts
sumber
0

Solusi lain untuk ini;

const isClockwise = (vertices=[]) => {
    const len = vertices.length;
    const sum = vertices.map(({x, y}, index) => {
        let nextIndex = index + 1;
        if (nextIndex === len) nextIndex = 0;

        return {
            x1: x,
            x2: vertices[nextIndex].x,
            y1: x,
            y2: vertices[nextIndex].x
        }
    }).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);

    if (sum > -1) return true;
    if (sum < 0) return false;
}

Ambil semua simpul sebagai array seperti ini;

const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);
Ind
sumber
0

Solusi untuk R untuk menentukan arah dan membalikkan jika searah jarum jam (merasa perlu untuk objek owin):

coords <- cbind(x = c(5,6,4,1,1),y = c(0,4,5,5,0))
a <- numeric()
for (i in 1:dim(coords)[1]){
  #print(i)
  q <- i + 1
  if (i == (dim(coords)[1])) q <- 1
  out <- ((coords[q,1]) - (coords[i,1])) * ((coords[q,2]) + (coords[i,2]))
  a[q] <- out
  rm(q,out)
} #end i loop

rm(i)

a <- sum(a) #-ve is anti-clockwise

b <- cbind(x = rev(coords[,1]), y = rev(coords[,2]))

if (a>0) coords <- b #reverses coords if polygon not traced in anti-clockwise direction
dez
sumber
0

Walaupun jawaban ini benar, secara matematis mereka lebih kuat daripada yang diperlukan. Asumsikan koordinat peta, di mana titik paling utara adalah titik tertinggi di peta. Temukan titik paling utara, dan jika 2 titik mengikat, itu adalah yang paling utara lalu paling timur (ini adalah titik yang digunakan lhf dalam jawabannya). Dalam poin Anda,

titik [0] = (5,0)

poin [1] = (6,4)

poin [2] = (4,5)

poin [3] = (1,5)

poin [4] = (1,0)

Jika kita mengasumsikan bahwa P2 adalah yang paling utara maka titik timur baik titik sebelumnya atau berikutnya menentukan searah jarum jam, CW, atau CCW. Karena titik paling utara adalah di wajah utara, jika P1 (sebelumnya) ke P2 bergerak ke timur arahnya adalah CW. Dalam hal ini, ia bergerak ke barat, jadi arahnya adalah CCW sebagaimana jawaban yang diterima mengatakan. Jika titik sebelumnya tidak memiliki gerakan horizontal, maka sistem yang sama berlaku untuk titik berikutnya, P3. Jika P3 berada di sebelah barat P2, berarti, maka pergerakannya adalah CCW. Jika gerakan P2 ke P3 adalah timur, di barat dalam hal ini, gerakannya adalah CW. Asumsikan bahwa nte, P2 dalam data Anda, adalah titik paling utara kemudian timur dan prv adalah titik sebelumnya, P1 dalam data Anda, dan nxt adalah titik berikutnya, P3 dalam data Anda, dan [0] horizontal atau timur / barat di mana barat kurang dari timur, dan [1] vertikal.

if (nte[0] >= prv[0] && nxt[0] >= nte[0]) return(CW);
if (nte[0] <= prv[0] && nxt[0] <= nte[0]) return(CCW);
// Okay, it's not easy-peasy, so now, do the math
if (nte[0] * nxt[1] - nte[1] * nxt[0] - prv[0] * (nxt[1] - crt[1]) + prv[1] * (nxt[0] - nte[0]) >= 0) return(CCW); // For quadrant 3 return(CW)
return(CW) // For quadrant 3 return (CCW)
VectorVortec
sumber
IMHO, akan lebih aman untuk tetap berpegang pada matematika dasar yang ditunjukkan dalam jawaban lhf - terima kasih telah menyebutkannya. Tantangan dalam mereduksinya menjadi kuadran adalah bahwa cukup banyak pekerjaan untuk membuktikan bahwa formula Anda benar dalam semua kasus. Apakah Anda menghitung "lebih barat" dengan benar? Dalam poligon cekung di mana kedua [1] dan [3] adalah "barat dan selatan" [2]? Apakah Anda benar menangani panjang [1] dan [3] yang berbeda dalam situasi itu? Saya tidak tahu, sedangkan jika saya langsung menghitung sudut itu (atau determinannya), saya menggunakan rumus-rumus terkenal.
ToolmakerSteve
@ToolmakerSteve pernyataan if selalu bekerja jika 3 poin cembung. Pernyataan if akan kembali, maka Anda akan mendapatkan jawaban yang benar. Pernyataan if tidak akan kembali, jika bentuknya cekung dan ekstrem. Saat itulah Anda harus melakukan perhitungan. Sebagian besar gambar memiliki satu kuadran, sehingga bagian itu mudah. Lebih dari 99% panggilan subrutin saya ditangani oleh pernyataan if.
VectorVortec
Itu tidak menjawab kekhawatiran saya. Formula apa itu? Apakah itu penentu orientasi seperti yang diberikan dalam tautan wiki dari jawaban lhf? Jika demikian, maka katakan demikian. Jelaskan bahwa apa yang Anda lakukan adalah melakukan pemeriksaan cepat yang menangani sebagian besar kasus, untuk menghindari matematika standar. Jika begitu, maka jawaban Anda sekarang masuk akal bagi saya. (Minor nit: akan lebih mudah dibaca jika Anda menggunakan .xdan .ymenggunakan struct, daripada [0]dan [1]. Saya tidak tahu apa kata kode Anda, pertama kali saya meliriknya.)
ToolmakerSteve
Karena saya tidak memiliki kepercayaan pada pendekatan Anda, saya menerapkan pendekatan lhf ; rumus dari tautannya. Bagian yang lambat adalah menemukan pencarian vertex - O (N) yang sesuai. Setelah ditemukan, penentu adalah operasi O (1), menggunakan 6 kali lipat dengan 5 tambah. Bagian terakhir itulah yang telah Anda optimalkan; tetapi Anda telah melakukannya dengan menambahkan tes-if tambahan. Saya pribadi tidak dapat membenarkan mengambil pendekatan non-standar - perlu memverifikasi setiap langkah sudah benar - Tapi terima kasih atas analisis kuadran yang menarik!
ToolmakerSteve
0

Kode C # untuk mengimplementasikan jawaban lhf :

// https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
    int nVerts = vertices.Count;
    // If vertices duplicates first as last to represent closed polygon,
    // skip last.
    Vector2 lastV = vertices[nVerts - 1];
    if (lastV.Equals(vertices[0]))
        nVerts -= 1;
    int iMinVertex = FindCornerVertex(vertices);
    // Orientation matrix:
    //     [ 1  xa  ya ]
    // O = | 1  xb  yb |
    //     [ 1  xc  yc ]
    Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
    Vector2 b = vertices[iMinVertex];
    Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
    // determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
    double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);

    // TBD: check for "==0", in which case is not defined?
    // Can that happen?  Do we need to check other vertices / eliminate duplicate vertices?
    WindingOrder result = detOrient > 0
            ? WindingOrder.Clockwise
            : WindingOrder.CounterClockwise;
    return result;
}

public enum WindingOrder
{
    Clockwise,
    CounterClockwise
}

// Find vertex along one edge of bounding box.
// In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
    int iMinVertex = -1;
    float minY = float.MaxValue;
    float minXAtMinY = float.MaxValue;
    for (int i = 0; i < vertices.Count; i++)
    {
        Vector2 vert = vertices[i];
        float y = vert.Y;
        if (y > minY)
            continue;
        if (y == minY)
            if (vert.X >= minXAtMinY)
                continue;

        // Minimum so far.
        iMinVertex = i;
        minY = y;
        minXAtMinY = vert.X;
    }

    return iMinVertex;
}

// Return value in (0..n-1).
// Works for i in (-n..+infinity).
// If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
    // "+n": Moves (-n..) up to (0..).
    return (i + n) % n;
}
ToolmakerSteve
sumber
1
Ini tampaknya untuk koordinat Y down-is-positive. Balikkan CW / CCW untuk koordinat standar.
Warwick Allison
0

Berikut ini implementasi Python 3 sederhana berdasarkan jawaban ini (yang, pada gilirannya, didasarkan pada solusi yang diusulkan dalam jawaban yang diterima )

def is_clockwise(points):
    # points is your list (or array) of 2d points.
    assert len(points) > 0
    s = 0.0
    for p1, p2 in zip(points, points[1:] + [points[0]]):
        s += (p2[0] - p1[0]) * (p2[1] + p1[1])
    return s > 0.0
nbro
sumber
-4

temukan pusat massa titik-titik ini.

misalkan ada garis dari titik ini ke poin Anda.

temukan sudut antara dua garis untuk line0 line1

daripada melakukannya untuk line1 dan line2

...

...

jika sudut ini meningkat secara monoton daripada berlawanan,

lain jika menurun secara monoton searah jarum jam

lain (tidak monoton)

Anda tidak bisa memutuskan, jadi itu tidak bijaksana

ufukgun
sumber
oleh "pusat massa" Saya pikir maksud Anda "centroid"?
Vicky Chijwani
Mungkin berfungsi jika poligon sepenuhnya cembung. Tetapi lebih baik menggunakan jawaban yang akan bekerja untuk poligon non-cembung.
ToolmakerSteve