文件名称：GettingClose:查找凸多边形和直线之间的最小距离的算法
文件大小：185KB
文件格式：ZIP
更新时间：2024-05-04 15:24:36
Python
路径查找器 确定具有整数坐标的凸多边形的顶点与ax + by = c形式的线之间的最小距离的算法。 假设条件 我们假设多边形和直线是不相交的。 我们基于这样的事实，即在分配指令中引用了“阳光侧”，如果存在交叉点，这将是没有意义的。 与键输入在YAML格式给出polygon作为表示在顺时针顺序的多边形的顶点的点的列表，并且line的三元组(a,b,c)指定如上所述的线。 算法 该算法首先在多边形上随机选择一个顶点，然后根据与直线的距离跨所有顶点执行二进制搜索。 到直线的距离是使用线性代数中讲授的简单投影算子在恒定时间内计算的。 有关具有非正式复杂性/正确性分析的完整伪代码，请参见GettingClose.pdf 。 运行指南： 所有命令都将从项目目录中运行。 该项目使用Matplotlib的目的只是为了绘制网络，以作为可视化工具。 这些软件包不用于算法。 要安装依赖项： foo@bar
【文件预览】：
GettingClose-main
----.gitignore(2KB)
----requirements.txt(315B)
----data()
--------images()
--------inputs()
----Pipfile.lock(18KB)
----GettingClose.pdf(88KB)
----Pipfile(198B)
----readme.md(2KB)
----main.py(5KB)