我正在使用Delaunay来对凹多边形进行三角测量,但它会填充凹陷.如何自动删除多边形边界外的三角形？

我正在寻找一种打包算法,它将正多边形缩小为矩形和直角三角形.该算法应该尝试使用尽可能少的这种形状,并且应该相对容易实现(考虑到挑战的难度).

如果可能,这个问题的答案应该解释建议算法中使用的一般启发式方法.

我有一个pointlist = [p1,p2,p3 ...]其中p1 = [x1,y1],p2 = [x2,y2] ......

我想使用scipy.spatial.Delaunay对这些点云进行三角测量,然后绘制它

我怎样才能做到这一点 ？

Delaunay的文档非常缺乏

到目前为止我有这个代码

from subprocess import Popen, PIPE
import os


os.environ['point_num'] = "2000"

cmd = 'rbox $point_num D2 | tail -n $point_num'
sub_process = Popen(cmd, shell=True,stdout=PIPE,stderr=PIPE)
output = sub_process.communicate()
points = [line.split() for line in output[0].split('\n') if line]
x = [p[0] for p in points if p]
y = [p[1] for p in points if p]

import matplotlib.pyplot as plt
plt.plot(x,y,'bo')

from scipy.spatial import Delaunay

dl = Delaunay(points)
convex …

我最近问过这个问题,关于如何将凹多边形切割成凸多边形,我建议做三角剖分或多边形分区.

我正在使用的库(SFML\Box2D)只采用凸形.

这就是我想知道的:

1. 多边形分区或多边形的三角测量更快吗？

2. Polygon Partitioning如何工作/你是如何做到的？

不要忘记三角测量不需要凸起的形状......

我正在努力让OpenCV triangulatePoints功能起作用.我正在使用从光流生成的点匹配功能.我正在使用一个移动相机的两个连续帧/位置.

目前这些是我的步骤:

给出了内在函数,看起来像人们期望的那样:

2.6551e+003  0.           1.0379e+003
0.           2.6608e+003  5.5033e+002
0.           0.           1.

然后,我基于(高度精确的)GPS和相对于GPS的摄像机位置计算两个外部矩阵([R | t]).请注意,GPS数据使用荷兰周围的笛卡尔坐标系,该坐标系使用米作为单位(因此不需要奇怪的lat/lng数学运算).这产生以下矩阵:

接下来,我简单地删除这些矩阵的底行并将它们与内在矩阵相乘以得到投影矩阵:

projectionMat = intrinsics * extrinsics;

这导致:

我的图像点只包含第一组的所有像素坐标,

(0, 0)...(1080, 1920)

和所有像素坐标+他们计算的第二组光流.

(0 + flowY0, 0 + flowX0)...(1080 + flowYN, 1920 + flowXN)

为了计算3D点,我将图像点(以OpenCV期望的格式)和投影矩阵提供给triangulatePoints函数:

cv::triangulatePoints(projectionMat1, projectionMat2, imagePoints1, imagePoints2, outputPoints);

最后,我将outputPoints齐次坐标转换为它们的第四个坐标(w)并删除该坐标.

我最终得到的是一些奇怪的锥形点云:

现在我已经尝试了我能想到的每种调整组合(反转矩阵,改变X/Y/Z顺序,反转X/Y/Z轴,改变乘法顺序......),但是一切都会产生类似奇怪的结果.确实给我带来更好结果的一件事就是将光流值乘以0.01.这导致以下点云:

这仍然不是很完美(远离相机的区域看起来非常弯曲),但更像我期望的那样.

我想知道是否有人能发现我做错了什么.我的矩阵看起来不错吗？输出我是否与某个问题有关？

我非常肯定的是,它与GPS或光流无关,因为我测试了多个帧,它们都产生相同类型的输出.我真的认为它与三角测量本身有关.

建立

给定凸包内的一些节点集,假设该域包含一个或多个凹面区域:

其中蓝点是点,黑线表示域.假设点被保持为points长度的2D数组n,其中n是点对的数量.

然后让我们使用类似scipy.spatial的Delaunay方法对点进行三角测量:

如您所见,人们可能会遇到穿过域的三角形的创建.

题

删除任何跨越域外的三角形的好算法方法是什么？理想但不一定,单面边缘仍然保留域形状(即,没有去除三角形的主要间隙).

由于我的问题似乎继续得到大量的活动,我想跟进我目前正在使用的应用程序.

假设您已定义边界,则可以使用光线投射算法来确定多边形是否在域内.

去做这个:

1. 取每个多边形的质心为C_i = (x_i,y_i).
2. 然后,想象一条线L = [C_i,(+inf,y_i)]:也就是说,一条横跨东部超过域末端的线.
3. 对于边界s_i中的每个边界段S,检查交叉点L.如果是,请向内部计数器添加+1 intersection_count; 否则,什么都不添加.

4. 后之间的所有交叉点的数量L和s_i for i=1..N计算:

   if intersection_count % 2 == 0:
       return True # triangle outside convex hull
   else:
       return False # triangle inside convex hull
   

   Run Code Online (Sandbox Code Playgroud)

如果没有明确定义边界,我发现将形状"映射"到布尔数组并使用邻居跟踪算法来定义它是有帮助的.请注意,此方法假设一个实体域,您需要对其中包含"漏洞"的域使用更复杂的算法.

概括

我正在尝试对两张图像中的点进行三角测量，但根本没有得到准确的结果。

细节

这就是我正在做的：

1. 测量现实世界坐标中的 16 个物点。

2. 确定每幅图像 16 个物点的像素坐标。

3. 使用 cv2.solvePnP() 获取每个摄像机的 tvec 和 rvec。

4. 使用 cv2.projectPoints 验证 tvecs 和 rvecs 是否将给定的 3D 点重新投影到正确的图像坐标（它确实有效）。例如：

   img_point_right = cv2.projectPoints(np.array([[0,0,39]], np.float), 
                                       right_rvecs, 
                                       right_tvecs,
                                       right_intrinsics,
                                       right_distortion)
   

   Run Code Online (Sandbox Code Playgroud)

5. 验证完毕后，使用以下公式获取旋转矩阵：

   left_rotation, jacobian = cv2.Rodrigues(left_rvecs)
   right_rotation, jacobian = cv2.Rodrigues(right_rvecs)
   

   Run Code Online (Sandbox Code Playgroud)

   然后是投影矩阵：

   RT = np.zeros((3,4))
   RT[:3, :3] = left_rotation
   RT[:3, 3] = left_translation.transpose()
   left_projection = np.dot(left_intrinsics, RT)
   
   RT = np.zeros((3,4))
   RT[:3, :3] = right_rotation
   RT[:3, 3] = right_translation.transpose()
   right_projection = np.dot(right_intrinsics, RT)
   

   Run Code Online (Sandbox Code Playgroud)

6. 在进行三角测量之前，使用 cv2.unactorPoints 取消扭曲点。例如：

   left_undist = cv2.undistortPoints(left_points, 
                                      cameraMatrix=left_intrinsics, …

   Run Code Online (Sandbox Code Playgroud)

我试图对多边形进行三角测量,以便在3d模型中使用.当我尝试在多边形上使用耳朵方法,点下面点,我得到红线所在的三角形.由于这些三角形内没有其他点,这可能是正确的.但我希望它只对黑线内的区域进行三角测量.有人知道会有这样的算法吗？

我正在使用效果很好的三角测量代码(它处理带孔的多边形并与JTS集成)但显然它不尊重三角形的缠绕.一些输出三角形以一种方式缠绕,一些以另一种方式缠绕.

我有可能确定并纠正这些异常三角形的缠绕吗？可能使用来自相邻三角形的信息,但当然越简单越好.

我想在两组多边形之间进行三角测量.一组总是在另一组内,事实上,外多边形被创建为原始集的偏移.如果它们在同一平面上,三角测量将很容易,但我想通过将外多边形移动到平行但不同的平面来增加深度.我使用的常用三角测量方法(glu tesselator)不起作用.会有替代方案吗？