我需要在二维平面上的几个顶点中找到一个表面积最小的不规则多边形。
不，这不是家庭作业。虽然我希望我现在回到学校。
对于如何构建多边形有一些要求。假设我在 8x8 网格上绘制了 3 种不同类型的顶点(红色、绿色、蓝色)。我需要扫描此网格中满足红、绿、蓝组合要求的所有顶点，并选择表面积最小的顶点。
获取不规则多边形的表面积非常简单。我主要关心的是高效扫描所有可能组合的性能。
有关示例，请参见下图。所有三种类型都用于制作多边形，但圈出的一种具有最小的表面积，这是我的目标。
与我尝试制作的原型(prototype)相比，这个场景得到了简化。多边形将由数十个(如果不是数百个)顶点构成，并且网格将大得多。此外，这将是一个 24/7 全天候运行的过程。
我在想也许我应该按类型组织顶点并将它们分解成单独的数组。然后以分层方式遍历数组以计算所有组合的表面积。然而，这种方法似乎很浪费。
最佳答案
这是一个基于分支定界的版本，有一些改进。
1) 将网格分解为四叉树，根据需要在节点中添加注释。
2) 在四叉树中找到具有每种类型节点之一的最低节点。这为您提供了一个起始解决方案，该解决方案至少应该足以加快其余搜索的速度。
3) 进行递归搜索，在我说猜测的地方采用所有可能的分支，在适用的情况下首先选择最有希望的候选者:
3a) 猜测最不常见类型的顶点。
3b) 使用四叉树中点的相对位置来排序你的猜测，猜测下一个最不常见类型的顶点，以便按照距离原始点的距离递增顺序猜测它们...
3z) 你有一组完整的顶点。
在每个步骤 3？您有一组部分顶点，我认为它为您提供了包括这些顶点在内的任何完整解决方案的区域的下限(它是顶点凸包内的区域吗？)。您可以丢弃任何已经至少与迄今为止最大的解决方案一样大的部分解决方案。如果您可以接受 X% 不准确的答案，则可以丢弃目前最大解决方案的 X% 范围内的任何部分解决方案。希望这会修剪您在 (3) 中导航的可能性树，使其足够易于处理。
关于c# - 从顶点组合中找到最小的不规则多边形(性能关键)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7373918/
如何在ruby中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL
我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha
我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'
C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.
如何找到调用此方法的位置？defto_xml(options={})binding.pryoptions=options.to_hifoptions&&options.respond_to?(:to_h)serializable_hash(options).to_xml(options)end 最佳答案 键入caller。这将返回当前调用堆栈。文档:Kernel#caller.例子[0]%rspecspec10/16|===================================================62=====
我正在尝试学习Ruby词法分析器和解析器(whitequarkparser)以了解更多有关从Ruby脚本进一步生成机器代码的过程。在解析以下Ruby代码字符串时。defadd(a,b)returna+bendputsadd1,2它导致以下S表达式符号。s(:begin,s(:def,:add,s(:args,s(:arg,:a),s(:arg,:b)),s(:return,s(:send,s(:lvar,:a),:+,s(:lvar,:b)))),s(:send,nil,:puts,s(:send,nil,:add,s(:int,1),s(:int,3))))任何人都可以向我解释生成的
给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我
我使用的第一个解析器生成器是Parse::RecDescent，它的指南/教程很棒，但它最有用的功能是它的调试工具，特别是tracing功能(通过将$RD_TRACE设置为1来激活)。我正在寻找可以帮助您调试其规则的解析器生成器。问题是，它必须用python或ruby编写，并且具有详细模式/跟踪模式或非常有用的调试技术。有人知道这样的解析器生成器吗？编辑:当我说调试时，我并不是指调试python或ruby。我指的是调试解析器生成器，查看它在每一步都在做什么，查看它正在读取的每个字符，它试图匹配的规则。希望你明白这一点。赏金编辑:要赢得赏金，请展示一个解析器生成器框架，并说明它的
我想合并多个事件记录关系例如，apple_companies=Company.where("namelike?","%apple%")banana_companies=Company.where("namelike?","%banana%")我想结合这两个关系。不是合并，合并是apple_companies.merge(banana_companies)=>Company.where("namelike?andnamelike?","%apple%","%banana%")我要Company.where("名字像？还是名字像？","%apple%","%banana%")之后，我会写代
下面的代码工作正常:person={:a=>:A,:b=>:B,:c=>:C}berson={:a=>:A1,:b=>:B1,:c=>:C1}kerson=person.merge(berson)do|key,oldv,newv|ifkey==:aoldvelsifkey==:bnewvelsekeyendendputskerson.inspect但是如果我在“ifblock”中添加return，我会得到一个错误:person={:a=>:A,:b=>:B,:c=>:C}berson={:a=>:A1,:b=>:B1,:c=>:C1}kerson=person.merge(berson
