Подключить точки и вычислить площадь

Question

Это мой первый пост, поэтому, пожалуйста, будьте добры.

У меня есть матрица с 3 ~ 10 координатами, и я хочу соединить эти точки, чтобы стать полигоном с максимальным размером.

Я попробовал fill() [1], чтобы создать сюжет, но как рассчитать площадь этого участка? Есть ли способ преобразования графика обратно в матрицу?

Что бы вы посоветовали мне?

Спасибо заранее!

[1]

 
x1 = [ 0.0, 0.5, 0.5 ]; 
y1 = [ 0.5, 0.5, 1.0 ]; 
fill (x1, y1, 'r'); 

[обновление]

Спасибо за ваш ответ MatlabDoug, но я думаю, что я не сформулировал мой вопрос достаточно ясно. Я хочу подключить все этих точек, чтобы стать полигоном с максимальным размером.

Любые новые идеи?

Answer 1

I второе предложение groovingandi попробовать все полигоны; вам просто нужно убедиться в правильности полигона (без самопересечений и т. д.).

Теперь, если вы хотите работать с большим количеством точек ... Как указал MatlabDoug, выпуклый корпус - это хорошее место для начала. Обратите внимание, что выпуклая оболочка дает многоугольник, площадь которого максимально возможная. Проблема, конечно, в том, что внутри корпуса могут быть точки, которые не являются частью многоугольника. Я предлагаю следующий жадный алгоритм, но я не уверен, гарантирует ли он максимальный полигон области.

Основная идея состоит в том, чтобы начать с выпуклого корпуса в качестве конечного полигона кандидата и вырезать треугольники, соответствующие неиспользуемым точкам, пока все точки не будут принадлежать окончательному многоугольнику. На каждом этапе удаляется наименьший возможный треугольник.

Given: Points P = {p1, ... pN}, convex hull H = {h1, ..., hM} 
     where each h is a point that lies on the convex hull. 
     H is a subset of P, and it is also ordered such that adjacent 
     points in the list of H are edges of the convex hull, and the 
     first and last points form an edge. 
Let Q = H 
while(Q.size < P.size) 
    % For each point, compute minimum area triangle 
    T = empty heap of triangles with value of their area 
    For each P not in Q 
     For each edge E of Q 
      If triangle formed by P and E does not contain any other point 
       Add triangle(P,E) with value area(triangle(P,E)) 
    % Modify the current polygon Q to carve out the triangle 
    Let t=(P,E) be the element of T with minimum area 
    Find the ordered pair of points that form the edge E within Q 
    (denote them Pa and Pb) 
    Replace the pair (Pa,Pb) with (Pa,E,Pb) 

Теперь, на практике вам не нужна куча для T, просто добавить данные в четыре списков: один для P, один для Па, один для Pb, и один для области. Чтобы проверить, находится ли точка в треугольнике, вам нужно только проверить каждую точку на линии, образующие стороны треугольника, и вам нужно только проверить точки, которые еще не были в Q. Наконец, чтобы вычислить площадь конечного многоугольника, вы можете триангулировать его (например, с помощью функции delaunay и суммировать области каждого треугольника в триангуляции), или вы можете найти область выпуклого корпуса и вычесть области треугольников по мере их вырезания.

Опять же, я не знаю, гарантирован ли этот жадный алгоритм найти максимальный многоугольник области, но я думаю, что он должен работать большую часть времени и, тем не менее, интересен.

Answer 2

x1 = rand(1,10) 
y1 = rand(1,10) 

vi = convhull(x1,y1) 
polyarea(x1(vi),y1(vi)) 

fill (x1(vi), y1(vi), 'r'); 
hold on 
plot(x1,y1,'.') 
hold off 

Что происходит здесь в том, что CONVHULL говорит нам, какие вершины, (VI) находятся на выпуклой оболочке (самый маленький полигон, который охватывает все точки). Зная, какие из них находятся на выпуклой оболочке, мы спрашиваем MATLAB для области с POLYAREA.

Наконец, мы используем команду FILL для рисования многоугольника, затем PLOT, чтобы поместить там точки для подтверждения.

Answer 3

Нахождение правильного порядка для очков - это трудная часть, как прокомментировал Амро. Достаточно ли этой функции?

function [idx] = Polyfy(x, y) 
% [idx] = Polyfy(x, y) 
% Given vectors x and y that contain pairs of points, find the order that 
% joins them into a polygon. fill(x(idx),y(idx),'r') should show no holes. 

%ensure column vectors 
if (size(x,1) == 1) 
    x = x'; 
end 
if (size(y,1) == 1) 
    y = y'; 
end 

% vectors from centroid of points to each point 
vx = x - mean(x); 
vy = y - mean(y); 
% unit vectors from centroid towards each point 
v = (vx + 1i*vy)./abs(vx + 1i*vy); 
vx = real(v); 
vy = imag(v); 

% rotate all unit vectors by first 
rot = [vx(1) vy(1) ; -vy(1) vx(1)]; 
v = (rot*[vx vy]')'; 

% find angles from first vector to each vector 
angles = atan2(v(:,2), v(:,1)); 
[angles, idx] = sort(angles); 
end 

Идея заключается в том, чтобы найти центр тяжести точек, а затем найти векторы из центроида в каждой точке. Вы можете думать об этих векторах как о сторонах треугольников. Многоугольник состоит из множества треугольников, где каждый вектор используется как «левый» и «правый» только один раз, и никакие векторы не пропускаются. Это сводится к упорядочению векторов на угол вокруг центра тяжести.

Я решил сделать это, нормализуя векторы на единицу длины, выбрав один из них в качестве вектора вращения и повернув остальные. Это позволило мне просто использовать atan2 для поиска углов. Вероятно, есть более быстрый и/или более элегантный способ сделать это, но я сбивал с толку идентификаторы триггеров. Наконец, сортировка этих углов дает правильный порядок для того, чтобы точки образовали желаемый многоугольник.

Это функция тестирования:

function [x, y] = TestPolyArea(N) 
x = rand(N,1); 
y = rand(N,1); 
[indexes] = Polyfy(x, y); 
x2 = x(indexes); 
y2 = y(indexes); 
a = polyarea(x2, y2); 
disp(num2str(a)); 
fill(x2, y2, 'r'); 
hold on 
plot(x2, y2, '.'); 
hold off 
end 

Вы можете получить некоторые довольно дикие картины, передавая N = 100 или около того!

Answer 4

Вы сказали, что у вас есть только 3 ... 10 точек для подключения. В этом случае я предлагаю вам просто взять все возможные комбинации, вычислить области с полиреей и взять самый большой.

Только в том случае, если ваше количество очков увеличивается или вам приходится часто его вычислять, так что время вычисления имеет значение, стоит потратить некоторое время на лучший алгоритм. Однако я думаю, что сложно найти алгоритм и доказать его полноту.