algorithm - 如何在矩形的周长周围均匀分布点

Question

我正在寻找一种沿矩形周长的一部分分布点的方法。这些点需要彼此均匀地远离。
我有一个矩形(通常是正方形)边界，沿该周长有 2 个点( ps 和 pe )，它们标记了点的允许范围。在这里，我用红色标记了允许的范围:

我需要沿该段放置 n 点(通常为 1-3)。这些点需要以 d 的距离均匀分布。所以 n0 .. n1 和 n1 .. n2 等之间的距离应该都是 d 。边界点也计入分布的目的，因此第一个和最后一个点与 ps/pe 之间的距离也应该是 d。
这似乎是一项简单的任务，但我很快意识到天真的方法在这里不起作用。取段的长度并除以 n +1 不会考虑角点。例如:n = 1，使点离 pe 太近:

我的数学很生疏(日常工作通常不需要太多)，但我尝试了几种不同的方法，但没有一个完全奏效。我能够使用向量求解 n = 1，方法是找到 ps 和 pe 之间的中点，找到一个垂直向量，然后将其与线段相交，如下所示。如果 n 是别的东西，或者即使可以完成，我也不知道如何使这种方法起作用。

最后要注意的是，如果完全均匀的分布是不切实际的，那么足够好的近似值就可以了。理想情况下，近似值在整个范围内的偏差大致相同(而不是说，边缘更差)。

Answer 1

我将建议一个算法，但由于推导在数学上有点困惑，我没有足够的时间仔细考虑它并仔细检查它的正确性。另外，我可能已经包含了一些冗余检查，如果证明某些适当的不等式可能会变得多余，并且可以证明在合理假设下解决方案的存在可能始终存在。我相信这个想法是正确的，但我可能在写这个东西时犯了一些错误，所以要小心。
因为根据您的评论，由于对称性，沿正方形边界的线段内只有一个角足以解决其余情况，所以我将重点讨论一个角情况。
带有一个 90 度角的多边形线段被分成一对垂直的直线段，第一个长度为 l1 ，第二个长度为 l2 。这两个长度给你。您还想在总长度为 l1 + l2 的多边形线段上添加给定数量的 n 点，以便任意两个连续点之间的欧几里德直线距离相同。调用未知距离 d 。当你这样做时，你最终会得到 n1 上未知长度 d 的 l1 完整段和 n2 上未知长度 d 的 l2 完整段，以便

n1 + n2 = n

通常，您还会在 d1 <= d 上多出一个长度为 l1 的段，其一端位于 90 度角。类似地，您还将在 d2 <= d 上有一个额外的长度为 l2 的段，其一端位于 90 度角。因此， d1 和 d2 两个线段共享一个公共(public)端并且是垂直的，因此它们形成一个直角三角形。根据毕达哥拉斯定理，这两段满足方程

d1^2 + d2^2 = d^2

如果我们把到目前为止的所有方程和信息结合起来，我们得到一个方程和限制系统，它是:

n1*d + d1 = l1
n2*d + d2 = l2
d1^2 + d2^2 = d^2
n1 + n2 = n
n1 and n2 are non-negative integers

其中变量 d, d1, d2, n1, n2 在给出 l1, l2, n 时未知。
从前两个方程，你可以表达 d1 和 d2 并代入第三个方程:

d1 = l1 - n1*d
d2 = l2 - n2*d
(l1 - n1*d)^2 + (l2 - n2*d)^2 = d^2
n1 + n2 = n
n1 and n2 are non-negative integers

在特殊情况下，当只想添加一个点时，即 n = 1 ，根据是 n1 = n = 1 还是 n2 = n = 1 分别有 l1 > l2 或 l1 <= l2 。
说 l1 > l2 。然后 n1 = n = 1 和 n2 = 0 所以

d1 = l1 - d
d2 = l2
(l1 - d)^2 + l2^2 = d^2

展开方程，简化它并求解 d :

l1^2 - 2*l1*d + d^2 + l2^2 = d^2
l1^2 + l2^2 - 2*l1*d = 0
d = (l1^2 + l2^2) / (2*l1)

接下来，让我们回到一般情况。你必须解决系统

(l1 - n1*d)^2 + (l2 - n2*d)^2 = d^2
n1 + n2 = n
n1 and n2 are non-negative integers

其中变量 d, n1, n2 在给出 l1, l2, n 时未知。展开第一个方程:

l1^2  -  2 * l1 * n1 * d  +  n1^2 * d^2  +  l2^2  -  2 * l2 * n2 * d  +  n2^2 * d^2 = d^2
n1 + n2 = n
n1 and n2 are non-negative integers

并将这些术语组合在一起

(n1^2 + n2^2 - 1) * d^2  - 2 * (l1*n1 + l2*n2) * d  +  (l1^2 + l2^2) = 0
n1 + n2 = n
n1 and n2 are non-negative integers

第一个方程是 d中的二次方程

(n1^2 + n2^2 - 1) * d^2  - 2 * (l1*n1 + l2*n2) * d  +  (l1^2 + l2^2) = 0

根据二次公式，您期望有两个解决方案(通常，您选择正数。
如果两者都是正数且 d < l1 和 d < l2 ，您可能有两种解决方案):

d = ( (l1*n1 + l2*n2) +- sqrt( (l1*n1 + l2*n2)^2 - (l1^2 + l2^2)*(n1^2 + n2^2 - 1) ) ) / (n1^2 + n2^2 - 1)
n1 + n2 = n
n1 and n2 are non-negative integers

现在，如果你能找到合适的 n1 和 n2 ，你可以使用上面的二次公式计算必要的 d 。
为了存在解，平方根中的表达式必须是非负的，所以你有不等式限制

d = ( (l1*n1 + l2*n2) +- sqrt( (l1*n1 + l2*n2)^2 - (l1^2 + l2^2)*(n1^2 + n2^2 - 1) ) ) / (n1^2 + n2^2 - 1)
(l1*n1 + l2*n2)^2 - (l1^2 + l2^2)*(n1^2 + n2^2 - 1) >= 0
n1 + n2 = n
n1 and n2 are non-negative integers

简化不等式表达式:

(l1*n1 + l2*n2)^2 - (l1^2 + l2^2)*(n1^2 + n2^2 - 1) = (l1^2 + l2^2) - (l1*n2 - l2*n1)^2

这将我们带到了以下系统

d = ( (l1*n1 + l2*n2) +- sqrt( (l1^2 + l2^2) - (l1*n2 - l2*n1)^2 ) ) / (n1^2 + n2^2 - 1)
(l1^2 + l2^2) - (l1*n2 - l2*n1)^2 >= 0
n1 + n2 = n
n1 and n2 are non-negative integers

分解不等式，

d = ( (l1*n1 + l2*n2) +- sqrt( (l1^2 + l2^2) - (l1*n2 - l2*n1)^2 ) ) / (n1^2 + n2^2 - 1)
(sqrt(l1^2 + l2^2) - l1*n2 + l2*n1) * (sqrt(l1^2 + l2^2) + l1*n2 - l2*n1) >= 0
n1 + n2 = n
n1 and n2 are non-negative integers

因此，对于这些限制，您有两种情况:
情况1:

d = ( (l1*n1 + l2*n2) +- sqrt( (l1^2 + l2^2) - (l1*n2 - l2*n1)^2 ) ) / (n1^2 + n2^2 - 1)
sqrt(l1^2 + l2^2) - l1*n2 + l2*n1 >= 0 
sqrt(l1^2 + l2^2) + l1*n2 - l2*n1 >= 0
n1 + n2 = n
n1 and n2 are positive integers

或者
案例2:

d = ( (l1*n1 + l2*n2) +- sqrt( (l1^2 + l2^2) - (l1*n2 - l2*n1)^2 ) ) / (n1^2 + n2^2 - 1)
sqrt(l1^2 + l2^2) - l1*n2 + l2*n1 <= 0 
sqrt(l1^2 + l2^2) + l1*n2 - l2*n1 <= 0
n1 + n2 = n
n1 and n2 are positive integers

我们专注于案例 1，看到案例 2 是不可能的。首先表达 n2 = n - n1 ，然后将其代入两个不等式中的每一个，并在每个不等式的一侧隔离 n1 。这个过程产生:
情况1:

d = ( (l1*n1 + l2*n2) +- sqrt( (l1^2 + l2^2) - (l1*n2 - l2*n1)^2 ) ) / (n1^2 + n2^2 - 1)
( l1*n - sqrt(l1^2 + l2^2) ) / (l1 + l2) <=  n1  <= ( l1*n + sqrt(l1^2 + l2^2) ) / (l1 + l2) 
n1 + n2 = n
n1 and n2 are positive integers

可以看到情况 2 颠倒了不等式，这是不可能的，因为左侧小于右侧。
所以算法可能是这样的:

function d = find_d(l1, l2, n)
{
   if n = 1 and l1 > l2 { 
      return d = (l1^2 + l2^2) / (2*l1)
   } else if n = 1 and l1 <= l2 {
      return d = (l1^2 + l2^2) / (2*l2)
   }
   for integer n1 >= 0 starting from floor( ( l1*n - sqrt(l1^2 + l2^2) ) / (l1 + l2) ) to floor( ( l1*n + sqrt(l1^2 + l2^2) ) / (l1 + l2) ) + 1 
   {
      n2 = n - n1
      D = (l1^2 + l2^2) - (l1*n2 - l2*n1)^2
      if D >= 0
      {
         d1 = ( (l1*n1 + l2*n2) - sqrt( D ) ) / (n1^2 + n2^2 - 1)  
         d2 = ( (l1*n1 + l2*n2) + sqrt( D ) ) / (n1^2 + n2^2 - 1) 
         if 0 < d1 < max(l1, l2) {       
            return d1
         } else if  0 < d2 < max(l1, l2) {
            return d2
         } else {
            return "could not find a solution"
         }
      }
   }
}