标签: computational-geometry

我决定创建一个简单的演示,将多边形划分为三角形集.到目前为止我得到的是:

给出顺序顶点列表(P1)形成多边形边缘(多边形在多数情况下不是凸面); 需要一个三角形集

遍历多边形P1内的所有顶点并找到一个(v),这将满足下一个子句:

1. 从多边形中移除v并将新的一个保存到P2前一个顶点到v连接到它的下一个顶点,形成一条不穿过任何P2边的线

2. v不在P2内

如果满足这些,我们可以用(P2 + 三角形(prev(v),v,next(v))替换P1 并重复此动作,直到P1包含多于3个顶点.

所以,问题是:这个算法是否正确以及如何使用C/C++以最明显和最简单的方式实现它？

我遇到了这个链接http://www.mathopenref.com/coordpolygonarea2.html

它解释了如何计算多边形的面积,并帮助确定我们输入的多边形顶点是顺时针还是逆时针.

如果面积值为+ ve,则为顺时针,如果为-nv,则为逆时针.

我的要求是仅确定它是顺时针还是逆时针.此规则是否正常工作(尽管链接中提到了一些限制).我只有正多边形(不复杂,没有自交叉),但顶点更多.

我对面积值精度不感兴趣,只是为了知道环的旋转.

对此有任何其他想法.

输入:两个3d凹面多边形A和B,单位矢量d.没有多边形在时间t = 0 处相交.预期方向d不会经常变化,因此需要一些预处理阶段.

问题:在某个时间t确定两个凹多边形A和B是否可以在方向d上相交.换句话说:如果我们在给定方向d上移动一个多边形,它是否会与另一个多边形相交？

输出: 1 - 交叉存在,0 - 其他.

假设我们有带顶点的凸多边形

(v0,v1,....vn)

我的目的是确定对于给定点,p(x,y)连接此点和多边形的任何顶点的任何线段是否在多边形内或甚至对于给定的两点

p(x0,y0)  `p(x1,y1)`

连接这两个点的线段是多边形内？我已经搜索了很多关于这个的网站,但我仍然感到困惑,一般来说我认为我们必须比较顶点的坐标,并通过确定哪个点的坐标小于或大于另一个点的坐标,我们可以确定任何线段的位置,但是我不确定这是多么正确,请帮助我

我需要找到两个段(线)之间的"内部"角度,小于180度.有什么快速的方法在python2.7中做到这一点？(Shapely似乎没有这个功能)

segment1是x1,y1,x2,y2

segment2是x3,y3,x4,y4

给定平面中的一组点,我想找到包含所有点的最小多边形.更确切地说,该多边形的顶点必须是原始点集的子集.

最简单的方法是找到凸包,可以使用格雷厄姆的扫描算法在O(N log(N))时间内计算,但我理想的是要放弃多边形为凸的要求.对此有任何标准方法吗？我认为这个问题有点难度,因为在我看来并不能保证是一个独特的解决方案.

我有一个UIImageView显示一个分为六个相等三角形的圆圈,对应于:

• area1在0-60度之间
• area2在> 60-120度之间
• area3在> 120-180度之间
• area4在> 180-240度之间
• area5在> 240-300度之间
• area6在> 300-360度之间

圆圈类似于以下内容(原谅我糟糕的绘图):

我想从水龙头所在区域的接触点得出.例如,如果用户点击圆圈的右上角,则该区域应为区域2:"> 60-120".

我得到的输入数据是:

• 包含圆的框架的宽度和高度(例如200像素宽,200像素高)
• 点击坐标

考虑到上述输入数据,有关如何推断抽头点落在哪个区域的任何建议？

是否存在一种算法,对于给定的2d位置,在恒定时间内找到由n-1个线段(n个线顶点)组成的2d折线上的最近点？天真的解决方案是遍历所有段,测试每个段到给定位置的最小距离,然后对于最近的段,计算到给定位置的精确最近点,其具有O(n)的复杂度.不幸的是,硬件约束阻止我使用任何类型的循环或指针,这意味着也没有像四叉树这样的优化来对O(log n)中最近的段进行分层查找.

理论上我有无限的时间来预先计算可用于查找的任何数据结构,这个预计算可能是任意复杂的,只有运行时自身的查找需要在O(1)中.然而,硬件的第二个约束是我只有非常有限的内存,这意味着为每个数字可能的域位置找到线上最近的点并将其存储在一个巨大的数组中是不可行的.换句话说,内存消耗应该是O(n ^ x).

所以它归结为如何在没有任何循环的情况下找到2d位置的折线或其索引的最近段.这可能吗？

编辑:关于给定的位置......它可以是非常随意的,但仅考虑一条线的较近邻域中的位置是合理的,由恒定的最大距离给出.

最近我一直在使用OpenCASCADE(准确地说是PythonOCC)进行一些CAD操作,包括网格形状,并偶然发现了这个类: BRepMesh_IncrementalMesh.

我没有找到关于什么theLinDeflection和theAngDeflection参数含义的任何暗示- 并且想要了解更多关于此的信息.

我将不胜感激任何关于这一主题的阅读材料/提示/解释.

我目前正在使用的算法存在一些问题。我希望它成为一个界限。

这是当前行为的示例：

这是通缉行为的MSPaint示例：

C＃中凸包的当前代码：https : //hastebin.com/dudejesuja.cs

所以这是我的问题：

1）这有可能吗？

R：是的

2）这甚至被称为凸包吗？（我不这么认为）

R：不，这叫做边界，链接：https : //www.mathworks.com/help/matlab/ref/boundary.html

3）与传统的凸包相比，这是否会降低性能？

R：据我研究，它应该具有相同的性能

4）使用伪代码或类似方法的此算法示例？

R：尚未回答，或者我尚未找到解决方案