一种检测直线与凸多边形是否相交的O(n)算法是检查多边形的任一边是否与直线相交，并查看相交点数是奇数还是偶数。 是否存在渐进更快的算法，例如O(log n)的算法？

我有一个三角网格。假设它看起来像一个崎岖的表面。我想能够找到所有落在网格周围边界上的边缘。（忘记内部顶点） 我知道我必须找到只与一个三角形相连的边缘，并将所有这些收集在一起，那就是答案。但是我想确保这些边缘的顶点按顺时针顺序环绕形状。 我想这样做是因为我想获得网格外部的多边形线条。 我希...

我找到了一些解决方案，但它们太凌乱了。

假设我有一个在六维空间中给出的点云，我可以根据需要使其密度足够大。这些点最终落在较低维度的多面体表面上（即点向量（x1，x2，... x6）似乎共面）。 我想找到这个未知多面体的顶点，我的当前尝试利用qhull算法，通过Python中的scipy接口进行。开始时，我只会收到错误消息，显然是由...

给定一个凸多边形，我想要在保持其直径的同时扩大它的形状（如“最大面积”）。 直径定义为可以放置在多边形内的最长线段的长度。 由于多边形是凸的，因此我假设可以通过扫描所有顶点对来找到该直径。 例如，给出一个等边三角形作为输入多边形，三角形的直径是任何一条边的长度；将其平滑处理将导致如图所示的3...

我将使用Scipy和ConvexHull库来创建凸包。据我所知，它会调用QHull。 当我要添加的点没有“完整维度”时，就会出现问题。例如： from scipy.spatial import ConvexHull import numpy as np points = np.append...

我最近提出了这个问题，询问如何将凹多边形切割成凸多边形，并被建议采用三角剖分或多边形分割。 我正在使用的库（SFML\Box2D）仅接受凸形状。 以下是我想知道的内容： 1. 多边形分割或三角剖分哪个更快？ 2. 多边形分割如何工作/如何实现？ 不要忘记，三角测量也不需要制作凸多...

我想检查一组N个点是否描述了一个凸多边形。 我在想是否有一个好的算法来解决这个问题？ 以下是我考虑的一些方法： 1. 凸包算法: 如果该集合等于其凸包，则其为凸多边形。这种算法的复杂度为O(n*LN(N))。但我感觉像是杀鸡焉用牛刀。 2. 角度分析： 然后我想检查连续两个向量的角...