关键词：
找了半天网上只有两种版本的计算闵科夫斯基和
夏天大佬的c++闵科夫斯基和这个大佬的闵科夫斯基和更好理解
饕餮传奇大佬的c++闵科夫斯基和这个大佬讲的更加细致，同时他的博客里还有很多其他的数学计算的讲解，挺好的（比如极角排序）
注意，该方法对输入点集的顺序有要求，必须要是逆时针顺序输入点集才行
当然。。。这也就叉乘判断一下，然后一个reverse就能解决问题的了
import math
import time
def Minkowski_sum(rec1, rec2):
vectors=[]
ans=[]
#
tmp_rec=rec1
init_point1=rec1[0]
for i in range(len(tmp_rec)):
point=tmp_rec[i]
if init_point1[1]==point[1] and init_point1[0]>point[0]:
init_point1=point
if point[1]>init_point1[1]:
init_point1=point
if i>0:
vectors.append([tmp_rec[i][0] - tmp_rec[i - 1][0], tmp_rec[i][1] - tmp_rec[i - 1][1]])
if i==len(tmp_rec)-1:
vectors.append([tmp_rec[0][0] - tmp_rec[i][0], tmp_rec[0][1] - tmp_rec[i][1]])
tmp_rec=rec2
init_point2=rec2[0]
for i in range(len(tmp_rec)):
point=tmp_rec[i]
if init_point2[1]==point[1] and init_point2[0]>point[0]:
init_point2=point
if point[1]>init_point2[1]:
init_point2=point
if i>0:
vectors.append([tmp_rec[i][0] - tmp_rec[i - 1][0], tmp_rec[i][1] - tmp_rec[i - 1][1]])
if i==len(tmp_rec)-1:
vectors.append([tmp_rec[0][0] - tmp_rec[i][0], tmp_rec[0][1] - tmp_rec[i][1]])
tmp_point=[init_point1[0]+init_point2[0],init_point1[1]+init_point2[1]]
ans.append([tmp_point[0],tmp_point[1]])
tmp_cmp=[]
for i in range(len(vectors)):
tmp_cmp.append([math.atan2(vectors[i][1],vectors[i][0]),vectors[i]])
tmp_cmp=sorted(tmp_cmp,key= lambda tmp:tmp[0])
# for i in tmp_cmp:
# print(i[0],i[1].x,i[1].y)
vectors=[]
for i in range(1,len(tmp_cmp)):
if tmp_cmp[i][0]==tmp_cmp[i-1][0]:
tmp_cmp[i][1][0]+=tmp_cmp[i-1][1][0]
tmp_cmp[i][1][1]+=tmp_cmp[i-1][1][1]
else:
vectors.append(tmp_cmp[i-1][1])
vectors.append(tmp_cmp[len(tmp_cmp)-1][1])
for i in range(len(vectors)-1):
tmp_point[0]+=vectors[i][0]
tmp_point[1]+=vectors[i][1]
ans.append([tmp_point[0],tmp_point[1]])
return ans
def main():
a=[]
a.append([0,0])
a.append([2,3])
a.append([-3,1])
b=[]
b.append([0,0])
b.append([1,1])
b.append([0,4])
b.append([-2,3])
c=Minkowski_sum(a,b)
print(c)
if __name__ == '__main__':
start_time=time.time()*1000
main()
end_time=time.time()*1000
print('time ',(end_time-start_time),' ms ')
模板/经典题型闵可夫斯基和(代码片段)
闵可夫斯基和是两个欧几里得空间的点集的和。点集A与B的闵可夫斯基和就是o|o=a+b，其中a属于A,b属于B。求凸包之间的闵可夫斯基和的方法。把两个凸包的每一条向量都抠出来，按照极角序排序构成新凸包即可。注意点和向量的... 查看详情
闵可夫斯基和莫队codeforces1195f(代码片段)
题目链接：https://codeforces.com/contest/1195/problem/F题意：给你n个凸多边形，m次询问，每次询问[l,r]区间内的凸多边形的闵可夫斯基和，有多少个顶点。首先：多个凸多边形的闵可夫斯基和其实就是多个凸多边形的边排个序，然后首... 查看详情
闵可夫斯基和(代码片段)
...思想对两个凸包进行合并，合并完以后再求一次凸包以下代码因使用浮点误差巨大#include<bits/stdc++.h>usingnamespacestd;#definempmake_pair#definefifirst#definesesecond#definepbpush_backtypedefdoubledb;constdbeps=1e-9;constdbpi=acos(-1);intsign(dbk)if(k>eps)retur... 查看详情
hdu4785闵可夫斯基和exhaustedrobot(代码片段)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4785题意：一个房间（矩形），里面有一些家具（凸多边形），你有一个扫地机器（凸多边形），扫地机器可以扫地是它的第一个点，能扫地条件是机器完全在房间里面并且和家具没有... 查看详情
数据挖掘任务1：距离计算(代码片段)
...1,42,10）和（20,0,36,8）表示的对象（a）计算这两个对象之间的欧几里得距离；（b）计算这两个对象之间的曼哈顿距离；（c）使用q=3，计算这两个对象之间的闵可夫斯基距离（d&... 查看详情
机器学习距离度量中常见的距离计算公式(代码片段)
机器学习：距离度量欧式距离(EuclideanDistance)曼哈顿距离(ManhattanDistance)切比雪夫距离(ChebyshevDistance)闵可夫斯基距离(MinkowskiDistance)标准化欧氏距离(StandardizedEuclideanDistance)余弦距离(CosineDistance)汉明距离(HammingDistance)杰卡德距离(J 查看详情
机器学习距离公式总结(代码片段)
作者：daniel-D出处：http://www.cnblogs.com/daniel-D/在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法&... 查看详情
机器学习距离公式总结(代码片段)
作者：daniel-D出处：http://www.cnblogs.com/daniel-D/在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法&... 查看详情
机器学习常用距离度量(代码片段)
...雪夫距离2.4闵可夫斯基距离3连续属性和离散属性的距离计算4小结5其他距离公式5.1标准化欧氏距离5.2余弦距离5.3汉明距离5.4杰卡德距离5.5马氏距离1距离公式的基本性质在机器学习过程中，对于函数dist()，若它是一"距... 查看详情
深度剖析hmm（附python代码）2.隐马尔科夫链hmm的em训练过程(代码片段)
隐马尔科夫链HMM的参数θ的EM训练过程现在回到前一节最后提出的参数θ的最大似然函数上来，先对其做个对数变换，做对数变换是考虑到序列X的概率计算公式中包含了连乘，为了方便计算同时避免序列X的概率过小... 查看详情
高效的 Minkowski 和计算
】高效的Minkowski和计算【英文标题】：EfficientMinkowskisumcalculation【发布时间】：2012-07-1318:16:57【问题描述】：不知道有没有算法可以高效计算离散的一维Minkowski和。闵可夫斯基和定义为：S+T=x+y|xinS,yinT我们是否可以将集合表示为... 查看详情
pymc：马尔科夫链蒙特卡洛采样工具(代码片段)
...叶斯统计模型和马尔科夫链蒙塔卡洛采样工具拟合算法的Python库。PyMC的灵活性及可扩展性使得它能够适用于解决各种问题。除了包含核心采样功能，PyMC还包含了统计输出、绘图、拟合优度检验和收敛性诊断等方法。加qq群81362257... 查看详情
火炉炼ai机器学习045-对股票数据进行隐马尔科夫建模(代码片段)
...器学习045-对股票数据进行隐马尔科夫建模(本文所使用的Python库和版本号:Python3.6,Numpy1.14,scikit-learn0.19,matplotlib2.2)股票数据是非常非常典型的时序数据，数据都是按照日期排列好，而且股价就是我们所能观察到的观测序列，而股价... 查看详情
各种距离欧式距离曼哈顿距离切比雪夫距离闵可夫斯基距离标准欧氏距离马氏距离余弦距离汉明距离杰拉德距离相关距离信息熵
1.欧氏距离(EuclideanDistance)欧氏距离是最容易直观理解的距离度量方法，我们小学、初中和高中接触到的两个点在空间中的距离一般都是指欧氏距离。二维平面上点a(x1,y1)与b(x2,y2)间的欧氏距离:三维空间点a(x1,y1,z1)与b(x2,y2,z2)间的欧... 查看详情
深度剖析hmm（附python代码）3.隐马尔科夫链所解决的问题(代码片段)
...问题，利用维比特算法来解决）解码过程的相关python代码defdecode(self,X,istrain=True):"""利用维特比算法，已知序列求其隐藏状态值: 查看详情
机器学习实战4：基于马尔科夫随机场的图像分割(附python代码)
...题2图像像素邻域3观测场与标记场4马尔科夫随机场建模5Python实现5.1计算能量函数5.2退火优化5.3效果展示0写在前面机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数... 查看详情
初识马尔科夫模型（markovmodel）(代码片段)
...性质使得马尔科夫模型可以被广泛用于统计学、经济学、计算机科学等多领域，并发挥重要作用。三、学习步骤学习马尔科夫模型，可以按以下步骤进行：①了解马尔科夫模型的概念和基本定义，包括马尔科夫性... 查看详情
用隐马尔科夫模型来预测股价走势(代码片段)
...题求解的方法为动态规划的维特比算法。HMM的实现：python的hmmlearn类， 查看详情