Algoritma untuk menggembungkan / mengempiskan (offsetting, buffering) poligon

Bagaimana saya "mengembang" poligon? Yaitu, saya ingin melakukan sesuatu yang serupa dengan ini:

Syaratnya adalah bahwa tepi / titik poligon baru (meningkat) semuanya pada jarak konstan yang sama dari poligon lama (asli) (pada contoh gambar tidak, karena kemudian harus menggunakan busur untuk simpul yang digembungkan, tapi mari kita lupakan itu untuk saat ini;)).

Istilah matematika untuk apa yang saya cari sebenarnya mengimbangi ke dalam / luar poligon . +1 ke balint untuk menunjukkan ini. Penamaan alternatif adalah penyangga poligon .

Hasil pencarian saya:

Berikut ini beberapa tautan:

• Sebuah Survei Strategi Offset Poligon
• Offset poligon, MASALAH
• Buffering Polygon Data

Saya pikir saya mungkin secara singkat menyebutkan perpustakaan kliping dan mengimbangi poligon saya sendiri - Clipper .

Sementara Clipper terutama dirancang untuk operasi kliping poligon, Clipper juga mengimbangi. Perpustakaan adalah freeware open source yang ditulis dalam bahasa Delphi, C ++ dan C # . Ini memiliki lisensi Peningkatan yang sangat tidak terbebani yang memungkinkannya untuk digunakan dalam aplikasi freeware dan komersial tanpa biaya.

Offset poligon dapat dilakukan dengan menggunakan salah satu dari tiga gaya offset - kuadrat, bulat, dan disatukan.

Poligon yang Anda cari disebut polygon offset ke dalam / luar dalam geometri komputasi dan terkait erat dengan kerangka lurus .

Ini adalah beberapa poligon offset untuk poligon yang rumit:

Dan ini adalah kerangka lurus untuk poligon lain:

Seperti yang ditunjukkan dalam komentar lain, juga, tergantung pada seberapa jauh Anda berencana untuk "mengembang / mengempis" poligon Anda, Anda dapat berakhir dengan konektivitas yang berbeda untuk output.

Dari sudut pandang komputasi: begitu Anda memiliki kerangka lurus, Anda harus dapat membuat poligon offset dengan relatif mudah. Sumber terbuka dan (gratis untuk non-komersial) perpustakaan CGAL memiliki paket yang menerapkan struktur ini. Lihat contoh kode ini untuk menghitung poligon offset menggunakan CGAL.

The pengguna paket harus memberikan yang baik sebuah titik awal tentang bagaimana membangun struktur ini bahkan jika Anda tidak akan menggunakan CGAL, dan berisi referensi ke kertas dengan definisi matematika dan sifat:

Manual CGAL: Kerangka Lurus 2D dan Pengimbangan Poligon

Untuk hal-hal semacam ini saya biasanya menggunakan JTS . Untuk tujuan demonstrasi saya membuat jsFiddle ini yang menggunakan JSTS (JavaScript port of JTS). Anda hanya perlu mengonversi koordinat yang Anda miliki ke koordinat JSTS:

function vectorCoordinates2JTS (polygon) {
  var coordinates = [];
  for (var i = 0; i < polygon.length; i++) {
    coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
  }
  return coordinates;
}

Hasilnya kira-kira seperti ini:

Info tambahan : Saya biasanya menggunakan inflating / deflating jenis ini (sedikit dimodifikasi untuk keperluan saya) untuk menetapkan batas dengan jari-jari pada poligon yang digambar di peta (dengan Leaflet atau Google maps). Anda hanya mengonversi pasangan (lat, lng) ke koordinat JSTS dan yang lainnya sama. Contoh:

Kedengarannya seperti apa yang Anda inginkan:

• Mulai dari titik, hadapi berlawanan arah jarum jam di sepanjang tepi yang berdekatan.
• Ganti tepi dengan tepi paralel baru yang ditempatkan pada jarak dke "kiri" yang lama.
• Ulangi untuk semua ujung.
• Temukan persimpangan tepi baru untuk mendapatkan simpul baru.
• Mendeteksi jika Anda telah menjadi poligon silang dan memutuskan apa yang harus dilakukan tentang hal itu. Mungkin menambahkan titik baru di titik persimpangan dan menyingkirkan beberapa yang lama. Saya tidak yakin apakah ada cara yang lebih baik untuk mendeteksi ini daripada hanya membandingkan setiap pasangan tepi yang tidak berdekatan untuk melihat apakah perpotongan mereka terletak di antara kedua pasang simpul.

Poligon yang dihasilkan terletak pada jarak yang diperlukan dari poligon lama "cukup jauh" dari simpul. Di dekat titik, himpunan titik pada jarak ddari poligon lama, seperti yang Anda katakan, bukan poligon, sehingga persyaratan yang dinyatakan tidak dapat dipenuhi.

Saya tidak tahu apakah algoritma ini memiliki nama, kode contoh di web, atau optimasi jahat, tapi saya pikir itu menjelaskan apa yang Anda inginkan.

Di dunia GIS seseorang menggunakan buffering negatif untuk tugas ini: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

The JTS perpustakaan harus melakukan ini untuk Anda. Lihat dokumentasi untuk operasi buffer: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Untuk gambaran umum kasar, lihat juga Panduan Pengembang: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Setiap garis harus membagi bidang menjadi "bagian dalam" dan "garis besar"; Anda dapat menemukan ini menggunakan metode produk dalam biasa.

Pindahkan semua garis keluar dengan jarak tertentu.

Pertimbangkan semua pasangan garis tetangga (garis, bukan segmen garis), temukan persimpangan. Ini adalah simpul baru.

Bersihkan verteks baru dengan menghapus bagian berpotongan. - Kami punya beberapa kasus di sini

(a) Kasus 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

jika Anda mengeluarkannya satu per satu, Anda dapat:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 dan 4 tumpang tindih .. jika Anda melihat ini, Anda menghapus titik ini dan semua titik di antaranya.

(B) kasus 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

jika Anda menghabiskannya dengan dua, Anda mendapatkan ini:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

untuk menyelesaikan ini, untuk setiap segmen garis, Anda harus memeriksa apakah tumpang tindih dengan segmen yang terakhir.

(c) kasus 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

pengeluaran oleh 1. ini adalah kasus yang lebih umum untuk kasus 1.

(d) kasus 4

sama seperti case3, tetapi menghabiskan dua.

Sebenarnya, jika Anda dapat menangani case 4. Semua case lainnya hanya case khusus dengan beberapa garis atau vertex yang tumpang tindih.

Untuk melakukan kasus 4, Anda menyimpan setumpuk titik .. Anda mendorong ketika Anda menemukan garis tumpang tindih dengan baris terakhir, pop ketika Anda mendapatkan baris terakhir. - Persis seperti apa yang Anda lakukan di cembung.

Ini adalah solusi alternatif, lihat apakah Anda lebih suka ini.

1. Lakukan triangulasi , tidak harus delaunay - triangulasi apa pun akan berhasil.

2. Mengembang setiap segitiga - ini harus sepele. jika Anda menyimpan segitiga dalam urutan anti-searah jarum jam, cukup pindahkan garis ke sisi kanan dan lakukan persimpangan.

3. Gabungkan mereka menggunakan algoritma kliping Weiler-Atherton yang dimodifikasi

Terima kasih banyak kepada Angus Johnson untuk perpustakaan guntingnya. Ada contoh kode yang baik untuk melakukan hal-hal kliping di beranda clipper di http://www.angusj.com/delphi/clipper.php#code tapi saya tidak melihat contoh untuk offset poligon. Jadi saya pikir mungkin itu berguna bagi seseorang jika saya memposting kode saya:

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        foreach (var point in originalPath)
        {
            polygon.Add(new ClipperLib.IntPoint(point.X, point.Y));
        }

        ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset();
        co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);

        List<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        co.Execute(ref solution, offset);

        foreach (var offsetPath in solution)
        {
            foreach (var offsetPathPoint in offsetPath)
            {
                resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y)));
            }
        }

        return resultOffsetPath;
    }

Satu opsi lebih lanjut adalah menggunakan boost :: polygon - dokumentasi agak kurang, tetapi Anda harus menemukan metode resizedan bloat, dan juga +=operator kelebihan beban , yang sebenarnya menerapkan buffering. Jadi misalnya meningkatkan ukuran poligon (atau satu set poligon) dengan beberapa nilai dapat sesederhana:

poly += 2; // buffer polygon by 2

Berdasarkan saran dari @ JoshO'Brian, tampaknya rGeospaket dalam Rbahasa mengimplementasikan algoritma ini. Lihat rGeos::gBuffer.

Ada beberapa perpustakaan yang dapat digunakan (Juga dapat digunakan untuk set data 3D).

1. https://github.com/otherlab/openmesh
2. https://github.com/alecjacobson/nested_cages
3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

Orang juga dapat menemukan publikasi yang sesuai untuk pustaka ini untuk memahami algoritma lebih terinci.

Yang terakhir memiliki paling tidak dependensi dan mandiri dan dapat membaca file .obj.

Salam hangat, Stephan

Saya menggunakan geometri sederhana: Vektor dan / atau Trigonometri

1. Di setiap sudut temukan vektor tengah, dan sudut tengah. Vektor tengah adalah rata-rata aritmatika dari dua vektor satuan yang ditentukan oleh tepi sudut. Mid Angle adalah setengah dari sudut yang ditentukan oleh tepi.

2. Jika Anda perlu memperluas (atau mengontrak) poligon Anda dengan jumlah d dari setiap sisi; Anda harus keluar (dalam) dengan jumlah d / sin (midAngle) untuk mendapatkan titik sudut baru.

3. Ulangi ini untuk semua sudut

*** Berhati-hatilah dengan arahmu. Lakukan Uji CounterClockWise menggunakan tiga titik yang menentukan sudut; untuk mencari tahu jalan mana yang keluar, atau masuk