Форум программистов, компьютерный форум, киберфорум
Зосима
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  

Охват точек линией минимальной длинны в MATLAB

Запись от Зосима размещена 06.10.2021 в 09:38
Показов 3256 Комментарии 3

Как-то давно писал программку и вот она вновь пригодилась.
Может еще кому будет полезна)
Суть в чем? Есть несколько точек и нужно охватить их всех так, чтобы линия имела минимальный периметр.
По-научному такие линии называются "минимально выпуклая оболочка", почитать о них можно например на хабре. Собственно из этой статьи я и взял алгоритм.
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
clear, clc
% случайные точки
N = 10;
x = randn(N,1);
y = randn(N,1);
plot(x,y,'.') % рисуем исходные точки
hold on 
p = x + 1i*y; % переводим координаты в комплексный вид, чтобы было проще записывать
% берем самую левую точку - это первая точка оболочки z
z(1) = p( x == min(x) ); 
k = 1; % счетчик точек
% алгоритм Джарвиса
while z(end) ~= z(1) | k == 1 % пока не вернемся к начальной точке (или только первый шаг)
    % находим разности всех точек и текущей: p-z(k) 
    % вычисляем аргумент этих разностей (angle)
    % функция unwrap убирает разрывы:
    f1 = unwrap( angle( p-z(k) ) ) ;
    % игнорируем точки, у которых аргумент получился +/-пи, 
    % то есть они находятся позади, чтобы не возвращалось:
    f1( abs(f1)-pi==0 ) = NaN; 
    % сохраняем в массив z точку с минимальным аргументом:
    z(k+1) = p( f1==min(f1) );
    p( p==z(k+1) ) = []; % убираем из исходного набора эту точку
    k = k + 1; % увеличиваем счетчик
end
plot(z,'d-r') % рисуем оболочку
hold off
% периметр - это сумма (sum) отрезков оболочки,
% длинна каждого равна модулю (abs) разности соседних (diff) точек
P = sum( abs( diff(z) ) );
title(['Периметр P = ',num2str(P)]) % подписываем
Нажмите на изображение для увеличения
Название: 01.png
Просмотров: 458
Размер:	22.5 Кб
ID:	7167 Нажмите на изображение для увеличения
Название: 02.png
Просмотров: 431
Размер:	57.1 Кб
ID:	7168
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 3
Комментарии
  1. Старый комментарий
    Классный алгоритм! Мне правда приходилось решать несколько иную задачу. Заключить множество случайных точек в окружность наименьшего радиуса. А изначально все точки заключались в прямоугольник либо сразу вычислялся минимальный диаметр окружности... В общем программа работала как волк.
    Запись от wer1 размещена 06.10.2021 в 11:08 wer1 вне форума
  2. Старый комментарий
    Уважаемый Зосима,
    мне интересно вот что, как изменится алгоритм вашей программы, если допустим из 100 случайных точек надо заключить в "минимально выпуклую оболочку" например 90% всех точек? Плюс/минус одна точка значения не имеет. Или это совсем другая задача?
    Запись от wer1 размещена 06.10.2021 в 11:14 wer1 вне форума
  3. Старый комментарий
    Там разве нет готового?
    MATLAB convhull и convhulln
    Запись от Excalibur921 размещена 06.10.2021 в 12:46 Excalibur921 вне форума
 
Новые блоги и статьи
Размещения без повторений
VistaSV30 31.05.2025
Код возвращает список вариантов размещений A^{k}_{n}=\frac{n!}{(n-k)!} from itertools import permutations def pwr(k, n): # Размещение без повторений (Placement without repetition) if k. . .
Redis и Node.js с TypeScript - решения для высоконагруженных систем
Reangularity 31.05.2025
Redis (Remote Dictionary Server) — сверхбыстрое хранилище данных в памяти, способное обрабатывать операции за микросекунды. И что особенно важно для нас — с удивительно простым API. А теперь. . .
Unit-тестирование с моками в Go
golander 31.05.2025
Большинство разработчиков предпочитают тестировать код без использования моков. Например, при интеграции с Elasticsearch логичнее запустить контейнер локально и тестировать Go-код непосредственно с. . .
Как работать с PDF в C#
stackOverflow 31.05.2025
Нам приходится сталкиваться с PDF по разным причинам. Генерация счетов, создание отчетов, извлечение данных из загруженных пользователем документов, автоматизация рабочих процесов - это лишь верхушка. . .
Двухбуквенные коды стран в шифровании.
russiannick 31.05.2025
Человечество издревле манила возможность замены сочетаний букв вымышленными символами, делающие сообщение понятным только для посвещенных. Настала пора внести в это свой вклад. Двухбуквенные коды. . .
Мой опыт в исправлении ошибки приложения Boinc в части заряда батареи смартфона.
Programma_Boinc 31.05.2025
Мой опыт в исправлении ошибки приложения Boinc в части заряда батареи смартфона. Хотел бы поделиться опытом в исправлении ошибки приложения в части заряда батареи смартфона. Сразу скажу, что. . .
Добро пожаловать на конкурс PrimeGrid, посвященный 20-летию PrimeGrid
Programma_Boinc 31.05.2025
Добро пожаловать на конкурс PrimeGrid, посвященный 20-летию PrimeGrid: 5-дневный обобщенный поиск простых чисел Ферма n = 20 с 12 июня 20:20 UTC по 17 июня 20:20 UTC. 12 июня 2005 года. . .
Вероятность в шансы / Шансы в вероятность
VistaSV30 31.05.2025
# Шансы -> Вероятность def Chance_to_Probability(ch): def gcd(a, b): # НОД - нужен для упрощения значений шансов while b != 0: a, b = b, a % b return a. . .
FastAPI и Flask: Отличия, производительность и примеры использования
py-thonny 30.05.2025
Если вы разрабатываете веб-приложения на Python, вы наверняка слышали о Flask и FastAPI. Эти два фреймворка часто становятся предметом жарких дискуссий в сообществе разработчиков. И не без основания. . .
ML.NET и TensorFlow.NET: Умные приложения на C# с машинным обучением
stackOverflow 30.05.2025
Еще совсем недавно, когда речь заходила о машинном обучении, C# разработчики обреченно вздыхали и тянулись к Python. Мир искуственного интеллекта словно был огражден невидимым забором с табличкой. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
OSZAR »