以任何给定方向的缠绕顺序对 4 个 3D 坐标进行排序

Question

我需要按照如下图所示的缠绕顺序对选定的 3D 坐标进行排序。右下角的顶点应该是数组的第一个元素，左下角的顶点应该是数组的最后一个元素。这需要在相机面向点的任何方向以及这些点的任何方向的情况下工作。由于“左上角”、“右下角”等是相对的，我假设我可以将相机用作参考点？我们还可以假设所有 4 个点都共面。

我正在使用 Blender API（编写一个 Blender 插件）并且在必要时可以访问相机的视图矩阵。从数学上讲，这甚至可能吗？也许我把事情复杂化了？

由于 Blender API 在 Python 中，我将其标记为 Python，但我可以接受伪代码或根本没有代码。我主要关心如何从数学上解决这个问题，因为我不知道从哪里开始。

Answer 1

既然你假设这四个点是共面的，那么你需要做的就是找到质心，计算质心到每个点的向量，并根据向量的角度对点进行排序。

import numpy as np

def sort_points(pts):
    centroid = np.sum(pts, axis=0) / pts.shape[0]
    vector_from_centroid = pts - centroid
    vector_angle = np.arctan2(vector_from_centroid[:, 1], vector_from_centroid[:, 0]) 
    sort_order = np.argsort(vector_angle) # Find the indices that give a sorted vector_angle array

    # Apply sort_order to original pts array. 
    # Also returning centroid and angles so I can plot it for illustration. 
    return (pts[sort_order, :], centroid, vector_angle[sort_order])

假设点是二维的，这个函数计算角度，但是如果你有共面点，那么找到公共平面中的坐标并消除第三个坐标应该很容易。

让我们编写一个快速绘图函数来绘制我们的点：

from matplotlib import pyplot as plt

def plot_points(pts, centroid=None, angles=None, fignum=None):
    fig = plt.figure(fignum)
    plt.plot(pts[:, 0], pts[:, 1], 'or')
    if centroid is not None:
        plt.plot(centroid[0], centroid[1], 'ok')
        
    for i in range(pts.shape[0]):
        lstr = f"pt{i}"
        if angles is not None:
            lstr += f" ang: {angles[i]:.3f}"
        plt.text(pts[i, 0], pts[i, 1], lstr)
    
    return fig

现在让我们测试一下：

随机点数：

pts = np.random.random((4, 2))
spts, centroid, angles = sort_points(pts)
plot_points(spts, centroid, angles)

点在矩形中：

pts = np.array([[0, 0],  # pt0
                [10, 5], # pt2
                [10, 0], # pt1
                [0, 5]]) # pt3
spts, centroid, angles = sort_points(pts)
plot_points(spts, centroid, angles)

很容易找到包含我们的点的平面的法向量，它只是连接两对点的向量的（归一化）叉积：

plane_normal = np.cross(pts[1, :] - pts[0, :], pts[2, :] - pts[0, :])
plane_normal = plane_normal / np.linalg.norm(plane_normal)

现在，要找到所有点在这个平面上的投影，我们需要知道新坐标系在这个平面上的“原点”和基础。假设第一个点是原点，x 轴连接第一个点和第二个点，由于我们知道 z 轴（平面法线）和 x 轴，我们可以计算 y 轴。

new_origin = pts[0, :]
new_x = pts[1, :] - pts[0, :]
new_x = new_x / np.linalg.norm(new_x)

new_y = np.cross(plane_normal, new_x)

现在，点在新平面上的投影为 this answer:

proj_x = np.dot(pts - new_origin, new_x)
proj_y = np.dot(pts - new_origin, new_y)

现在你有了二维点。运行上面的代码对它们进行排序。

Answer 2

经过几个小时，我终于找到了解决办法。 @Pranav Hosangadi 的解决方案适用于事物的 2D 方面。但是，我在使用他的解决方案的第二部分将 3D 坐标投影到 2D 坐标时遇到了问题。我还尝试按照 this answer, but it did not work as intended. I then discovered an API function called location_3d_to_region_2d() (see docs) 中所述投影坐标，顾名思义，它以给定 3D 坐标的像素为单位获取 2D 屏幕坐标。我不需要首先将任何东西“投影”到 2D 中，让屏幕坐标工作得很好并且更简单。从那时起，我可以使用 Pranav 的函数对坐标进行排序，并稍作调整，使其按照我的第一个 post 屏幕截图中所示的顺序进行排序，我希望它作为列表而不是 NumPy 数组返回。

import bpy
from bpy_extras.view3d_utils import location_3d_to_region_2d
import numpy

def sort_points(pts):
    """Sort 4 points in a winding order"""
    pts = numpy.array(pts)
    centroid = numpy.sum(pts, axis=0) / pts.shape[0]
    vector_from_centroid = pts - centroid
    vector_angle = numpy.arctan2(
        vector_from_centroid[:, 1], vector_from_centroid[:, 0])
    # Find the indices that give a sorted vector_angle array
    sort_order = numpy.argsort(-vector_angle)

    # Apply sort_order to original pts array.
    return list(sort_order)

# Get 2D screen coords of selected vertices
region = bpy.context.region
region_3d = bpy.context.space_data.region_3d

corners2d = []
for corner in selected_verts:
    corners2d.append(location_3d_to_region_2d(
        region, region_3d, corner))

# Sort the 2d points in a winding order
sort_order = sort_points(corners2d)
sorted_corners = [selected_verts[i] for i in sort_order]

谢谢 Pranav 花时间和耐心帮我解决这个问题！

以任何给定方向的缠绕顺序对 4 个 3D 坐标进行排序

Sort 4 3D coordinates in a winding order in any given direction

python

algorithm

math