相关疑难解决方法(0)

这个问题有点牵扯.我编写了一个将简单多边形分解为凸子多边形的算法,但现在我无法证明它不是最优的(即使用Steiner点(添加顶点)的最小凸多边形数).我的教授坚持认为它不能用这样的贪婪算法来完成,但我想不出一个反例.

所以,如果有人能证明我的算法不是最理想的(或最优的),我会很感激.

用图片解释我的算法的最简单方法(这些是来自较旧的次优版本)

我的算法所做的是将点线周围的线段延伸到相反的边缘上的点.

如果此范围内没有顶点,则会创建一个新的顶点(红点)并连接到该顶点:

如果是在范围内的一个或多个顶点,它连接到最近的一个.这通常会产生最少数量的凸多边形的分解:

但是,在某些情况下,它可能会失败 - 在下图中,如果碰巧首先连接中间的绿线,这将创建一个额外的不需要的多边形.为此,我建议仔细检查我们添加的所有边缘(对角线),并检查它们是否仍然是必要的.如果没有,请将其删除:

但是,在某些情况下,这还不够.看到这个图:

用ac替换ab和cd会产生更好的解决方案.但在这种情况下,没有边缘可以移除,因此这会产生问题.在这种情况下,我建议一个偏好顺序:当决定将反射顶点连接到哪个顶点时,它应该选择具有最高优先级的顶点:

最低的)最近的顶点

med)最接近的反射顶点

最高的近距离反射,当向后工作时也在范围内(很难解释) -

在这个图中,我们可以看到反射顶点9选择连接到12(因为它最接近),当连接到5时会更好.两个顶点5和12都在扩展线定义的范围内段10-9和8-9,但应优先考虑顶点5,因为9在4-5和6-5给出的范围内,但不在13-12和11-12给出的范围内.即,边缘9-12在9处消除反射顶点,但是在12处不消除反射顶点,但是它可以在5处消除反射顶点,因此应优先选择5.

边缘5-12可能仍然存在此修改版本,但可以在后处理期间将其删除.

有没有我错过的案例？

伪代码(由John Feminella请求) - 这是缺少图3和图5中的位

assume vertices in `poly` are given in CCW order
let 'good reflex' (better term??) mean that if poly[i] is being compared with poly[j], then poly[i] is in the range given by the rays poly[j-1], poly[j] and poly[j+1], poly[j]

for each vertex poly[i]
    if poly[i] …

我正在使用OpenGL ES为Android创建2D Openstreetmap渲染应用程序.

不幸的是,我正在努力绘制由大约50或更多点组成的凹多边形.为了实现我的多边形填充,我使用的是GL10.GL_TRIANGLE_FAN:

gl.glVertexPointer(2, GL10.GL_FLOAT, 0, vertBuff); // size = 2 because 2D

gl.glDrawElements(GL10.GL_TRIANGLE_FAN, pointCount, GL10.GL_UNSIGNED_SHORT, indexBuff);

只要我的多边形不是太复杂,这种方法就可以正常工作,例如绘制像这样的多边形完全没问题:

我的问题是,GL_TRIANGLE_FAN始终从第一个点(在本例中为a)开始,然后使用其他2个点绘制三角形,直到整个形状完成.

如果必须绘制更复杂的多边形,这可能会导致问题,如您在此处所见:(在此示例中,流经城市的河流是复杂的多边形)

我现在的问题是如何避免这个问题,以便即使复杂的多边形被正确绘制并填充？

问题在于绘制凹多边形.

使用GL_TRIANGLE_STRIP而不是GL_TRIANGLE_FAN时,正确绘制多边形,但只有它们的点通过三角形连接在一起,多边形本身未填充.

我不明白显示精灵映射到OpenGL三角形的概念.

如果OpenGL ES只绘制三角形和点,那么如何显示/绘制非三角形？

为什么映射到三角形的形状不会失真？

解释:

在我看来,将一个马里奥的精灵映射到一个三角形会产生一个扭曲或裁剪的马里奥.在这种情况下,头部会被挤压或看不见.