分解为凸多边形 [英] Decomposition to Convex Polygons
问题描述
这个问题有一点涉及。我写了一个将，我们可以看到反射顶点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
假设'poly'中的顶点以CCW顺序给出
让'good reflex'（更好如果将poly [i]与poly [j]进行比较，则poly [i]处于由射线poly [j-1]，poly [j]和poly [j + 1 ]，poly [j]
如果poly [i]是反射
，则为每个顶点poly [i]
找到由聚[ i-1]并向poly [i]方向延伸（称为下界）
rep在poly（i + 1），poly [i]（称为上界）
给出的射线下吃东西，如果在上下限给定的范围内没有沿多边形边界的顶点边界
创建一个新的顶点，恰好在下边界和上边界点之间的中间（下边界和上边界位于同一边界上）
将poly [i]连接到这个新点
else $ b对于每个顶点poly [j]
，如果poly [j]是一个'好的反射'
，如果没有其他好的反射，b $沿着顶点在上下界给出的范围内迭代找到
保存它（覆盖找到的任何其他顶点）
else
如果它接近其他好的反射顶点，则保存它
else
如果没有好的反射，被发现并且比找到的其他顶点更接近，保存它
connect poly [i]为最佳候选
重复整个算法，对于刚被分割的多边形的两半部分
//找不到反射顶点，然后`poly`凸出
save poly
原来我还没有预料到另外一种情况：[图5]
我的算法会尝试连接顶点1到4，除非我添加另一个检查以确保它可以。因此，我建议使用上面提到的优先级方案将在范围内的所有内容填充到优先级队列中，然后选择最高优先级，检查它是否可以连接，如果没有，请弹出并使用下一个。我认为这使得我的算法O（rn log n），如果我优化它的权利。
我把一个网站放在一起，它粗略地描述了我的发现。我倾向于移动东西，所以当它很热。
我相信规则的五个指向星
对评论进行编辑
根据我的修改理解，修改后的答案是：尝试一个尖锐的五角星（例如，一个手臂足够窄，以至于只有三个点组成了手臂对面的反射点）在被认为是良好反射点的范围内）。至少在纸上通过它看起来会给予更多的优化。然而，对代码的最终解读让我想知道：最接近（即最接近于什么）的含义是什么？
$ b 注意
即使我的回答被接受，但它并不是我们最初想到的反例。正如@Mark在评论中指出的那样，它与最佳状态同时发生的时间从四次到五次。
触发器，触发器
经过进一步的思考，我认为我毕竟是对的。通过简单地确保一对臂具有共线边缘，可以将四个的最佳边界保留在急剧星形中。但是算法发现了五个，即使是修正了。
我得到这个：
死的ImageShack链接
当最优化是这样的：
This question is a little involved. I wrote an algorithm for breaking up a simple polygon into convex subpolygons, but now I'm having trouble proving that it's not optimal (i.e. minimal number of convex polygons using Steiner points (added vertices)). My prof is adamant that it can't be done with a greedy algorithm such as this one, but I can't think of a counterexample.
So, if anyone can prove my algorithm is suboptimal (or optimal), I would appreciate it.
The easiest way to explain my algorithm with pictures (these are from an older suboptimal version)
What my algorithm does, is extends the line segments around the point i across until it hits a point on the opposite edge.
If there is no vertex within this range, it creates a new one (the red point) and connects to that:
If there is one or more vertices in the range, it connects to the closest one. This usually produces a decomposition with the fewest number of convex polygons:
However, in some cases it can fail -- in the following figure, if it happens to connect the middle green line first, this will create an extra unneeded polygon. To this I propose double checking all the edges (diagonals) we've added, and check that they are all still necessary. If not, remove it:
In some cases, however, this is not enough. See this figure:
Replacing a-b and c-d with a-c would yield a better solution. In this scenario though, there's no edges to remove so this poses a problem. In this case I suggest an order of preference: when deciding which vertex to connect a reflex vertex to, it should choose the vertex with the highest priority:
lowest) closest vertex
med) closest reflex vertex
highest) closest reflex that is also in range when working backwards (hard to explain) --
In this figure, we can see that the reflex vertex 9 chose to connect to 12 (because it was closest), when it would have been better to connect to 5. Both vertices 5 and 12 are in the range as defined by the extended line segments 10-9 and 8-9, but vertex 5 should be given preference because 9 is within the range given by 4-5 and 6-5, but NOT in the range given by 13-12 and 11-12. i.e., the edge 9-12 elimates the reflex vertex at 9, but does NOT eliminate the reflex vertex at 12, but it CAN eliminate the reflex vertex at 5, so 5 should be given preference.
It is possible that the edge 5-12 will still exist with this modified version, but it can be removed during post-processing.
Are there any cases I've missed?
Pseudo-code (requested by John Feminella) -- this is missing the bits under Figures 3 and 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] is reflex
find the closest point of intersection given by the ray starting at poly[i-1] and extending in the direction of poly[i] (call this lower bound)
repeat for the ray given by poly[i+1], poly[i] (call this upper bound)
if there are no vertices along boundary of the polygon in the range given by the upper and lower bounds
create a new vertex exactly half way between the lower and upper bound points (lower and upper will lie on the same edge)
connect poly[i] to this new point
else
iterate along the vertices in the range given by the lower and upper bounds, for each vertex poly[j]
if poly[j] is a 'good reflex'
if no other good reflexes have been found
save it (overwrite any other vertex found)
else
if it is closer then the other good reflexes vertices, save it
else
if no good reflexes have been found and it is closer than the other vertices found, save it
connect poly[i] to the best candidate
repeat entire algorithm for both halves of the polygon that was just split
// no reflex vertices found, then `poly` is convex
save poly
Turns out there is one more case I didn't anticipate: [Figure 5]
My algorithm will attempt to connect vertex 1 to 4, unless I add another check to make sure it can. So I propose stuffing everything "in the range" onto a priority queue using the priority scheme I mentioned above, then take the highest priority one, check if it can connect, if not, pop it off and use the next. I think this makes my algorithm O(r n log n) if I optimize it right.
I've put together a website that loosely describes my findings. I tend to move stuff around, so get it while it's hot.
I believe the regular five pointed star (e.g. with alternating points having collinear segments) is the counterexample you seek.
Edit in response to comments
In light of my revised understanding, a revised answer: try an acute five pointed star (e.g. one with arms sufficiently narrow that only the three points comprising the arm opposite the reflex point you are working on are within the range considered "good reflex points"). At least working through it on paper it appears to give more than the optimal. However, a final reading of your code has me wondering: what do you mean by "closest" (i.e. closest to what)?
Note
Even though my answer was accepted, it isn't the counter example we initially thought. As @Mark points out in the comments, it goes from four to five at exactly the same time as the optimal does.
Flip-flop, flip flop
On further reflection, I think I was right after all. The optimal bound of four can be retained in a acute star by simply assuring that one pair of arms have collinear edges. But the algorithm finds five, even with the patch up.
I get this:
removing dead ImageShack link
When the optimal is this:
removing dead ImageShack link
这篇关于分解为凸多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
