Блог

Я ищу способ распределить точки вдоль части периметра прямоугольника. Эти точки должны быть равномерно удалены друг от друга.

У меня есть прямоугольные (обычно квадратные) границы и 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 есть что-то еще, или даже если это можно сделать.

И последнее замечание: если полностью равномерное распределение невыполнимо, тогда достаточно хорошее приближение подойдет. В идеале аппроксимация примерно на одинаковую величину по всему диапазону (вместо того, чтобы, скажем, хуже по краям).

Я собираюсь предложить алгоритм, но поскольку вывод немного запутан с математической точки зрения, у меня не было достаточно времени, чтобы тщательно продумать его и тщательно проверить на правильность. Кроме того, я мог бы включить некоторые избыточные проверки, которые, если кто-то докажет, что некоторые правильные неравенства могут стать избыточными, и можно доказать, что существование решения всегда может существовать при разумных предположениях. Я считаю, что идея правильная, но, возможно, я допустил несколько ошибок, написав эту статью, так что будьте осторожны.

Поскольку, согласно вашему комментарию, для решения остальных случаев из-за симметрии достаточно иметь только один угол внутри сегмента вдоль границы квадрата, я сосредоточусь на случае с одним углом.

Ваш многоугольный сегмент с одним углом 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 имеют общий конец и перпендикулярны, поэтому они образуют прямоугольный треугольник. Согласно теореме Пифагора, эти два отрезка удовлетворяют уравнению

 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"
         }
      }
   }
}
 

Это предварительная версия, поэтому я предлагаю подходить к ней с некоторой осторожностью. У меня не было достаточно времени, чтобы проверить алгоритм, могут ли быть какие-то близкие к вырожденным случаи, для которых, возможно, придется добавить где-то несколько коротких циклов с операторами if. Однако, в целом, это, вероятно, будет работать почти всегда. Я просто публикую реализацию python, но когда я найду немного больше времени, и если вы хотите, я могу записать математику, лежащую в основе этого алгоритма. Некоторые идеи из этого алгоритма могут упростить предыдущий на один угол.

 import numpy as np
import math
import matplotlib.pyplot as plt


def sq_root(x, m, K):
  return math.sqrt(x**2 - (K - m*x)**2)

def f(x, n, L):
  return sq_root(x, n[0], L[0])   sq_root(x, n[2], L[2])   n[1]*x - L[1]

def df(x, n, L):
  return ((1-n[0]**2)*x   L[0]*n[0])/sq_root(x, n[0], L[0])   ((1-n[2]**2)*x   L[2]*n[2])/sq_root(x, n[2], L[2])   n[1]

#Solving the nonlinear equation for d by using Newton's method:
def solve_f(n, L):
  x = sum(L) / (sum(n)   2)
  y = f(x, n, L)
  while abs(y) >= 0.0000001:
    x = x - y / df(x, n, L)
    y = f(x, n, L) 
  return x - y / df(x, n, L)

def find_n(L, N):
  x0 = sum(L) / (N   1)
  # x <= x0
  n = np.array([0,0,0])
  n[0] = math.floor(L[0]/x0)
  n[2] = math.floor(L[2]/x0)
  n[1] = N - n[0] - n[2] - 1
  return n

def find_d(L, N):
  if N==1:
    d2 = (L[2]**2   L[1]**2 - L[0]**2)/(2*L[1])
    return math.sqrt(L[0]**2   d2**2), np.array([0,0,0])
  n = find_n(L, N)
  return solve_f(n, L), n

def find_the_points(L, N):
  d, n = find_d(L, N)
  d2 = math.sqrt(d**2 - (L[0]-n[0]*d)**2)
  #d3 = math.sqrt(d**2 - (L[2]-n[2]*d)**2)
  p = np.zeros((sum(n)   3, 2))
  p[ 0] = np.array([0, L[1]-L[0]])
  p[-1] = np.array([L[1], L[1]-L[2]])
  e_x = np.array([1,0])
  e_y = np.array([0,1])
  corner = np.array([0,L[1]]) 
  for i in range(n[0]):
    p[i 1] = p[0]   (i 1)*d*e_y
  for i in range(n[1] 1):
    p[n[0] i 1] = corner   (d2   i*d)*e_x
  for i in range(n[2]):
    p[-(2 i)] = p[-1]   (i 1)*d*e_y
  return p, d, n 

'''
Test example:
'''

# lengths of the three straight segments along the edges of a square of edge_length L2:
L1 = 5
L2 = 7
L3 = 3
L = np.array([L1, L2, L3]) 

N = 7
# N = number of points to be added
# If there are two corners then number of segments aligned with edges of square is N - 1
# total number of equidistant segments is N   1
# n = n[0], n[1], n[2] represents the number of segments aligned with each 
# striaght segment from the rectangular polyline along square's boundary


points, d, n = find_the_points(L, N)
print(points)
print(d)
print(n)

plt.figure()
plt.plot(points[:,0], points[:,1]) 
for j in range(points.shape[0]):
  plt.plot(points[j,0], points[j,1], 'ro')
axx = plt.gca()
axx.set_aspect('equal')
plt.show() # if you need...

 

Пифагор спешит на помощь.

Рассмотрим случай, когда n = 2 с одним углом ¹. Остальные случаи, вероятно, будут аналогичными, только с большим количеством краевых случаев и возможных конфигураций ².

Назовем длину вертикального отрезка i и длину горизонтального отрезка j.
Мы ищем точки X, Y, так что расстояние dist(ps,x) = dist(x,y) = dist(y,pe)

Во-первых, давайте предположим, что угол лежит между точками X и Y. В этом случае мы ищем решение этого уравнения: x2 = (i — x^{)2 (j — x)2}, где i и j известны.

Если вышеупомянутое уравнение не имеет решения, это означает, что угол должен лежать либо между ps и X, либо между Y и pe. Я рассмотрю только случай ps и X, поскольку другой является симметричным:
x ² = i ² (j-2x) ² — это уравнение для этого случая.

Для большего количества точек и углов просто будет больше возможных конфигураций точек и углов. Однако, поскольку расстояние должно быть равным, а длины известны, скорее всего, будет достаточно серии квадратных уравнений. Однако случай с 5 точками и тремя углами будет немного сомнительным.

¹ Случай для n=1 будет почти таким же, как и для асимметричного варианта n=2 , который я рассмотрю.
², Что сделает их довольно уродливыми.

Точки на любой из сторон должны быть равноудалены в соответствии с задачей. Просто угадайте расстояние и используйте двоичный поиск, чтобы найти решение с любой степенью точности. Есть немного сложная часть в определении того, сколько точек лежит на каждой стороне прямоугольника. (Надеюсь, это просто «слегка». 🙂