gpt4 book ai didi

algorithm - 通过一组点找到最宽的空直线路径

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:39:52 24 4
gpt4 key购买 nike

我正在创建一个简单的游戏,并在为我的游戏设计 AI 时遇到了这个问题:给定笛卡尔坐标矩形内的一组 N 个点,我需要找到通过该矩形的最宽直线路径。路径必须为空(即不包含任何点)。

enter image description here

enter image description here

请问有没有什么高效的算法可以解决这个问题?你能建议任何与这个问题相关的关键词/论文/任何东西吗?

编辑:矩形总是由其角上的 4 个点定义。我添加了一个图像来说明。上图中的路径是由两条红线决定的

最佳答案

这是最宽的空走廊问题。 Houle 和 Maciel 在 1988 年题为“通过一组点找到最宽的空走廊”的技术报告中给出了 O(n2)-时间、O(n)-空间算法,这似乎与在线提供。幸运的是,Janardan 和 Preparata 在他们论文的第 4 节中描述了这个算法 Widest-corridor problems , 这是可用的。

关于algorithm - 通过一组点找到最宽的空直线路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5798699/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com