如何将点均匀分布在矩形的周边

Question

我正在寻找一种沿着矩形周边的一部分分布点的方法。这些点需要彼此距离均匀。

我有一个矩形（通常是正方形）边界，以及沿该周边的 2 个点（ps和pe），标记了点的允许范围。这里我用红色标记了允许的范围：

我需要n沿着该线段放置点（通常是 1-3 个）。这些点需要均匀分布d。n0所以..n1和n1..等之间的距离n2应该都是d。出于分布目的，边界点也很重要，因此第一个点和最后一个点之间的距离 和ps/也pe应该d如此。

这似乎是一项简单的任务，但我很快意识到这种简单的方法在这里不起作用。获取线段的长度并除以n+1 不会考虑角点。例如：n= 1，使点太靠近pe：

我的数学很生疏（日常工作通常不需要太多数学），但我尝试了几种不同的方法，但都没有完全解决。我能够使用向量求解= 1，方法是找到和n之间的中点，找到垂直向量，然后将其与线段相交，如下所示。我不知道如何使这种方法发挥作用，如果是其他的话，或者即使它可以做到。pspen

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

Answer 1

我打算提出一个算法，但由于推导在数学上有点混乱，我没有足够的时间仔细思考并仔细检查其正确性。另外，我可能包含了一些冗余的检查，如果证明一些适当的不等式可能会变得多余，并且可能会证明解决方案的存在可能总是存在于合理的假设下。我相信这个想法是正确的，但我在写这篇文章时可能犯了一些错误，所以要小心。

因为根据您的评论，由于对称性，沿正方形边界的线段内只有一个角就足以解决其余情况，因此我将重点关注一个角情况。

具有一个 90 度角的多边形线段分为一对垂直的直线段，第一个长度为l1，第二个长度为l2。这两个长度是给你的。您还想在总长度为 的多边形线段上添加l1 + l2给定数量的n点，以便任意两个连续点之间的欧氏直线距离相同。称之为未知的距离d。当你这样做时，你最终会得到n1未知长度的完整段d和未知长度的完整段l1，这样n2dl2

n1 + n2 = n

一般来说，您还会在 90 度角处d1 <= d得到一段额外的长度。l1类似地，您还将有一段额外的长度，其一端位于 90 度角d2 <= d。l2因此，这两个线段d1和d2具有公共端并且是垂直的，因此它们形成直角三角形。根据毕达哥拉斯定理，这两个线段满足方程

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 = 1l1 > l2l1 <= l2l1 > l2n1 = n = 1n2 = 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"
         }
      }
   }
}