devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

多目标蚁群算法路径规划（一）-----从数据设计到毕业论文系列_多目标蚁群算法‘

作者：凡人多烦事01 | 2024-03-20 04:40:05

赞

踩

多目标蚁群算法‘

多目标蚁群算法路径规划（-）------数据的预处理分析

系列前言（一定要看）

  • 本系列为总结本人近一年多关于启发式算法解决路径规划的相关内容。主要从以下几个主题内容进行系列写作1.常见的数据获取方式与处理过程、，2、算法的基础流程，3.常见算法改进，4.多目标排序、5.基于应用场景的改进、6.其他相关问题、7、批量运行测试数据本系列全程免费提供相关代码。
  • 本系列代码来源主要参考网上相关博客与文献、根据不同实际需求重构的代码。
  • 本文所有提供的代码与文字说明仅供参考，不作为商业目的。
  • 对内容有疑问或是错误部分可以留言或私信。
  • 有偿定制特定功能, qq:1602480875。价格范围80—500。（建议优先看完系列内容，尝试系列中的代码，这些都是免费且能解决大部分问题。），具体代码后续会以完整形式上传百度云。
    更新时间：2021年8月17日

1 本章内容说明

1. 本章主要对数据的获取方式
2. 获取数据的聚类分析
3. 聚类的数据输入与聚类过程
4. 基于网格划分用户归属
5. 不同数据类型之间的转化
5. 第二章地址（基础VRP算法与常见变体算法）

1.1 数据获取

路径的数据通常来源包括：

  1. 随机生成
    基于特定规则的随机生成，生成一个路径数据或者生成正定对称矩阵。要求生成的对称矩阵主对线上的元素为0或者一个尽量小的数eps。
    随机生成适用于生成数据适中且生成的数据有可行解的概率较大的条件，例如至少TSP问题。当路径规划涉及到多目标或是约束条件较多时使用随机生成数据往往会造成数据运行无解、求解困难、数据无法满足特定约束条件、调试困难等等问题。
%随机生成
 A = pascal(n) %n为矩阵大小 
 A_NEW=A-eye(size(A,1)).*diag(A); %使对角线上的元素为0

  • 1
  • 2
  • 3
  1. 路径数据空间坐标提取
    当要解决的问题偏实际应用场景时，需要获取真实的空间坐标或是实际的可行道路。此时可以通过一些开源的地图软件或者能提供地图API接口的应用。例如：百度地图、高德地图等。获取的数据主要包括三种类型
    1）特定空间中的平面坐标，
    2）读取经纬度坐标。
    3）软件标准坐标。
    针对3种坐标数据的获取过程可以浏览本博客另一篇文章。本文主要对经纬坐标的转化进行展示。首先输入经纬度坐标矩阵，利用球面坐标转化为平面坐标。计算平面坐标之间的欧式距离，生成路径矩阵。
mi=A;%输入路径经纬度
cc=zeros(size(mi,1));
    for j=1:size(mi,1)
        for i=j:size(mi,1)
            cc(j,i)=abs(6371004*acos((sin(deg2rad(mi(j,2)))*sin(deg2rad(mi(i,2)))+cos(deg2rad(mi(j,2)))*cos(deg2rad(mi(i,2)))*cos(deg2rad(mi(i,1)-mi(j,1))))));
            if i==j || cc(j,i)==0
                cc(j,i)=eps;
            end
            cc(i,j)=cc(j,i);
        end
    end

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  1. 通过特定的数据集获取
    当我们需要对比算法改进效率或者使用一个可以比较的结果差异的数据时，可以借助文献或者特定网站提供的数据集。
    公开的数据集需要自行查阅文献整理，针对不同路径规划问题有对应数据集，每个数据集都经过一系列测试。在使用这部分数据时需考虑当前设计的算法流程是否匹配，结果是否能达到预期要求。当结果差异较大时需要考虑是否重新设计初始参数与转移函数。
    数据集合网站例如：（待整理）公布可用的数据集http://w.cba.neu.edu/~msolomon/r101.htm。
    路径优化数据集说明网站：http://w.cba.neu.edu/~msolomon/home.htm
    http://w.cba.neu.edu/~msolomon/problems.htm
    网站种包含了常用的数据种类，并收集了不同文献针对这个数据集计算出的最优的结果。（遗憾的是数据优化结果只更新到2005年）
  2. 生成特定栅格图
    对于利用栅格绘制地图，搜索栅格内可行的路径点。如图生成的栅格图。
    在这里插入图片描述

1.2 数据的聚类

1.2.1 坐标数据的聚类过程

  1. 首先设置不同路径运行的起点位置，运用k_mean聚类坐标选择出适合配送中心点的位置。依次连接最外层的点展示包络的结果。如下图所示。
    对数据聚类主要分为两种部分：
    1）直接使用坐标的点进行聚类 通过坐标点聚类只反映出位置的坐标距离。
    2）考虑环境因素或其他条件 在一些路径情况种坐标距离并不能反映具体的位置特点，此时需要引入其他参考因素来进行聚类设置。比如：所处地理环境，装箱容量、运属的物品种类、运算需要的时间约束等。
    聚类过程种初始点选取有时也是决定聚类结果好坏的关键因素，因此在进行聚类前可以适当预估起始点的位置。除了kmeans聚类也可以采取其他聚类算法。

在这里插入图片描述
2) 基于voronoi图聚类不同客户点的分配（8.17更新）

1.2.2 数据的其他处理

  1. 路径规划的使用的数据通常包括（并非所有数据都有）路径信息、货物点可接受的时间信息、货物点载重信息、处理货物的行为、货物运输过程的损失情况、货物的种类特点、车辆种类信息。
  2. 例如：冷链运输过程中不同运输点货物需求的车辆种类、车辆的数目明显差异性 。此时在聚类过程中就需要把地点的货物需求作为特征进行聚类。此时聚类特征的处理方法可以分为3种特点考虑：
    1）采用离散的变量作为标记，不同货物点分配不同种类。
    2）采用连续变量进行考虑，根据货物点的比例，设定分类标签可以为连续变量。
    3）根据需求特定自行定值。
  3. 车辆在设定针对于同种货物同时存在在存取行为时，数据需要预先计算是否存在可行解满足保证到每个点都满足货物需求。如果寻找解比较困难，可以通过设定初始载货量来避免货物点错误情况。或者设置约束禁止产生此种路径。（目前接触到网上或是文献中都较少考虑此问题：大多只考虑送货或接货问题，对同时存在情况的分析比较少。在后续的系列会提供一个简单的解决方案。）。

1.2.3 不同需求的数据的转化

  1. 博主在长期接触不同客户需求的内容过程中观察到，不同专业刚开始在进行路径规划相关问题分析时缺少对问题本质的一个了解/思考。解决问题时通常急于探索课题的特异性。
  2. 例如：多类型路径的运输优化组合（海运、铁运、公路），客户觉得这个问题需要设计一个新的算法才能解决或者需要复杂的程序过程才能比较好分析。其实只要理解路径规划本身只是一个排序寻优过程，把不同类型路径长度映射到一个单位长度就可以用常规算法解决。1单位海运=10单位标准长度，1单位铁运=5单位标准长度，通过数据的简单转化就能很快着手准备。
  3. 例如： 车辆寻找规律时间内最有价值的货物运输道路。这个可以转化为载重约束过程，将时间看作车辆初始载重，每到一个货物点消耗货物等价于时间被消耗，当时间消耗完就需要返回中心重新出发。以此来寻找价值最高的集合。但此时需要每次计算道路的价值作为状态转移和寻有判段标准。
    4.例如：

聚类算法

%% 对最优仓库位置进行选择
%% 读取坐标的位置
clear
% [~, ~, raw] = xlsread('C:\Users\huang\Desktop\车车联动数据.xls','Sheet1','A1:B43');
% %% 创建输出变量
% S3 = reshape([raw{:}],size(raw));
close all
% %% 清除临时变量
% clearvars raw;
% 簇心数目k
% c101=importdata('c307.txt');
  c101=xlsread('c310.xlsx'); % 读取表格
S3=c101(2:end,2:3);
K =3;
data=S3; %  直接存储到data变量中
x = data(1:size(data,1),1);
y = data(1:size(data,1),2);

% 绘制数据，2维散点图
% x,y: 要绘制的数据点  20:散点大小相同，均为20  'blue':散点颜色为蓝色
n=length(x);
c = linspace(1,10,length(x));
s = scatter(x, y,20,c, 'blue');
title('送货地点：蓝圈初始聚集点：红点');
text(x,y,arrayfun(@(x)['  ' num2str(x)],1:n,'UniformOutput',0))


% 初始化簇心
sample_num = size(data, 1);      % 样本数量
sample_dimension = size(data, 2); % 每个样本特征维度


% 暂且手动指定簇心初始位置
clusters = zeros(K, sample_dimension);
%   clusters(1,:) = [86,51];
%   clusters(2,:) =[62,40];
%   clusters(3,:) = [35,7];
%  clusters(4,:) =S3(41,:);
%  clusters(5,:) =S3(42,:);
% 簇心赋初值：计算所有数据的均值，并将一些小随机向量加到均值上
minVal = min(data); % 各维度计算最小值
maxVal = max(data);% 各维度计算最大值
for i_1=1:K
    clusters(i_1, :) = minVal + (maxVal - minVal) * rand();
end

hold on; % 在上次绘图（散点图）基础上，准备下次绘图
% 绘制初始簇心
scatter(clusters(:,1), clusters(:,2), 'red', 'filled'); % 实心圆点，表示簇心初始位置
text(clusters(:,1),clusters(:,2),'中心点')
c = zeros(sample_num, 1); % 每个样本所属簇的编号

PRECISION = 0.001;


iter = 100; % 假定最多迭代100次
% Stochastic Gradient Descendant 的K-means，也就是Competitive Learning版本
basic_eta = 1;  % learning rate
for i_1=1:iter
    pre_acc_err = 0; % 上一次迭代中，累计误差
    acc_err = 0;  % 累计误差
    for j=1:sample_num
        x_j = data(j, :);     % 取得第j个样本数据，这里体现了stochastic性质
        
               % 所有簇心和x计算距离，找到最近的一个（比较簇心到x的模长）
        gg = repmat(x_j, K, 1);
        gg = gg - clusters;
        tt = arrayfun(@(n) norm(gg(n,:)), (1:K)');
        [minVal, minIdx] = min(tt);
        
       % 更新簇心：把最近的簇心(winner)向数据x拉动。 eta为学习率.
        eta = basic_eta/i_1;
        delta = eta*(x_j-clusters(minIdx,:));
        clusters(minIdx,:) = clusters(minIdx,:) + delta;
        acc_err = acc_err + norm(delta);
        c(j)=minIdx; 
    end
    
    if(rem(i_1,30) ~= 0)
        continue
    end
    figure;
    f = scatter(x, y, 20, 'blue');
    text(x,y,arrayfun(@(x)['  ' num2str(x)],1:n,'UniformOutput',0))
    hold on;
    scatter(clusters(:,1), clusters(:,2), 'filled'); % 实心圆点，表示簇心初始位置
    text(clusters(:,1),clusters(:,2),'中心点')
    title(['第', num2str(i_1), '次迭代']);
    if (abs(acc_err-pre_acc_err) < PRECISION)
        disp(['收敛于第', num2str(i_1), '次迭代']);
        break;
    end
    
    disp(['累计误差：', num2str(abs(acc_err-pre_acc_err))]);
    pre_acc_err = acc_err;
end
hold on
hold on;
% S3=cc_1;
% scatter(S3(39:43,1), S3(39:43,2), 'd'); % 实心圆点，表示簇心初始位置
% x_1=S3(39:43,1);
% n_1=length(x_1);
% %   text(S3(39:43,1), S3(39:43,2),arrayfun(@(x_1)[' 仓库' num2str(x_1)],1:n_1,'UniformOutput',0))
% title('最终聚类结果展示');
% disp('done');
% cc_1_1=zeros(1,5);
% for i_1=1:5
%     cc_1_1(i_1)=sqrt(sum((clusters(1, :)-S3(38+i_1,:)).^2,2)); %%与每个坐标的相对距离
% end

% c101=importdata('c307.txt');
c104=c101(2:end,:);
% figure 
 figure;
    f = scatter(x, y, 20, 'blue');
    text(x,y,arrayfun(@(x)['  ' num2str(x)],1:n,'UniformOutput',0))
    hold on;
    scatter(clusters(:,1), clusters(:,2), 'filled'); % 实心圆点，表示簇心初始位置
    text(clusters(:,1),clusters(:,2),'中心点')
for i_1=1:K
    [n,m]=find(c==i_1);
    c104_x{i_1}=c104(n,:);
    t=c104(n,2:3);
    samplef(t) %绘制包络线
    hold on
    xlabel('车辆空间位置X')
    ylabel('车辆空间位置Y')
    title(['车辆路径聚类数据结果']);
    % 保存数据
    fid=fopen(strcat('c104_',num2str(i_1),'.txt'),'w');%鍐欏叆鏂囦欢璺緞
    [r,c_txt]=size(c104_x{i_1});            % 寰楀埌鐭╅樀鐨勮鏁板拰鍒楁暟
    for i=1:r
        for j=1:c_txt
            fprintf(fid,'%f\t',c104_x{i_1}(i,j));
        end
        fprintf(fid,'\r\n');
    end
    fclose(fid);
    clear a_L_L
     a_L_L=importdata(strcat('c104_',num2str(i_1),'.txt'));
     xlswrite(strcat('c104_',num2str(i_1),'.xlsx'),a_L_L)
end
saveas(gcf,'聚类结果.bmp')


  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144

网格划分程序：

%% 对最优仓库位置进行选择
%% 读取坐标的位置
clear
据.xls','Sheet1','A1:B43');
% %% 创建输出变量
% S3 = reshape([raw{:}],size(raw));
% close all
% %% 清除临时变量
% clearvars raw;
% 簇心数目k
c101=importdata('c307.txt');
%   c101=xlsread('c310.xlsx'); % 读取表格
S3=c101(2:end,2:7);
K =3;
data=S3; %  直接存储到data变量中
x = data(1:size(data,1),1);
y = data(1:size(data,1),2);
%顾客坐标
xdot=[x(4:end,1),y(4:end,1)];
xdot=mapminmax(xdot',1,0)';
col=[0,0.4,0];
vonor(xdot,col)
hold on
%仓库坐标
xdot=[x(1:3,1),y(1:3,1)];
xdot=mapminmax(xdot',1,0)';
col=[0.8,0.5,0.2];
vonor(xdot,col)

  • 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
function vonor(xdot,col)
% clear
% N=100;
N = size(xdot,1);
% %点随机
% 
% xdot=rand(N,2);
%点按圆形随机
% r=rand(N,1).^0.3;
% theta=rand(N,1)*2*pi;
% xdot=[r.*cos(theta),r.*sin(theta)];
%点按双行随机
% x=rand(N,1);
% y=[randn(N/2,1)/5+0.5;randn(N/2,1)/5-0.5];
% y(y>1)=1;y(y<-1)=-1;
% y=(y+1)/2.1;
% xdot=[x,y];

%点按规则矩形加抖动
% [X1,X2]=meshgrid(0:1/sqrt(N):1-1/sqrt(N));
% xdot=zeros(N,2);
% xdot(:,1)=X1(1:end)'+1/sqrt(N)/2*rand(N,1);
% xdot(:,2)=X2(1:end)'+1/sqrt(N)/2*rand(N,1);

%点按随机三角加抖动
% NN=20;
% X1=[];X2=[];
% for j=1:NN
%      if mod(j,2)==0
%          X1=[X1;(0:1/NN/sqrt(3)*2:1-0/NN/sqrt(3)*2)'];
%          X2=[X2;ones(length(0:1/NN/sqrt(3)*2:1-0/NN/sqrt(3)*2),1)*(j-1)/NN];
%      else
%          X1=[X1;(0:1/NN/sqrt(3)*2:1-1/NN/sqrt(3)*2)'+1/NN/sqrt(3)];
%          X2=[X2;ones(length(0:1/NN/sqrt(3)*2:1-1/NN/sqrt(3)*2),1)*(j-1)/NN];
%      end
% end
% N=size(X1,1);
% xdot=[X1+rand(N,1)*1.2/NN/sqrt(3),X2+rand(N,1)*1.2/NN/2];


%1Delaulay三角形的构建

%整理点，遵循从左到右，从上到下的顺序
xdot=sortrows(xdot,[1 2]);

%画出最大包含的三角形
xmin=min(xdot(:,1));xmax=max(xdot(:,1));
ymin=min(xdot(:,2));ymax=max(xdot(:,2));
bigtri=[(xmin+xmax)/2-(xmax-xmin)*1.5,ymin-(xmax-xmin)*0.5;...
    (xmin+xmax)/2,ymax+(ymax-ymin)+(xmax-xmin)*0.5;...
   (xmin+xmax)/2+(xmax-xmin)*1.5,ymin-(xmax-xmin)*0.5];

xdot=[bigtri;xdot];%点集
edgemat=[1 2 xdot(1,:) xdot(2,:);...
    2 3 xdot(2,:) xdot(3,:);1 3 xdot(1,:) xdot(3,:)];%边集，每个点包含2个点，4个坐标值
trimat=[1 2 3];%三角集,每个三角包含3个点
temp_trimat=[1 2 3];
for j=4:N+3
    pointtemp=xdot(j,:);%循环每一个点
    deltemp=[];%初始化删除temp_trimat的点
    temp_edgemat=[];%初始化临时边
    for k=1:size(temp_trimat,1)%循环每一个temp_trimat的三角形
        panduan=whereispoint(xdot(temp_trimat(k,1),:),...
            xdot(temp_trimat(k,2),:),xdot(temp_trimat(k,3),:),pointtemp);%判断点在圆内0、圆外1、圆右侧2
        switch panduan
            case 0
                %点在圆内
                %则该三角形不为Delaunay三角形
                temp_edge=maketempedge(temp_trimat(k,1),temp_trimat(k,2),temp_trimat(k,3),j,xdot);%把三条边暂时存放于临时边矩阵
                temp_edgemat=[temp_edgemat;temp_edge];
                deltemp=[deltemp,k];
                ;
            case 1
                %点在圆外，pass
                ;
            case 2
                %点在圆右
                %则该三角形为Delaunay三角形，保存到triangles
                trimat=[trimat;temp_trimat(k,:)];%添加到正式三角形中
                deltemp=[deltemp,k];
                %并在temp里去除掉
                %别忘了把正式的边也添加进去
                edgemat=[edgemat;makeedge(temp_trimat(k,1),temp_trimat(k,2),temp_trimat(k,3),xdot)];%遵循12,13,23的顺序
                edgemat=unique(edgemat,'stable','rows');
                
        end

    
    %三角循环结束    
    end
    
    
    
    %除去上述步骤中的临时三角形
    temp_trimat(deltemp,:)=[];
    temp_trimat(~all(temp_trimat,2),:)=[];
    %对temp_edgemat去重复
    temp_edgemat=unique(temp_edgemat,'stable','rows');
    %将edge buffer中的边与当前的点进行组合成若干三角形并保存至temp triangles中
    temp_trimat=[temp_trimat;maketemptri(temp_edgemat,xdot,j)];
    k=k;


%点循环结束
end

%合并temptri
trimat=[trimat;temp_trimat];
edgemat=[edgemat;temp_edgemat];
%删除大三角形
deltemp=[];
for j=1:size(trimat,1)
    if ismember(1,trimat(j,:))||ismember(2,trimat(j,:))||ismember(3,trimat(j,:))
        deltemp=[deltemp,j];
    end
end
trimat(deltemp,:)=[];
edgemat=[trimat(:,[1,2]);trimat(:,[2,3]);trimat(:,[3,1])];
edgemat=sort(edgemat,2);
edgemat=unique(edgemat,'stable','rows');


temp_edgemat=[];
temp_trimat=[];

% figure(1)
% hold on
% plot(xdot(:,1),xdot(:,2),'ko')
% for j=1:size(trimat,1)
%     plot([xdot(trimat(j,1),1),xdot(trimat(j,2),1)],[xdot(trimat(j,1),2),xdot(trimat(j,2),2)],'k-')
%     plot([xdot(trimat(j,1),1),xdot(trimat(j,3),1)],[xdot(trimat(j,1),2),xdot(trimat(j,3),2)],'k-')
%     plot([xdot(trimat(j,3),1),xdot(trimat(j,2),1)],[xdot(trimat(j,3),2),xdot(trimat(j,2),2)],'k-')
% end
% hold off
% xlim([0,1]);ylim([0,1]);

%凸包监测
%思路是先找出边缘点（三角形只有1个或2个的），顺便整出一个三角形相互关系图，以后用。
%然后顺时针，依次隔一个点连接出一条线段，如果这个和之前的线段相交，则不算；如果不交，则记录出三角形
%更新完了以后，再监测一遍，直到没有新的为止。

t_w=0;
while t_w==0
    [~,border_point,~]=makebordertri(trimat);
    border_point=[border_point;border_point(1,:)];
    temp_edgemat=[];
    temp_trimat=[];
    for j=1:size(border_point,1)-1
        tempboderedge=[border_point(j,1),border_point(j+1,2)];
        tempboderdot=border_point(j,2);
        %寻找带tempboderdot的所有边
        tempdotex=edgemat(logical(sum(edgemat==tempboderdot,2)),:);
        %删除相邻边
        tempdotex(ismember(tempdotex,[tempboderdot,tempboderedge(1)],'rows'),:)=[];
        tempdotex(ismember(tempdotex,[tempboderedge(1),tempboderdot],'rows'),:)=[];
        tempdotex(ismember(tempdotex,[tempboderdot,tempboderedge(2)],'rows'),:)=[];
        tempdotex(ismember(tempdotex,[tempboderedge(2),tempboderdot],'rows'),:)=[];
        %检测tempdotex是否为空，如果是证明不用相连
        t_N=size(tempdotex,1);
        t_t=0;
        if t_N>0
            %依次检测是否相交，只要有一个相交就不算；如果都不想交，则相连
            for k=1:t_N
                if tempdotex(k,1)==tempboderdot
                    t_xdotno4=tempdotex(k,2);
                else
                    t_xdotno4=tempdotex(k,1);
                end
                tt_xdotno4=xdot(t_xdotno4,:)-xdot(tempboderdot,:);
                xdotno4=xdot(tempboderdot,:)+tt_xdotno4/sqrt(sum(tt_xdotno4.^2))*(sqrt((xmax-xmin)^2+(ymax-ymin)^2));
                panduan=crossornot(xdot(tempboderedge(1),:),xdot(tempboderedge(2),:),xdot(tempboderdot,:),xdotno4);
                if panduan==1
                    t_t=t_t+1;
                    break
                end
            end
            %t_t大于0说明有相交的线,略过
            if t_t==0
                temp_edgemat=[temp_edgemat;tempboderedge];
                temp_trimat=[temp_trimat;[tempboderedge,tempboderdot]];
                break
            end
        end
    end
    trimat=[trimat;temp_trimat];
    edgemat=[edgemat;temp_edgemat];
    %删除重复的三角形
    trimat=sort(trimat,2);
    trimat=unique(trimat,'stable','rows');
    if j==size(border_point,1)-1
        t_w=1;
    end
end


% figure(2)
% hold on
% % plot(xdot(:,1),xdot(:,2),'ko')
% for j=1:size(trimat,1)
%     plot([xdot(trimat(j,1),1),xdot(trimat(j,2),1)],[xdot(trimat(j,1),2),xdot(trimat(j,2),2)],'k-')
%     plot([xdot(trimat(j,1),1),xdot(trimat(j,3),1)],[xdot(trimat(j,1),2),xdot(trimat(j,3),2)],'k-')
%     plot([xdot(trimat(j,3),1),xdot(trimat(j,2),1)],[xdot(trimat(j,3),2),xdot(trimat(j,2),2)],'k-')
% end
% hold off
% xlim([0,1]);ylim([0,1]);

%2泰森多边形的建立步骤
%求每个三角形的外接圆圆心

trimatcenter=zeros(size(trimat,1),2);
for j=1:size(trimat,1)
    [a,b,~]=maketricenter(xdot(trimat(j,1),:),xdot(trimat(j,2),:),xdot(trimat(j,3),:));
    trimatcenter(j,:)=[a,b];
end

%求三角形的相邻三角形个数
[border_trimat,border_point,trimat_con]=makebordertri(trimat);
Thi_edge1=[];
for j=1:size(trimat,1)
    tempedge=[];
    %第一个相邻三角形
    if trimat_con(j,1)~=0
        tempedge=[tempedge;[j,trimat_con(j,1)]];
    end
    %第二个相邻三角形
    if trimat_con(j,2)~=0
        tempedge=[tempedge;[j,trimat_con(j,2)]];
    end
    %第三个相邻三角形
    if trimat_con(j,3)~=0
        tempedge=[tempedge;[j,trimat_con(j,3)]];
    end
    Thi_edge1=[Thi_edge1;tempedge];
end

%绘制非边缘泰勒多边形
% figure
Thi_edge1=unique(Thi_edge1,'stable','rows');
% xlim([0,1]);ylim([0,1]);
hold on
for j=1:size(Thi_edge1,1)
    plot(trimatcenter([Thi_edge1(j,1),Thi_edge1(j,2)],1),trimatcenter([Thi_edge1(j,1),Thi_edge1(j,2)],2),'color',[0,0.4,0])
end



%绘制边缘泰勒多边形
%先逐个边试探，如果中心点在三角内，则做中心-边缘延长线
%如果中心点在三角外，如果在屏幕外，忽略，如果在屏幕内，做边缘-中心延长线

for j=1:size(border_point,1)
    %先找到边对应的三角
    temp_trimat=border_trimat(sum(border_trimat==border_point(j,1),2)+sum(border_trimat==border_point(j,2),2)==2,:);
    %判断中心点是否在三角形内
    [t_x1,t_y1,~]=maketricenter(xdot(temp_trimat(1),:),xdot(temp_trimat(2),:),xdot(temp_trimat(3),:));%求中心
    
    panduan=pointintriangle(xdot(temp_trimat(1),:),xdot(temp_trimat(2),:),xdot(temp_trimat(3),:),[t_x1,t_y1]);
    %求边的中点
    t_x2=(xdot(border_point(j,1),1)+xdot(border_point(j,2),1))/2;
    t_y2=(xdot(border_point(j,1),2)+xdot(border_point(j,2),2))/2;
    if panduan==1
        %做中心-边缘的延长线
        %这里用到了边缘在01这个条件
        t_xy3=[t_x1,t_y1]+[t_x2-t_x1,t_y2-t_y1]*sqrt(2)/sqrt((t_x2-t_x1)^2+(t_y2-t_y1)^2);
        plot([t_x1,t_xy3(1)],[t_y1,t_xy3(2)],'color',col)
    elseif ~(t_x1<0||t_x1>1||t_y1<0||t_y1>1)
        %判断点是否在边与边框的三角内，如果在，做中心的延长线
        %如果不在，做中心-边缘的延长线
        %或者改成判断点是否在多边形内
        
        panduan2=pointinmutiangle(xdot,[border_point(1,1);border_point(:,2)],[t_x1,t_y1]);
        if panduan2==1
            t_xy3=[t_x1,t_y1]+[t_x2-t_x1,t_y2-t_y1]*sqrt(2)/sqrt((t_x2-t_x1)^2+(t_y2-t_y1)^2);
            plot([t_x1,t_xy3(1)],[t_y1,t_xy3(2)],'color',col)
        else
            t_xy3=[t_x1,t_y1]+[t_x1-t_x2,t_y1-t_y2]*1/sqrt((t_x2-t_x1)^2+(t_y2-t_y1)^2);
            plot([t_x1,t_xy3(1)],[t_y1,t_xy3(2)],'color',col)
        end
    end
end

scatter(xdot(:,1),xdot(:,2),5,col,'filled')
hold off







%判断点在三角形外接圆的哪个部分
function panduan=whereispoint(xy1,xy2,xy3,xy0)
%判断点在三角形外接圆的哪个部分
[a,b,r2]=maketricenter(xy1,xy2,xy3);
x0=xy0(1);y0=xy0(2);
if a+sqrt(r2)<x0
    %x0在圆的右侧
    panduan=2;
elseif (x0-a)^2+(y0-b)^2<r2
    %x0在圆内
    panduan=0;
else
    %在圆外
    panduan=1;
end
end

%做出三角形三点与内部1点之间的线段
function temp_edge=maketempedge(dot1,dot2,dot3,dot0,xdot)
%做出连接点与三角形之间的线
%每行包含2个点，4个坐标值，共3行
%xy1和xy0组成线段
temp_edge=zeros(3,6);
if xdot(dot1,1)<xdot(dot0,1)
    temp_edge(1,:)=[dot1,dot0,xdot(dot1,:),xdot(dot0,:)];
elseif xdot(dot1,1)==xdot(dot0,1)
    if xdot(dot1,2)<xdot(dot0,2)
        temp_edge(1,:)=[dot1,dot0,xdot(dot1,:),xdot(dot0,:)];
    else
        temp_edge(1,:)=[dot0,dot1,xdot(dot0,:),xdot(dot1,:)];
    end
else
    temp_edge(1,:)=[dot0,dot1,xdot(dot0,:),xdot(dot1,:)];
end
%xy2和xy0组成线段
if xdot(dot2,1)<xdot(dot0,1)
    temp_edge(2,:)=[dot2,dot0,xdot(dot2,:),xdot(dot0,:)];
elseif xdot(dot2,1)==xdot(dot0,1)
    if xdot(dot2,2)<xdot(dot0,2)
        temp_edge(2,:)=[dot2,dot0,xdot(dot2,:),xdot(dot0,:)];
    else
        temp_edge(2,:)=[dot0,dot2,xdot(dot0,:),xdot(dot2,:)];
    end
else
    temp_edge(2,:)=[dot0,dot2,xdot(dot0,:),xdot(dot2,:)];
end
%xy3和xy0组成线段
if xdot(dot3,1)<xdot(dot0,1)
    temp_edge(3,:)=[dot3,dot0,xdot(dot3,:),xdot(dot0,:)];
elseif xdot(dot3,1)==xdot(dot0,1)
    if xdot(dot3,2)<xdot(dot0,2)
        temp_edge(3,:)=[dot3,dot0,xdot(dot3,:),xdot(dot0,:)];
    else
        temp_edge(3,:)=[dot0,dot3,xdot(dot0,:),xdot(dot3,:)];
    end
else
    temp_edge(3,:)=[dot0,dot3,xdot(dot0,:),xdot(dot3,:)];
end

end

%做出一些列固定点发散的线段外点组成的三角形
function temp_trimat=maketemptri(temp_edgemat,xdot,dot0)
%将edge buffer中的边与当前的点进行组合成若干三角形
%temp_edgemat是新边，x是中心点
%思路是计算各个边对应角度，然后排序相连

A=temp_edgemat(:,1:2);
pointline=A(A~=dot0);
N=length(pointline);
pointaxe=xdot(pointline,:);
img_pointaxe=pointaxe(:,1)+1i*pointaxe(:,2);
d_img_pointaxe=img_pointaxe-xdot(dot0,1)-1i*xdot(dot0,2);
angle_d_img_pointaxe=angle(d_img_pointaxe);
[~,index]=sort(angle_d_img_pointaxe);
index=[index;index(1)];%排序，然后依次串起来
temp_trimat=zeros(N,3);
for j=1:N
    temp_trimat(j,:)=[pointline(index(j)),pointline(index(j+1)),dot0];
end


end

%将三个点构成3条边
function edgemat=makeedge(dot1,dot2,dot3,xdot)
%将dot1 2 3这三个点构成三条边
%每行包含2个点，4个坐标值，共3行
edgemat=zeros(3,6);
%点12
if xdot(dot1,1)<xdot(dot2,1)
    edgemat(1,:)=[dot1,dot2,xdot(dot1,:),xdot(dot2,:)];
elseif xdot(dot1,1)==xdot(dot2,1)
    if xdot(dot1,2)<xdot(dot2,2)
        edgemat(1,:)=[dot1,dot2,xdot(dot1,:),xdot(dot2,:)];
    else
        edgemat(1,:)=[dot2,dot1,xdot(dot2,:),xdot(dot1,:)];
    end
else
    edgemat(1,:)=[dot2,dot1,xdot(dot2,:),xdot(dot1,:)];
end
%点13
if xdot(dot1,1)<xdot(dot3,1)
    edgemat(2,:)=[dot1,dot3,xdot(dot1,:),xdot(dot3,:)];
elseif xdot(dot1,1)==xdot(dot3,1)
    if xdot(dot1,2)<xdot(dot3,2)
        edgemat(2,:)=[dot1,dot3,xdot(dot1,:),xdot(dot3,:)];
    else
        edgemat(2,:)=[dot3,dot1,xdot(dot3,:),xdot(dot1,:)];
    end
else
    edgemat(2,:)=[dot3,dot1,xdot(dot3,:),xdot(dot1,:)];
end
%点23
if xdot(dot3,1)<xdot(dot2,1)
    edgemat(3,:)=[dot3,dot2,xdot(dot3,:),xdot(dot2,:)];
elseif xdot(dot3,1)==xdot(dot2,1)
    if xdot(dot3,2)<xdot(dot2,2)
        edgemat(3,:)=[dot3,dot2,xdot(dot3,:),xdot(dot2,:)];
    else
        edgemat(3,:)=[dot2,dot3,xdot(dot2,:),xdot(dot3,:)];
    end
else
    edgemat(3,:)=[dot2,dot3,xdot(dot2,:),xdot(dot3,:)];
end
% edgemat
end

%求三角形外接圆圆心
function [a,b,r2]=maketricenter(xy1,xy2,xy3)
x1=xy1(1);y1=xy1(2);
x2=xy2(1);y2=xy2(2);
x3=xy3(1);y3=xy3(2);
a=((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2.0*((x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)));
b=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1))/(2.0*((y3-y1)*(x2-x1)-(y2-y1)*(x3-x1)));
r2=(x1-a)*(x1-a)+(y1-b)*(y1-b);
end

%求边缘三角形
function [border_trimat,border_point,trimat_con]=makebordertri(trimat)
N=size(trimat,1);
border_trimat=[];
border_point=[];
trimat_con=zeros(N,3);
for j=1:N
    %tempborder_trimat=zeros(3,3);
    temptri=trimat(j,:);
    %计算temptri中12点边对应的三角形有哪些
    edgetrimat=find(sum(trimat==temptri(1),2)+sum(trimat==temptri(2),2)==2);
    edgetrimat(edgetrimat==j)=[];
    if size(edgetrimat,2)==0
        %这个边没有三角形相连，是个临边。
        border_point=[border_point;[temptri(1),temptri(2)]];
        
    elseif size(edgetrimat,2)==1
        %这个边没有三角形相连，是个临边。
        %tempborder_trimat(1,:)=trimat(edgetrimat,:);%记录三角形三点坐标
        trimat_con(j,1)=edgetrimat;%trimat_con记录上相邻三角形
    end
    
    %计算temptri中23点边对应的三角形有哪些
    edgetrimat=find(sum(trimat==temptri(2),2)+sum(trimat==temptri(3),2)==2);
    edgetrimat(edgetrimat==j)=[];
    if size(edgetrimat,2)==0
        border_point=[border_point;[temptri(2),temptri(3)]];
        
    elseif size(edgetrimat,2)==1
        %tempborder_trimat(2,:)=trimat(edgetrimat,:);
        trimat_con(j,2)=edgetrimat;
    end
    
    %计算temptri中31点边对应的三角形有哪些
    edgetrimat=find(sum(trimat==temptri(3),2)+sum(trimat==temptri(1),2)==2);
    edgetrimat(edgetrimat==j)=[];
    if size(edgetrimat,2)==0
        border_point=[border_point;[temptri(3),temptri(1)]];
        
    elseif size(edgetrimat,2)==1
        %tempborder_trimat(3,:)=trimat(edgetrimat,:);
        trimat_con(j,3)=edgetrimat;
    end
    
    %tempborder_trimat(all(tempborder_trimat==0, 2),:)=[];%删除0行
    if ~all(trimat_con(j,:))
        %如果边缘三角少于3个,就添加
        border_trimat=[border_trimat;temptri];
    end

end

%把边首尾排序一遍,输出border_point
for j=1:size(border_point,1)-1
    border_pointtemp=find(sum(border_point==border_point(j,2),2)==1);
    border_pointtemp(border_pointtemp==j)=[];
    border_point([j+1,border_pointtemp],:)=border_point([border_pointtemp,j+1],:);
    if border_point(j,2)==border_point(j+1,2)
        border_point(j+1,[1,2])=border_point(j+1,[2,1]);
    end
end

end


%判断两个线段是否相交
function panduan=crossornot(l1xy1,l1xy2,l2xy1,l2xy2)
l1x1=l1xy1(1);l1y1=l1xy1(2);
l1x2=l1xy2(1);l1y2=l1xy2(2);
l2x1=l2xy1(1);l2y1=l2xy1(2);
l2x2=l2xy2(1);l2y2=l2xy2(2);
%先快速判断
if    (max(l2x1,l2x2)<min(l1x1,l1x2))||(max(l2y1,l2y2)<min(l1y1,l1y2))||...
        (max(l1x1,l1x2)<min(l2x1,l2x2))||(max(l1y1,l1y2)<min(l2y1,l2y2))
    %如果判断为真，则一定不会相交
    panduan=0;
else
    %如果判断为假，进一步差积判断
    if ((((l1x1-l2x1)*(l2y2-l2y1)-(l1y1-l2y1)*(l2x2-l2x1))*...
        ((l1x2-l2x1)*(l2y2-l2y1)-(l1y2-l2y1)*(l2x2-l2x1))) > 0 ||...
        (((l2x1-l1x1)*(l1y2-l1y1)-(l2y1-l1y1)*(l1x2-l1x1))*...
        ((l2x2-l1x1)*(l1y2-l1y1)-(l2y2-l1y1)*(l1x2-l1x1))) > 0)
        %如果判断为真，则不会相交
        panduan=0;
    else
        panduan=1;
    end
end
end

%两个向量做差积
function t=crossdot(xy1,xy2)
x1=xy1(1);y1=xy1(2);
x2=xy2(1);y2=xy2(2);
t=x1*y2-y1*x2;
end

%点是否在三角形内
function panduan=pointintriangle(xy1,xy2,xy3,xy0)
x1=xy1(1);y1=xy1(2);
x2=xy2(1);y2=xy2(2);
x3=xy3(1);y3=xy3(2);
x0=xy0(1);y0=xy0(2);
PA=[x1-x0,y1-y0];PB=[x2-x0,y2-y0];PC=[x3-x0,y3-y0];
%利用差积同正或同负号来判断是否在三角内
t1=crossdot(PA,PB);
t2=crossdot(PB,PC);
t3=crossdot(PC,PA);
if abs(sign(t1)+sign(t2)+sign(t3))==3
    panduan=1;
else
    panduan=0;
end

end

%点是否在多边形内
function panduan=pointinmutiangle(xdot,d_no,xy0)
%d_no符合12341的格式，收尾相连
Ndot=xdot(d_no,:);
PN=[Ndot(:,1)-xy0(1),Ndot(:,2)-xy0(2)];
tn=zeros(length(d_no)-1,1);
for j=1:length(d_no)-1
    tn(j)=crossdot(PN(j,:),PN(j+1,:));
end
%利用差积同正或同负号来判断是否在三角内

if abs(sum(sign(tn)))==length(d_no)-1
    panduan=1;
else
    panduan=0;
end

end
end


  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
  • 371
  • 372
  • 373
  • 374
  • 375
  • 376
  • 377
  • 378
  • 379
  • 380
  • 381
  • 382
  • 383
  • 384
  • 385
  • 386
  • 387
  • 388
  • 389
  • 390
  • 391
  • 392
  • 393
  • 394
  • 395
  • 396
  • 397
  • 398
  • 399
  • 400
  • 401
  • 402
  • 403
  • 404
  • 405
  • 406
  • 407
  • 408
  • 409
  • 410
  • 411
  • 412
  • 413
  • 414
  • 415
  • 416
  • 417
  • 418
  • 419
  • 420
  • 421
  • 422
  • 423
  • 424
  • 425
  • 426
  • 427
  • 428
  • 429
  • 430
  • 431
  • 432
  • 433
  • 434
  • 435
  • 436
  • 437
  • 438
  • 439
  • 440
  • 441
  • 442
  • 443
  • 444
  • 445
  • 446
  • 447
  • 448
  • 449
  • 450
  • 451
  • 452
  • 453
  • 454
  • 455
  • 456
  • 457
  • 458
  • 459
  • 460
  • 461
  • 462
  • 463
  • 464
  • 465
  • 466
  • 467
  • 468
  • 469
  • 470
  • 471
  • 472
  • 473
  • 474
  • 475
  • 476
  • 477
  • 478
  • 479
  • 480
  • 481
  • 482
  • 483
  • 484
  • 485
  • 486
  • 487
  • 488
  • 489
  • 490
  • 491
  • 492
  • 493
  • 494
  • 495
  • 496
  • 497
  • 498
  • 499
  • 500
  • 501
  • 502
  • 503
  • 504
  • 505
  • 506
  • 507
  • 508
  • 509
  • 510
  • 511
  • 512
  • 513
  • 514
  • 515
  • 516
  • 517
  • 518
  • 519
  • 520
  • 521
  • 522
  • 523
  • 524
  • 525
  • 526
  • 527
  • 528
  • 529
  • 530
  • 531
  • 532
  • 533
  • 534
  • 535
  • 536
  • 537
  • 538
  • 539
  • 540
  • 541
  • 542
  • 543
  • 544
  • 545
  • 546
  • 547
  • 548
  • 549
  • 550
  • 551
  • 552
  • 553
  • 554
  • 555
  • 556
  • 557
  • 558
  • 559
  • 560
  • 561
  • 562
  • 563
  • 564
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/270766
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号