多项式弧算法？ [英] Polynom arc algorithm?

问题描述

在课堂上我们看到了跟随着的问题，但我没有undestand的解决方案。不要任何人都可以有更详细的解释我的方法来解决这个问题，或者给我一个更好的解决方案：

  

假定n个点在平面中给出。找到多边形弧用n-1侧面其顶点是给定的点，和其边不相交。（相邻侧面可以形成一角度180）。操作的数量shold是n阶数为n的。

老师的解决办法是：

  

排序所有的点相对于该x坐标;当x坐标相等，采取y坐标进去，然后连接所有顶点通过线段（以该顺序）。

解决方案

你的老师的解决方法是（幸运的）好。我会尽力想象这个给你。

刚刚画上一个情节点。然后你就可以得出最左边的点到下一个点的直线。通过这种方式，连接的是正确的所有问题。

如果所有的点都具有不同的x坐标，那会工作了，没有线将穿越：

对于具有相同的X坐标点，我们先去最低（最小y坐标），然后上去。不能横穿马路那边。

In class we saw the followin problem but i didnt undestand the solution. Do anybody could explain me with more detail the procedure to solve this problem or give me a better solution?:

Assume that n points in the plane are given. Find a polygonal arc with n-1 sides whose vertices are given points, and whose sides do not intersect.(Adjacent sides may form a 180 angle). The number of operations shold be of order n log n.

The teacher solution was:

Sort all the points with respect to the x-coordinate; when x-coordinates are equal, take the y-coordinate into account, then connect all the vertices by line segments(in that order).

解决方案

The solution of your teacher is (fortunately) good. I'll try to visualize this for you.

Just draw the points on a plot. Then you can draw a line from the leftmost point to the next point. This way, connect all points going to the right.

If all the points have different x-coordinates, that'll work out, and no lines will cross:

For the points with the same x-coordinates, we first go to the lowest (smallest y-coordinate) and then go up. No crossing there, either.

这篇关于多项式弧算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！