gpt4 book ai didi

algorithm - 如何识别周围的矩形

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

如何识别给定点的近似包围矩形?

预期输出:如下图上半部分所示。

输入:下半部分。

enter image description here

最佳答案

我的建议是执行以下两个步骤:

  1. 找到 convex hull的点
  2. 找到一个可以在 O(n) 中解决的凸多边形的最小边界框,接下来是 algorithm

已编辑:好的,实际上上述 2 个步骤不足以成为一个正确且被接受的答案。

在这两个步骤之前,您必须先对点集进行预处理。

  1. 检查是否有任何3个或更多点共线,删除除两个端点之外的那些点。
  2. 在第 1 步之后,您现在应该得到一组没有 3 个或更多点共线的点。

检查集合的大小:如果它只剩下 1 点或 2 点,你必须特殊处理它们(对于 1 点,你可以通过你自己的方法找到任何最小的盒子来包含它;对于 2 点,可能使它们成为边界框的对角线?)

如果结果集还剩下 >= 3 个点,那么就按照我原来的 2 个步骤:凸包 + 旋转卡尺

干杯。

关于algorithm - 如何识别周围的矩形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22011255/

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