在任何給定方向上按纏繞順序對4個3D坐標進行排序

我需要按如下圖所示的纏繞順序對選擇的 3D 坐標進行排序。右下角的頂點應該是陣列的第一個元素，左下角的頂點應該是陣列的最后一個元素。考慮到相機面向這些點的任何方向以及這些點的任何方向，這需要作業。由于“左上”、“右下”等是相對的，我假設我可以使用相機作為參考點？我們也可以假設所有 4 個點都是共面的。

我正在使用 Blender API（撰寫 Blender 插件），如果有必要，我可以訪問相機的視圖矩陣。從數學上講，如果可以的話，這甚至可能嗎？也許我把事情復雜化了？

由于 Blender API 在 Python 中，我將其標記為 Python，但我可以使用偽代碼或根本沒有代碼。我主要關心如何在數學上處理這個問題，因為我不知道從哪里開始。

uj5u.com熱心網友回復：

由于您假設這四個點是共面的，因此您需要做的就是找到質心，計算從質心到每個點的向量，然后按向量的角度對點進行排序。

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)

It's easy enough to find the normal vector of the plane containing our points, it's simply the (normalized) cross product of the vectors joining two pairs of points:

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

Now, to find the projections of all points in this plane, we need to know the "origin" and basis of the new coordinate system in this plane. Let's assume that the first point is the origin, the x axis joins the first point to the second, and since we know the z axis (plane normal) and x axis, we can calculate the y axis.

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)

Now, the projections of the points onto the new plane are given by this answer:

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

Now you have two-dimensional points. Run the code above to sort them.

uj5u.com熱心網友回復：

幾個小時后，我終于找到了解決方案。@Pranav Hosangadi 的解決方案適用于事物的 2D 方面。但是，我在使用他的解決方案的第二部分將 3D 坐標投影到 2D 坐標時遇到了麻煩。我還嘗試按照此答案中的描述投影坐標，但它沒有按預期作業。然后我發現了一個名為的 API 函式location_3d_to_region_2d()（請參閱檔案)，顧名思義，獲取給定 3D 坐標的 2D 螢屏坐標（以像素為單位）。首先，我不需要將任何東西“投影”到 2D 中，讓螢屏坐標作業得非常好，而且要簡單得多。從那時起，我可以使用 Pranav 的函式對坐標進行排序，并稍作調整，以按照我第一篇文章的螢屏截圖中所示的順序得到它，我希望它以串列而不是 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 花費您的時間和耐心幫助我解決這個問題！

標籤：

上一篇：Python：如何計算給定兩個陣列的多個x截距？

下一篇：GroupLayout的問題：調整視窗大小時組件突然“爆裂”