用于查找未知形状的边缘的算法

发布于 2024-12-23 08:05:39 字数 450 浏览 5 评论 0原文

我正在寻找一种有效的算法，可以为我提供随机形状的所有边缘。我可以写一个，但如果有人知道可以优化的现有解决方案，我们将不胜感激，因为这将在手机上运行:)

示例形状：

=====     ==========
=====     \=========
====/      \\     
===/        \\
==/          =======
=/           =======
====================
             =======
             =======
=====\       =======
======\     /=======

对于左上角，我需要以下数据可以有效地给我：[ 0%, 0% ], [ 25%, 0% ]

原文

I'm looking for an efficient algorithm that can give me all the edges of a random shape. I can write one, but if anyone knows of an existing solution that may be optimized, it would be appreciated as this is going to be running on mobile phones :)

Example Shape:

=====     ==========
=====     \=========
====/      \\     
===/        \\
==/          =======
=/           =======
====================
             =======
             =======
=====\       =======
======\     /=======

For the top-left edge, I'd need data that can effectively give me: [ 0%, 0% ], [ 25%, 0% ]

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

甜是你 2024-12-30 08:05:39

似乎没有比嵌套循环和字符检查更优化的了。我可能是错的，但这就是我要开始的地方。

Psueudo

for ( i = 0; i < rows; i++ ){
   for (j = 0; j < cols; j++ ){
      if character[i][j] === '/' or '|' or '\'  or '-'
         // Edge-Found logic.
   }
}

编辑

我撤销我之前的回答。我想了更多，您可以通过在第一个找到的字符边缘实例处停止迭代并搜索该点周围的所有直接节点来查找另一个边缘来进一步优化。冲洗并重复，直到您完全回到起始边缘。这个问题很容易递归，并通过在绘制形状时创建链接列表来打开编程选项的世界。

让我想起二年级计算机科学中的一些老鼠迷宫问题。很好的问题——很高兴能时不时地看到有趣的问题！ :D

另外 - 对于任何其他好奇的人，您可以查看“图论”来了解像这样的各种很酷的问题。它基本上是互联网、谷歌地图和各种其他很酷的数据库应用程序的动力（例如，它是 FaceBook 数据库背后的理论，几乎独自负责其服务的速度......听说过 OpenGraph？）

It seems like you can't get any more optimized than a nested loop and a character check. I could be wrong, but that's where I'd start.

Psueudo

for ( i = 0; i < rows; i++ ){
   for (j = 0; j < cols; j++ ){
      if character[i][j] === '/' or '|' or '\'  or '-'
         // Edge-Found logic.
   }
}

EDIT

I rescind my previous answer. I thought about it some more, and you could optimize even further by stopping the iteration at the first found instance of a character edge and searching all immediate nodes around that point for another edge. Rinse and repeat until you've worked your way all the way back to your starting edge. This problem lends itself easily to recursion and opens up a world of programming options to by creating a linked list while mapping out the shape.

Reminds me of some of the mouse maze problems in 2nd year computer science. Excellent question -- it's great to see fun ones every now and again! :D

Also - for anybody else that's curious, you can check out "graph theory" for all sorts of cool problems like this one. It's basically what powers the internet, google maps, and all sorts of other cool database applications (for instance, it's the theory behind FaceBook's database and is almost single-handedly responsible for the speed of their service...Ever heard of OpenGraph?)

回复收藏 0 原文

~没有更多了~