草庐IT

python - 查找由一组线创建的平面的所有分区

coder 2023-08-23 原文

我有一组线(形式为 y = mx + b 的线性函数)(其中 120 条!)，如果我将它们全部绘制成图，那么它们将划分 R^2 平面。这些线不一定穿过原点。

查找由一组这样的行创建的所有分区的最有效方法是什么？就个人而言，我很难想出任何方法，更不用说有效的方法了。为了更清楚，我包括以下仅 4 行的图像:

分区的一个例子是集合 {(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7} ，这是第一象限中由红、黄、绿线创建的分区。另一个例子是 {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2} , 这是第一象限中由蓝线、红线和绿线包围的三角形。

非 分区的示例是 {(x,y)|5x+3 <= y <= -30x+28} ，这是由上面的绿线和下面的蓝线所界定的集合。这不是一个分区，因为其中包含多个分区(例如上面的第二个分区)，或者与它重叠。套装{(x,y)|5x+3 <= y <= -30x+28 && 90x+7 <= y} , 然而, 将是一个分区。

所需的输出将是此类集合的完整列表: {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2},{(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}...等。当然，它们不必以这种表示法给出。

我不确定如何解决这个问题，因此，不幸的是，我无法提供太多我尝试过的方法。理想情况下，我想在 R、Python、Mathematica 或 MATLAB 中执行此操作，但此时我对任何选项都持开放态度。

编辑:由于符号似乎有问题，我会稍微澄清一下。简单地获取点的条件列表就足够了，这样满足该条件的所有点都将准确地定义一个分区。例如，一长串交叉路口就可以了:y <= 5x+3 && y >= 90x+7 && y<= -30x+28是定义分区的完美输出。当然，所需的输出是此类分区的完整列表(如上定义)。

最佳答案

查找分区数遵循以下公式(当没有 3 条或更多条线在同一点相交时 - 此假设贯穿本文):

num_partitions = (n_lines * (n_lines + 1) / 2 ) + 1

可以找到解释here , 和另一个 there .

The desired output would be a complete list of such sets: {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2}, {(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}... etc... They don't have to be given in this notation, of course.

缺乏精确的符号是这里的一个障碍。

下面是我的信封尝试的背面。如您所见，可以根据编号区域与每条线的相对位置来识别编号区域。
有 5 个空集，如果行顺序改变，它们将不相同。
用线划分平面上的一组点可能会更容易，试图确定哪个点属于哪个集合；在这种情况下，探索 2^n潜在的分区，返回它们的内容会很容易。 (比试图找到一个好的符号来识别抽象集更容易)

这并没有完全回答你的问题，但对于能够/愿意进一步插入这个问题的人来说可能是一个很好的陈述点。
这是关于 partitioning a set of points with two lines in the plane. 的注释 这是一个不同的问题，但它的一些方法可能有用。

其他方法:

识别由线段形成的多边形，计算一个凸包，确定一个点是否在该包内。

关于python - 查找由一组线创建的平面的所有分区，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47466806/

python的codeampltmatlabmathwolfram-mathematicacomputational-geometry

有关python - 查找由一组线创建的平面的所有分区的更多相关文章

  1. ruby - 如何在 Ruby 中顺序创建 PI - 2

    出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

  2. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  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 - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  5. ruby-on-rails - 无法使用 Rails 3.2 创建插件？ - 2

    我对最新版本的Rails有疑问。我创建了一个新应用程序(railsnewMyProject)，但我没有脚本/生成，只有脚本/rails，当我输入ruby./script/railsgeneratepluginmy_plugin"Couldnotfindgeneratorplugin.".你知道如何生成插件模板吗？没有这个命令可以创建插件吗？PS:我正在使用Rails3.2.1和ruby​​1.8.7[universal-darwin11.0] 最佳答案 随着Rails3.2.0的发布，插件生成器已经被移除。查看变更日志here.现在

  6. ruby - 如何使用 RSpec::Core::RakeTask 创建 RSpec Rake 任务？ - 2

    如何使用RSpec::Core::RakeTask初始化RSpecRake任务？require'rspec/core/rake_task'RSpec::Core::RakeTask.newdo|t|#whatdoIputinhere?endInitialize函数记录在http://rubydoc.info/github/rspec/rspec-core/RSpec/Core/RakeTask#initialize-instance_method没有很好的记录；它只是说:-(RakeTask)initialize(*args,&task_block)AnewinstanceofRake

  7. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  8. 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

  9. 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

  10. Ruby rpartition 与分区？ - 2

    rpartition和partition有什么区别？我已经阅读了文档，但我认为它们是一样的。只是那些出现在后来的ruby​​版本中吗？ 最佳答案 以下示例将有助于识别差异:"abccba".partition("b")#=>["a","b","ccba"]"abccba".rpartition("b")#=>["abcc","b","a"]所以区别在于rpartition搜索最右边的匹配项，而不是最左边的匹配项。 关于Rubyrpartition与分区？，我们在StackOverflow

随机推荐