คำตอบสองข้อที่มีอยู่มีข้อบกพร่องอย่างมาก:
เมธอดของ Durkee ใช้ได้ก็ต่อเมื่อระยะห่างระหว่างจุดต่อมาเท่ากันทุกประการ จุดจะต้องมีพิกัดที่สามารถแทนค่าจุดลอยตัวได้อย่างสมบูรณ์ เพื่อให้สามารถพบว่าระยะห่างระหว่างจุดที่ตามมาบนเส้นจะเท่ากัน ถ้าคะแนนไม่เท่ากัน วิธีนี้ก็จะไม่ทำอะไรเลย นอกจากนี้ จุดเริ่มต้นและจุดสิ้นสุดของรูปหลายเหลี่ยมจะไม่ถูกตรวจสอบพร้อมกัน ดังนั้น หากมีการสร้างเส้นตรงพาดผ่านจุดเริ่มต้น/จุดสิ้นสุดของรูปหลายเหลี่ยม จะเหลือจุดหนึ่งที่มากเกินไป
วิธีของ ShadowMan ดีกว่าตรงที่ระยะทางไม่จำเป็นต้องเท่ากัน และเส้นที่พาดจุดเริ่มต้น/สิ้นสุดของรูปหลายเหลี่ยมคือ ได้รับการจัดการอย่างถูกต้อง อย่างไรก็ตาม มันยังใช้การเปรียบเทียบความเท่าเทียมกันของจุดลอยตัวด้วย ซึ่งจะใช้งานไม่ได้โดยทั่วไป เฉพาะพิกัดจำนวนเต็มเท่านั้นที่จะทำงานได้อย่างถูกต้อง นอกจากนี้ ยังใช้ vecnorm (ซึ่งใช้สแควร์รูท) และการหาร ทั้งคู่มีการดำเนินการที่ค่อนข้างแพง (เมื่อเปรียบเทียบกับวิธีการที่แสดงไว้ที่นี่)
หากต้องการดูว่าจุดสามจุดเป็นเส้นตรงหรือไม่ คุณสามารถใช้กฎทางคณิตศาสตร์อย่างง่ายได้ สมมติว่าเรามีคะแนน p0, p1 และ p2 เวกเตอร์ตั้งแต่ p0 ถึง p1 และเวกเตอร์ตั้งแต่ p0 ถึง p2 เป็นพื้นฐานของรูปสี่เหลี่ยมด้านขนาน ซึ่งสามารถคำนวณพื้นที่ได้โดย ผลคูณไขว้ของเวกเตอร์สองตัว (ใน 2D ผลคูณไขว้เป็นที่เข้าใจกันว่าใช้ z=0 โดยเวกเตอร์ผลลัพธ์ที่มี x=0 และ y=0 มีเพียงค่า z เท่านั้นที่มีประโยชน์ ดังนั้น 2D ผลิตภัณฑ์ข้ามเราถือว่าจะสร้างค่าสเกลาร์) สามารถคำนวณได้ดังนี้:
v1 = p1 - p0;
v2 = p2 - p0;
x = v1(1)*v2(2) - v1(2)*v2(1);
x ซึ่งเป็นผลคูณไขว้จะเป็นศูนย์หากเวกเตอร์สองตัวขนานกัน ซึ่งหมายความว่าจุดสามจุดนั้นอยู่ในแนวเดียวกัน แต่การทดสอบความเท่าเทียมกับ 0 ต้องมีพิกัดความเผื่ออยู่บ้าง เนื่องจากเลขคณิตจุดลอยตัวไม่แน่นอน ฉันใช้ 1e-6 เป็นค่าเผื่อที่นี่ ใช้ค่าที่มีขนาดน้อยกว่าระยะห่างระหว่างจุดหลายจุด
เมื่อกำหนดชุดอินพุตของคะแนน p เราสามารถหาจุดมุมได้ด้วย:
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
โปรดทราบว่าการทดสอบผลิตภัณฑ์ข้ามนี้จะล้มเหลวหากจุดสองจุดติดต่อกันมีพิกัดที่เหมือนกัน (เช่น เวกเตอร์ตัวใดตัวหนึ่งมีความยาวเป็นศูนย์) จำเป็นต้องมีการทดสอบเพิ่มเติมหากข้อมูลอาจมีจุดซ้ำกัน
นี่คือผลลัพธ์ของทั้งสามวิธี ฉันได้สร้างรูปหลายเหลี่ยมที่มีพิกัดที่ไม่สำคัญและมีจุดยอดที่มีระยะห่างไม่เท่ากัน ฉันยังใส่ช่องว่างเริ่มต้น/สิ้นสุดไว้ตรงกลางของขอบตรงด้วย ลักษณะเหล่านี้มีจุดประสงค์เพื่อแสดงข้อบกพร่องของอีกสองวิธี
นี่คือรหัสที่ฉันใช้สร้างกราฟ:
% 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
person
Cris Luengo
schedule
10.04.2019
end-1,endและ1และด้วยend,1และ2- person Cris Luengo schedule 10.04.2019