Bagaimana cara menghitung luas bentuk yang tidak beraturan?

17

Saya memiliki objek ruang yang ditentukan oleh kumpulan segmen garis perulangan yang perlu saya perhitungkan luasnya. Kelas-kelas dapat dijelaskan sebagai berikut (dalam pseudo-code):

class Point {
    float x; 
    float y;
    ...
    float distanceFrom(Point p);
}

class Segment {
    Point start;
    Point end;
    ...
    float length();
}

class Room {
    List<Segment> walls;
    ...
    float area();
}

Dinding-dinding sebuah ruangan tidak pernah bisa berpotongan di mana pun, tetapi pada titik akhir segmen dan "sub-loop" apa pun yang dibuat juga akan dipisahkan menjadi ruang baru. Solusinya tidak perlu benar-benar akurat (margin kesalahan 10% dapat diterima) dan juga tidak sering dihitung (<1 / d).

algorithm geometry
sumber
7
Akan lebih masuk akal jika Roommemuat daftar Points, dan kemudian mendapatkan segmen dengan menghubungkan setiap titik dan kemudian memutarnya kembali. Jika tidak, dengan pengaturan Anda saat ini, sangat timur untuk mendapatkan nilai yang salah (mis. Ruangan tertutup, ruangan dengan dinding di tengah, dll.). Ini akan menjadi pilihan terbaik.
MCMastery
Pilihan lain adalah triangulasi bentuk atas dan hitung luas setiap segitiga. Bagian yang sulit adalah triangulasi. Bisa dilakukan, tetapi tidak selalu cantik. Jawaban tali sepatu masih jauh lebih baik.
Draco18s tidak lagi mempercayai SE
@MCMastery Solusi itu tidak akan berfungsi, karena mengharuskan Rooms untuk selalu lengkap, dan itu mungkin tidak terjadi jika saya meminta pemain membuat Rooms menggunakan Segments. Juga, fungsi ruang tertutup mudah untuk didefinisikan (hanya loop melalui Segments dan pastikan mereka membuat ruang).

Jawaban:

31

Anda dapat menggunakan rumus tali sepatu Gauss :

Anda perlu mengambil koordinat x dari setiap titik, kalikan dengan koordinat y titik berikutnya, lalu kurangi koordinat y titik saat ini dikalikan dengan koordinat x titik berikutnya dari hasil dan menambahkannya ke total area. Setelah Anda melakukan ini untuk setiap titik, membagi dua area total untuk mendapatkan area sebenarnya dari poligon. Jika titik saat ini adalah yang terakhir, maka yang berikutnya adalah yang pertama.

A = 0

for (i = 0; i < points.length; i++) do

    A += points[i].x * points[(i + 1) % points.length].y - points[i].y * points[(i + 1) % points.length].x

end

A /= 2
Bálint
sumber
2
Saya selalu menggunakannya untuk menghitung produk silang dari dua vektor yang tidak pernah tahu itu disebut algoritme tali sepatu
Sidar
3
Perhatikan bahwa ini dapat diperluas untuk menghitung volume objek 3D tidak teratur yang terbuat dari segitiga, dan dapat dianggap sebagai kasus sepele dari teorema dasar kalkulus.
Dietrich Epp
5
Area di sini sudah ditandatangani. Pergi melalui poin ke arah lain dan final Adinegasikan. Tergantung pada tujuan, A = |A|mungkin diperlukan. Dengan kode area negatif dapat menemukan area pada donat tidak teratur menggunakan daftar poin di dalam dan luar (satu dalam urutan yang berlawanan).
chux - Reinstate Monica
6
Karena tentu saja Gauss atau Euler memiliki formula untuk itu.
corsiKa
0

Kita juga bisa menggunakan metode Monte Carlo.

Gambarlah persegi panjang di sekitar bentuk sewenang-wenang. Ambil contoh sumber PRNG yang terdistribusi secara merata. mersenne twister, lalu ikat output dengan X, Y panjang persegi panjang menggunakan fungsi modulo. Hitung tidak. poin acak yang mendarat di dalam bentuk Anda. Membagi dengan jumlah total poin yang dihasilkan. Kalikan hasil bagi itu dengan area persegi panjang itu. Dengan setiap iterasi, Anda akan bertemu ke area yang benar. Algoritma ini sangat paralel dan dapat digunakan untuk menghitung 'volume' bentuk sewenang-wenang, selama Anda dapat menentukan apakah koordinat R ^ N berada dalam batas R ^ N bentuk.

.

Di sini seseorang menggunakan metode ini menemukan area lingkaran kemudian menggunakannya untuk menghitung pi https://www.youtube.com/watch?v=VJTFfIqO4TU

FranG
sumber
2
-1: Anda tidak ingin menggunakan modulo untuk mendapatkannya dalam jangkauan, Anda ingin menggunakan distribusi yang seragam atau distribusi lainnya, melakukannya dengan cara modulo memiliki segala macam masalah statistik.
user1997744
12
Metode ini mungkin bermanfaat ketika kita tidak memiliki poligon sederhana, tetapi lebih tepatnya bentuk implisit yang batasnya sulit diungkapkan, seperti gumpalan fraktal atau metaball. Untuk kasus poligon seperti dalam pertanyaan, sepertinya itu akan mahal.
DMGregory
Seperti yang ditunjukkan oleh @DMGregory, ini bukan yang saya cari. Namun, saya pikir itu layak diberi +1 kalau-kalau ada orang lain yang membutuhkannya.
Ini menarik tetapi bukankah biaya tes inklusi akan menjadi penghalang? Yaitu jika Anda memiliki bentuk yang cukup kompleks untuk menjamin pendekatan ini, bukankah tes inklusi juga benar-benar mahal sehingga Anda tidak ingin melakukan banyak dari mereka? (dengan asumsi poligon)
Mattia
Ok modulo memang bermasalah, tapi ini solusi sederhana. Apa yang benar-benar kita dapatkan adalah P acak = 1/2 bit 0/1, jadi yang kita dapatkan adalah distribusi angka yang seragam misalnya. untuk 3 bit dari 0 hingga 7. Melakukan rand% 5, jika angka acak mengambil nilai 6 atau 7, dipetakan ke 1 atau 2, secara efektif meningkatkan 1,2 frekuensi sehingga distribusi menjadi tidak seragam. Untuk menghindarinya Anda memerlukan sesuatu seperti mesin negara yang memutar pemetaan misalnya. 6,7 peta menjadi 1,2 lalu ke 3,4 lalu 5,0 dan terus berlanjut. Kita juga bisa membuang 6,7 kapan pun mereka datang. Pokoknya itu masalah implementasi perpustakaan.
FranG
-1

Pendekatan lain: Jangan.

Sebagai gantinya:

while (Segments.Count > 3)
{
    Segment A = Segments[Segments.Count - 2];
    Segment B = Segments[Segments.Count - 1];
    Segment C = new Segment(B.End, A.Start);
    Triangle T = new Triangle(A, B, C);
    Segments[Segments.Count - 2] = C;
    Segments.RemoveAt(Segments.Count - 1);
    if (B is inside the new shape Segments)
        Area -= T.Area;
    else
        Area += T.Area;
}
Area += new Triangle(Segments[0], Segments[1], Segments[2]).Area;

Pada dasarnya, potong segitiga. Luas segitiga adalah sederhana dan dengan demikian kami mengurangi jumlah segmen sisanya dengan satu. Ulangi sampai yang tersisa adalah segitiga.

Loren Pechtel
sumber
2
Rumus Gauss 'Shoelace adalah singkatan untuk ini yang membagi dua atau pertiga dari jumlah perhitungan. Menyelesaikannya.
Pieter Geerkens