介绍
今年夏天,我的工作在Västerås的技术部分。 我曾在同一家公司,并连续三个夏天在大致相同的办公室。 这项工作是非常技术性的,有趣和具有挑战性的。 在办公室与许多其他暑期工,我发现我有责任和共同任务与工作。 具体来说,我的工作,以简化计算,使用大多MATLAB GUI编程和Java的开发工具。 MATLAB的风格,使新的面向对象的代码比前几年更为清晰。
问题
有一天,我面临一个小的挑战。 简化它找到一个多边形包围了一套复杂点,散落在飞机集中。 起初,我没有发现的功能,在MATLAB,当然这是很奇怪的。 因此,我决定找到一个自定义的算法。 在这篇文章中,我将描述我的算法。
我Alogritm
我描述了我的BE算法使用图2。 首先,我将解释在寻找住房困难。 事情是所有点都在无序结构。 如果点围绕一个中心点排列,可以使用它们的顺序和距离,从中心来解决这个问题。 然而,它需要至少为O(n日志(N)),以线性排序。 我的算法工作中的无序列表,甚至可能将更多的时间,因为我还没有得出任何证据。
这个想法肯定是开始,我在x方向的点,然后找到K值变成最高点。 即找出:
MAX(k_i)=(y_min - y_i)/(x_min - x_i的)I = [所有项目],这给你点P_2。
所有小于y值X_min点可能被忽略。 与x的值小于P_2所有点也可以排除进一步阅读。
K_2然后找到降到最低点发现:
K_1 - (y_1 - y_i)/(X_1 - x_i的)I = [所有点都不能排除]
同样发现k_a一般由:
分钟(k_a-1 - (y_a-1 - y_i)/(x_a-1 - x_i的))= [不排除所有的点]
计算多边形的上半部分,直到你得到的最高点,这是在x方向。 此后,同样的算法,多边形的下半部分。
性能
该算法的性能取决于多少分,最终在多边形。 我使许多linjärsök的清单,它在多边形点。 这意味着,复杂度为O(N *搜索)。 在最佳的多边形数量的点是根据10和25之间的机会点。 因此算法是比较快的。
码
代码是不公开的。
MATLAB解决方案 - 凸壳
我的算法做同样的事情作为一个MATLAB函数convhull 。 凸包是一个封闭的多边形或凸体的英文单词。 另一种很好的资源是http://en.wikipedia.org/wiki/Convex_hull_algorithms解释说,理论的最短时间找到一个凸壳为O(n日志(N))。








