按顺时针顺序对球体表面上的3D点进行排序 [英] Sorting 3D points on the surface of a sphere in clockwise order

问题描述

我在单位球体的表面上有一个3D点数组，并且有一个中心点C(也在单位球体的表面上).如何对这些点进行排序，使它们相对于表面按顺时针顺序排列?

I have an array of 3D points on the surface of the unit sphere, and a center point C (also on the surface of the unit sphere). How can I sort these points so they are in clockwise order relative to the surface?

推荐答案

稍晚一些，但是您可以计算法线，然后查看它们是否沿着法线轴沿法线或逆时针方向绕法线或任意单点平均.表面.第二种方法可以减少一个点，但基本相同.

A bit late but you can calculate the normal and then see if along the normal axis they average clockwise or counter clockwise around the normal or around any single point of the surface. The second way you have one less point to track but it's basically the same.

1. 计算表面的中心点(坐标的总和除以坐标的计数)；
2. 从表面点减去中心点；
3. 通过表面法线旋转表面点； **您现在只处理2轴，因为z始终为零；
4. 对相对角度求和(((1,2)中i的sum(atan(p [i]-p [0])))
5. 如果为正，则为顺时针.

1. calculate the center point of the surface (the sum by coordinate divided by the count by coordinates);
2. subtract the center point from the surface points;
3. rotate the surface points by the surface normal; ** you are only dealing with 2 axis now because z will always be zero;
4. sum the relative angles (sum(atan(p[i] - p[0]) for i in (1,2)))
5. if it's positive then it's clockwise.

一些代码...

from math import sqrt, atan2, pi
twopi = 2 * pi
dists = lambda s: sqrt(sum(c*c for c in s))

import numpy as np
trans_y_mat = lambda dx, dz: np.array(((dz,0,dx),(0,1,0),(-dx,0,dz)) \
    , dtype=np.float64)


def p3d_normal(p3d):
  Ux, Uy, Uz = (p3d[1][i] - p3d[0][i] for i in (0,1,2))
  Vx, Vy, Vz = (p3d[2][i] - p3d[0][i] for i in (0,1,2))
  N = (Uy*Vz - Uz*Vy, Uz*Vx - Ux*Vz, Ux*Vy - Uy*Vx)
  d = dists(N)
  return tuple(c / d for c in N)


def p3d_is_clockwise(p3d, p3n=None):
  if p3n is None: p3n = p3d_normal(p3d)
  dnx, dnz = p3n[0]/p3n[1], p3n[2]/p3n[1]
  dn = dists((dnz, dnx))
  mn = trans_y_mat(dnz/dn, dnx/dn)
  p2d = np.matmul(mn, p3d)[:,:2]
  asum = 0.0
  xp,yp = p2d[0]
  ap = 0.0
  for (xn,yn) in p2d[1:]:
    an = atan2(yn-yp, xn-xp)
    asum += (an - ap + pi) % twopi - pi
    xp, yp, an = xn, yp, ap
  return asum >= 0


faces = (((0.0, 0.0, 100.0), (30.9017, 0.0, 95.1057), (15.4508, 26.7617, 95.1057)) \
    , ((0.0, 0.0, 100.0), (15.4508, 26.7617, 95.1057), (-15.4508, 26.7617, 95.1057)) \
    , ((0.0, 0.0, 100.0), (-15.4508, 26.7617, 95.1057), (-30.9017, 0.0, 95.1057)) \
    , ((0.0, 0.0, 100.0), (-30.9017, 0.0, 95.1057), (-15.4508, -26.7617, 95.1057)) \
    , ((0.0, 0.0, 100.0), (-15.4508, -26.7617, 95.1057), (15.4508, -26.7617, 95.1057)) \
    , ((0.0, 0.0, 100.0), (15.4508, -26.7617, 95.1057), (30.9017, -0.0, 95.1057)) \
    , ((30.9017, 0.0, 95.1057), (50.9037, 29.3893, 80.9017), (58.7785, 0.0, 80.9017)) \
    , ((30.9017, 0.0, 95.1057), (15.4508, 26.7617, 95.1057), (50.9037, 29.3893, 80.9017)) \
    , ((15.4508, 26.7617, 95.1057), (29.3893, 50.9037, 80.9017), (50.9037, 29.3893, 80.9017)) \
    , ((15.4508, 26.7617, 95.1057), (0.0, 58.7785, 80.9017), (29.3893, 50.9037, 80.9017)))

for face in faces:
  print(p3d_is_clockwise(face))

输出:

False
False
True
False
False
False
False
False
True
True

这篇关于按顺时针顺序对球体表面上的3D点进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！