jjzjj

c# - 在二维网格中查找所有循环/封闭形状

coder 2024-06-02 原文

我有一个“无限”二维网格，我想检测封闭/完整的“结构”——任何形状的区域，这些区域被四面包围。但是，我需要识别每个单独的闭合电路 - 包括较大的形状(如果有的话)。

在研究这个过程中，我发现了循环检测算法，但我没有看到一种干净/有效的方法来将较大的电路与较小的电路分开。

例如给定以下两个“完整”结构:

0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1

第一个是由 8 个“墙”包围的单个单元格。循环检测使得检测这一点变得微不足道。

第二个示例包含示例一个的两个副本，但它们共用一堵墙。我关心的是三个独立的电路 - 左室、右室和整体结构。

循环算法的多次通过可能有效，但我必须确保我没有回溯已经找到的形状。

我还研究了洪水填充算法，但它似乎假设您已经知道有界区域内的一个点。对于无限的二维网格，如果它不在有效结构中，我需要一个大小限制来强制它放弃。

是否有我遗漏的解决方案或我的想法遗漏了什么？

我只会在添加边界值时进行此“检查”。使用上面的示例，如果我更改任何 0 -> 1，则可能已创建一个新循环，我将运行该逻辑。我不关心识别单独的结构，并且始终有一个原点坐标。

我一直在研究解决方案posted here但它们都是基于已经知道哪些节点连接到其他节点。我已经玩弄了识别每个单独“行”的逻辑，我可以从那里继续前进，但感觉是多余的。

最佳答案

我会这样做:

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 1 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

  1. 用2填充背景

    要确定您是否在背景中，只需转换光线并计算随之而来的 zeores。一旦找到射线长度大于电路尺寸限制的位置，您就得到了起点。

    [0]0-0-0-0-0-0
 0 1 1 1 1 1 0
 0 1 0 1 0 1 0
 0 1 1 1 1 1 0
 0 0 0 0 0 0 0

 2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1 0 1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2

    不要为此使用未绑定(bind)的递归泛洪填充!!! 因为对于“无限” 区域您将堆栈溢出。您可以限制递归级别，如果达到而不是递归，则将点添加到某些队列以供以后进一步处理。这通常会大大加快速度并限制堆栈使用...

  2. 首先找到 0

     2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1[0]1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2

  3. 用 3 填充它

     2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1 3 1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2

  4. 选择 3 附近的所有 1

    这是你的电路。如果您在填充 #3 时记得 bbox，那么您只需要扫描每侧放大一个单元格的区域...选定的单元格就是您的电路。

     2 2 2 2 2 2 2
 2 * * * 1 1 2
 2 * 3 * 0 1 2
 2 * * * 1 1 2
 2 2 2 2 2 2 2

  5. 用 2 填充 3

    这将避免使用已经处理过的电路

     2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1 2 1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2

  6. 在找到任何 0 时循环 #2

  7. 将所有 2 改回 0

     0 0 0 0 0 0 0
 0 1 1 1 1 1 0
 0 1 0 1 0 1 0
 0 1 1 1 1 1 0
 0 0 0 0 0 0 0

关于c# - 在二维网格中查找所有循环/封闭形状，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44979629/

c#封闭codestrongprealgorithmgrid2d

有关c# - 在二维网格中查找所有循环/封闭形状的更多相关文章

  1. ruby - 树顶语法无限循环 - 2

    我脑子里浮现出一些关于一种新编程语言的想法，所以我想我会尝试实现它。一位friend建议我尝试使用Treetop(Rubygem)来创建一个解析器。Treetop的文档很少，我以前从未做过这种事情。我的解析器表现得好像有一个无限循环，但没有堆栈跟踪；事实证明很难追踪到。有人可以指出入门级解析/AST指南的方向吗？我真的需要一些列出规则、常见用法等的东西来使用像Treetop这样的工具。我的语法分析器在GitHub上，以防有人希望帮助我改进它。class{initialize=lambda(name){receiver.name=name}greet=lambda{IO.puts("He

  2. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  3. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

    我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

  4. ruby-on-rails - 跳过状态机方法的所有验证 - 2

    当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested

  5. ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2

    我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("

  6. ruby - Nokogiri 剥离所有属性 - 2

    我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？ 最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog

  7. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  8. ruby - 获取模块中定义的所有常量的值 - 2

    我想获取模块中定义的所有常量的值:moduleLettersA='apple'.freezeB='boy'.freezeendconstants给了我常量的名字:Letters.constants(false)#=>[:A,:B]如何获取它们的值的数组，即["apple","boy"]？ 最佳答案 为了做到这一点，请使用mapLetters.constants(false).map&Letters.method(:const_get)这将返回["a","b"]第二种方式:Letters.constants(false).map{|c

  9. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  10. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

随机推荐