Padatkan himpunan titik-titik pada suatu poligon menjadi himpunan titik-titik yang lebih pendek

Dua jawaban yang ada memiliki kekurangan yang besar:

• Metode Durkee hanya berfungsi jika jarak antara titik-titik berikutnya sama persis. Titik-titik harus mempunyai koordinat yang dapat direpresentasikan secara sempurna sebagai nilai titik-mengambang, sehingga jarak antara titik-titik berikutnya pada suatu garis dapat diketahui sama. Jika titik-titiknya tidak berjarak sama, maka metode ini tidak akan menghasilkan apa-apa. Selain itu, titik awal dan akhir poligon tidak diperiksa secara bersamaan, jadi jika garis lurus terbentuk melintasi awal/akhir poligon, akan tersisa satu titik yang terlalu banyak.

• Metode ShadowMan lebih baik karena jarak tidak harus sama, dan garis yang melintasi awal/akhir poligon adalah ditangani dengan benar. Namun ia juga menggunakan perbandingan kesetaraan floating point, yang tidak akan berfungsi secara umum. Hanya dengan koordinat bilangan bulat metode ini akan berfungsi dengan benar. Selain itu, ia menggunakan vecnorm (yang menghasilkan akar kuadrat) dan pembagian, keduanya merupakan operasi yang relatif mahal (jika dibandingkan dengan metode yang ditunjukkan di sini).

Untuk mengetahui apakah tiga titik membentuk garis lurus, dapat digunakan aturan aritmatika sederhana. Katakanlah kita memiliki poin p0, p1 dan p2. Vektor dari p0 hingga p1 dan vektor dari p0 hingga p2 membentuk dasar jajaran genjang, yang luasnya dapat dihitung dengan perkalian silang dari dua vektor (dalam 2D, perkalian silang dipahami menggunakan z=0, dengan vektor yang dihasilkan memiliki x=0 dan y=0, hanya nilai z yang berguna; dengan demikian, 2D perkalian silang yang kita asumsikan menghasilkan nilai skalar). Itu dapat dihitung sebagai berikut:

v1 = p1 - p0;
v2 = p2 - p0;
x = v1(1)*v2(2) - v1(2)*v2(1);

x hasil kali silang akan bernilai nol jika kedua vektor sejajar, artinya ketiga titik tersebut segaris. Namun pengujian kesetaraan dengan 0 harus mempunyai toleransi, karena aritmatika floating-point tidak eksak. Saya menggunakan 1e-6 sebagai toleransi di sini. Gunakan nilai yang beberapa kali lipat lebih kecil dari jarak antar titik Anda.

Diberikan kumpulan masukan titik p, kita dapat mencari titik sudut dengan:

p1 = p;                                  % point 1
p0 = circshift(p1,1);                    % point 0
v1 = p1 - p0;                            % vector from point 0 to 1
v2 = circshift(p1,-1) - p0;              % vector from point 0 to 2
x = v1(:,1).*v2(:,2) - v1(:,2).*v2(:,1); % cross product
idx = abs(x) > 1e-6;                     % comparison with tolerance
p = p(idx,:);                            % corner points

Perhatikan bahwa uji perkalian silang ini akan gagal jika dua titik berurutan memiliki koordinat yang sama (yaitu salah satu vektor memiliki panjang nol). Tes tambahan akan diperlukan jika data dapat memiliki poin duplikat.

Berikut hasil dari ketiga metode tersebut. Saya telah membuat poligon dengan koordinat non-trivial dan jarak simpul yang tidak sama. Saya juga menempatkan celah awal/akhir di tengah garis lurus. Ciri-ciri ini bertujuan untuk menunjukkan kekurangan kedua metode lainnya.

Ini adalah kode yang saya gunakan untuk menghasilkan grafik:

% Make a polygon that will be difficult for the other two methods
p = [0,0 ; 0.5,0 ; 1,0 ; 1,1 ; 0.5,1 ; 0,1];
p = p + rand(size(p))/3;
p(end+1,:) = p(1,:);
q = [];
for ii = 1:size(p,1)-1
   t = p(ii,:) + (p(ii+1,:) - p(ii,:)) .* [0;0.1;1/3;0.45;0.5897545;pi/4;exp(1)/3];
   q = [q;t];
end
q = circshift(q,3,1);

figure
subplot(2,2,1)
plot(q(:,1),q(:,2),'bo-')
axis equal
title('input')

subplot(2,2,2)
res1 = method1(q);
plot(res1(:,1),res1(:,2),'ro-')
axis equal
title('Durkee''s method')

subplot(2,2,3)
res2 = method2(q);
plot(res2(:,1),res2(:,2),'ro-')
axis equal
title('ShadowMan''s method')

subplot(2,2,4)
res3 = method3(q);
plot(res3(:,1),res3(:,2),'go-')
axis equal
title('correct method')

% Durkee's method: https://stackoverflow.com/a/55603145/7328782
function P = method1(P)
a = logical([1 diff(P(:,1),2)' 1]);
b = logical([1 diff(P(:,2),2)' 1]);
idx = or(a,b);
P = P(idx,:);
end

% ShadowMan's method: https://stackoverflow.com/a/55603040/7328782
function corners = method2(poly0)
poly0Z = circshift(poly0,1);
poly0I = circshift(poly0,-1);
unitVectIn =(poly0 - poly0I)./vecnorm((poly0 - poly0I),2,2);
unitVectOut =(poly0Z - poly0)./vecnorm((poly0Z - poly0),2,2);
cornerIndices = sum(unitVectIn == unitVectOut,2)==0;
corners = poly0(cornerIndices,:);
end
% vecnorm is new to R2017b, I'm still running R2017a.
function p = vecnorm(p,n,d)
% n is always 2
p = sqrt(sum(p.^2,d));
end

function p = method3(p1)
p0 = circshift(p1,1);
v1 = p1 - p0;
v2 = circshift(p1,-1) - p0;
x = v1(:,1).*v2(:,2) - v1(:,2).*v2(:,1);
idx = abs(x) > 1e-6;
p = p1(idx,:);
end

Oke, saya mengadaptasi ini untuk menangani sudut non-persegi.

Perhatikan sebuah segitiga yang diidentifikasi oleh titik-titiknya

P = [0 0; 1 0; 2 0; 1.5 1; 1 2; .5 1; 0 0];

Ini adalah array 7x2, jika kita mendefinisikan 2 vektor turunan seperti yang ditentukan oleh pertanyaan yang saya sebutkan di komentar.

a = logical([1 diff(P(:,1),2)' 1]);
b = logical([1 diff(P(:,2),2)' 1]);

Dari sana, kita dapat menggabungkan keduanya untuk mendapatkan variabel pengindeksan baru

idx = or(a,b);

Akhirnya, kita dapat menggunakan ini untuk membuat plot kita

line(P(idx,1), P(idx,2),'Color','k','LineWidth',3,'LineStyle',':');

Jika Anda membuat plot garis, saya rasa Anda perlu menyetel variabel terakhir ke false.

idx(end) = false;

Cara 'vektor' bisa dilakukan dengan cukup elegan. Saya mencoba cara loop for juga dan Anda dapat melakukan hal yang sama tetapi Anda meminta vektor jadi inilah cara saya melakukannya.

Satu-satunya perubahan yang saya buat pada data Anda adalah menghapus semua replika sebelum memulai skrip ini. Selain itu, poin yang diberikan harus berurutan searah jarum jam atau berlawanan arah jarum jam.

    poly0Z = circshift(poly0,1);
    poly0I = circshift(poly0,-1); 
    unitVectIn =(poly0 - poly0I)./vecnorm((poly0 - poly0I),2,2);
    unitVectOut =(poly0Z - poly0)./vecnorm((poly0Z - poly0),2,2)  ;
    cornerIndices = sum(unitVectIn == unitVectOut,2)==0
    corners = poly0(cornerIndices,:)

    line(poly0(:,1), poly0(:,2),'Color','k','LineWidth',2,'LineStyle',':');
    hold on
    scatter(corners(:,1), corners(:,2),'filled')

Dasar dari metode ini adalah pergi ke setiap titik, menghitung vektor satuan yang masuk, dan vektor satuan yang keluar. Titik dimana vektor satuan masuk tidak sesuai dengan vektor satuan keluar adalah sudut.