Como gerar n pontos equidistantes em um espaço dimensional n-1

Como dito, eu quero construir um programa para gerar n pontos equidistantes em um espaço euclidiano. Pelo que eu sei

1d: todos os pontos
2d: todos os triângulos equilaterais
3d: todos os tetraedros equilaterais
até 3d: suponho que seja chamado de hipertriangulo equilateral

Portanto, meu problema é o seguinte, em um espaço n-1 euclidiano, fornecendo um ponto definido para construir o outro n-1, a fim de ter um hiper-triângulo equilateral com um d distante entre cada ponto.

Suponho que podemos começar como a seguir, por exemplo, um espaço 3D.

p1 = (x1, y1, z1) fixo
p2 = (x2, y2, z2)
p3 = (x3, y3, z3)
p4 = (x4, y4, z4)
d

Começamos a consertar p2 sabendo d e p1

$d²=(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2$

Temos 3 variáveis x2, y2, z2. Podemos consertar aleatoriamente dois deles e determinar o terceiro sem problemas.

Então, para o segundo ponto, temos agora 2 equações para defini-lo:

$d²=(x_1-x_3)^2 + (y_1-y_3)^2 + (z_1-z_3)^2$
$d²=(x_2-x_3)^2 + (y_2-y_3)^2 + (z_2-z_3)^2$

Como anteriormente, presumo que possamos consertar 2 variáveis para determinar a terceira.

Para o último ponto, agora temos 3 equações que o definiram.

Portanto, para um espaço dimensional n-1, temos a equação n-1 para definir o último ponto.

Não sei como resolver esse tipo de sistema composto de equação quadrática com uma variável e se o processo que consiste em fixar a dimensão n-1 para determinar a última leva a um hipertriangulo equidistante. Além disso, existem outros métodos com uma complexidade menor e mais fácil de implementar.

Espero ter sido suficientemente claro e agradeço a sua ajuda.

computational-geometry KyBe
fonte

Respostas:

Suponho que estamos trabalhando em . $\mathbb{R}^n$

Antes de tudo, observe que um simplex regular determina efetivamente todos os outros. De fato, se são dois conjuntos de pontos em que atendem à condição de regularidade, eles podem ser obtidos um do outro, compondo no máximo uma isometria e uma transformação homotética do espaço afim (o converse também é verdadeiro). $n-$ $S_1, S_2$ $\mathbb{R}^n$

Portanto, é suficiente construir um simplex unitário centrado na origem. Visualizamos cada vértice do simplex como um elemento do espaço vetorial dimensional real . $n-$ $v_1, v_2, \dots v_{n+1}$ $n$

Considere dois vértices do simplex, deixe- ser a origem e ser o plano que passa . O ângulo é exatamente . Para provar isso, observamos que: $v_1, v_2$ $O$ $\pi$ $v_1, v_2, O$ $\vartheta =\angle v_1 O v_2$ $\arccos (-1/n)$

0 = {‖ \sum_{i} v_{i} ‖}^{2} = (n + 1) + 2 \cos ϑ (\binom{n + 1}{2})

$0 = \left \| \sum_{i} v_i \right \|^2 = (n+1) + 2 \cos\vartheta \binom{n+1}{2}$

Deduzimos que o seguinte se aplica:

$\forall i \quad \| v_i \| = 1$
$\forall i \neq j \quad \left \langle v_i, v_j\right \rangle = -1/n$

Podemos assumir sem perda de generalidade que estão na mesma linha, que está no mesmo plano que os outros e assim por diante (em geral, que para cada , estão no mesmo subespaço de com dimensão ). Portanto, podemos escrever os vetores por coordenadas da seguinte maneira: $v_1, v_2$ $v_3$ $k$ $v_1, v_2, \dots v_k$ $\mathbb{R}^n$ $k$

\begin{array}{rcl} \begin{array}{r} v_{1} \\ v_{2} \\ \dots \\ v_{n + 1} \end{array} & \begin{array}{r} = \\ = \\ = \end{array} & \begin{array}{cccccc} (x_{1, 1} & 0 0 & 0 0 & 0 0 & \dots & 0 0)^{T} \\ (x_{2, 1} & x_{2, 2} & 0 0 & 0 0 & \dots & 0 0)^{T} \\ (x_{n + 1, 1} & x_{n + 1, 2} & x_{n + 1, 3} & x_{n + 1, 4} & \dots & x_{n + 1, n + 1})^{T} \end{array} \end{array}

$\begin{array}{r c l} \begin{array}{r} v_1 \\ v_2 \\ \cdots \\ v_{n+1} \end{array} & \begin{array}{r} = \\ = \\ \\ = \end{array} & \begin{array}{c c c c c c} (x_{1,1} & 0 & 0 & 0 & \dots & 0)^T \\ (x_{2,1} & x_{2,2} & 0 & 0 & \dots & 0)^T \\ \\ (x_{n+1, 1} & x_{n+1, 2} & x_{n+1, 3} & x_{n+1, 4} & \dots & x_{n+1, n+1})^T \\ \end{array} \end{array}$

A primeira equação determina exclusivamente e a segunda todo . Agora usamos novamente o primeiro para calcular e com o segundo determinamos todo o restante . $x_{1,1}$ $x_{m,1}$ $x_{2,2}$ $x_{2, m}$

A continuação do procedimento de maneira semelhante calcula os valores das coordenadas de todos os vértices.

ordenação rápida
fonte

Obrigado, apesar das coisas teóricas bem formadas que você compartilha conosco, não consigo descobrir como determinar , presumindo que é definido pelo usuário. Você pode explicar isso de outra maneira?

x_{2, 1}, x_{2, 2}, . . .

$x_{2,1}, x_{2,2},...$

x_{1, 1}

$x_{1,1}$

precisa saber é

v [n + 1] deve ter n dimensões, não n + 1, como na última equação; o v [n + 1] deve ser calculado a partir de v [0] + v [1] + ... + v [n] + v [n + 1] = 0

04/04/19

Você pode criar n-1 pontos equidistantes usando os vetores unitários ao longo de cada um dos eixos aka. (1, 0, 0, 0, ..., 0); (0, 1, 0, 0, ..., 0); (0, 0, 1, 0, ..., 0); etc., o último enésimo ponto será ao longo da direção 1, 1, 1, ..., 1.

Então você pode usar uma escala para definir a distância entre os pontos de a e traduzir para mover um dos pontos para o ponto fixo $\sqrt 2$ $d$

catraca arrepiante
fonte

Bom - acho que você pode escrever uma solução em formato fechado com essa abordagem!

Ruakh

[mais tarde] Para o último ponto, você pode usar ou .

(\frac{1 - \sqrt{n}}{n - 1}, \frac{1 - \sqrt{n}}{n - 1}, \dots, \frac{1 - \sqrt{n}}{n - 1})

$\left( \frac{1 - \sqrt n}{n - 1} , \frac{1 - \sqrt n}{n - 1} , \dots , \frac{1 - \sqrt n}{n - 1} \right)$

(\frac{1 + \sqrt{n}}{n - 1}, \frac{1 + \sqrt{n}}{n - 1}, \dots, \frac{1 + \sqrt{n}}{n - 1})

$\left( \frac{1 + \sqrt n}{n - 1} , \frac{1 + \sqrt n}{n - 1} , \dots , \frac{1 + \sqrt n}{n - 1} \right)$

Ruakh

Obrigado, mas não tenho certeza de entender bem o que você propôs "usando o vetor unitário ao longo de cada eixo", pode reformular, por favor.

precisa saber é

@KyBe Adicionei alguns exemplos.

ratchet freak

De onde você encontrou sua expressão do último ponto (que é o enésimo num espaço n-1 d) @ruakh? É interessante, mas não consigo descobrir como obtê-lo.

precisa saber é