最小化3-d中与点集的欧几里得距离 [英] Minimize Euclidean distance from sets of points in 3-d

问题描述

让我们看一下3维空间中的四个（m）点-我想将其推广为n维，但是3个足以满足要求（第1部分）。

  a =（x1，y1，z1）
 
b =（x2，y2，z2）
 
c =（x3，y3，z3）
。 
。 
 
p =（x，y，z）
 
查找点q = c1 * a + c2 * b + c3 * c + .. 
 
其中c1 + c2 + c3 + .. = 1 
和c1，c2，c3，..> = 0 
 st 
欧式距离pq最小。 
  

可以使用哪些算法？想法或伪代码就足够了。

第二部分：求解n维的m点：

我认为将n个维度上的m个点归纳起来是微不足道的，但是事实证明，这并不容易。我在这里为一般问题创建了另一个问题：

Let's look at four (m) points in 3-d space- I want to generalize to n-d, but 3 should suffice for a solution ( Part 1).

a= (x1, y1, z1)

b= (x2, y2, z2)

c= (x3, y3, z3)
.
.

p= (x , y , z)

Find point q = c1* a + c2* b + c3* c + ..

where c1 + c2 + c3 +.. = 1
and  c1, c2, c3, .. >= 0
s.t.
euclidean distance pq is minimized.

What algorithms can be used ? Idea or pseudocode is enough.

Part 2: solve for m points in n-dimensions :

I thought it would be trivial to generalize to m points in n dimensions, but turns out it is not straightforward. I created another problem for the general problem here: minimize euclidean distance from sets of points in n-dimensions

解决方案

I think your question in 3D can be reduced to a simple affine 2D geometry problem by projecting the point P on the plane defined by the three points A, B, C, or the two vectors AB and AC (or another combinations of AB, AC, and BC).

At first sight, it seems likely that the 3+1 points problem generalizes to N dimensions (3 points always defining a triangle and a plane).
However, it is not immediately clear if this approach would work for more points that would not be coplanar.

1- reduction to 2D by projecting P to a point P'on the plane defined by vectors AB, and AC.

2- understand that the position of P' is determined by only one coefficient t in the Reals s.t. P' is an affine combination of AB and AC :
P' = t * AB + (1-t) * AC

3- from there, P' can be in 3 distinct locations:

• (a) inside the triangle ABC: in that case, Q = P'

• (b) in the areas delimited by an orthogonal outwards projection of one of the segments; in that case Q is the orthogonal projection of P' on the closest segment.

• (c) not in (a) or (b); in that last trivial case, Q is the closest of A, B, or C

---

这篇关于最小化3-d中与点集的欧几里得距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！