草庐IT

javascript - 将弱简单多边形拆分为真正的简单多边形或多边形

coder 2024-07-20 原文

我想将弱简单多边形划分为简单多边形。

背景

用例是使用 Javascript Clipper 来简化已简化(联合)的多边形。 . Javascript Clipper 以及 original Clipper's SimplifyPolygon()函数去除自相交并合并公共(public)边,但它不能产生真正的简单多边形。输出用于three.js,其中有TriangulateShapes()这需要多边形很简单。 Three.js 接受具有一个轮廓和零个或多个孔的多边形结构。

输入,弱简单多边形

弱简单多边形不能有连续重复顶点(真正的重复点),也不能有孔(岛)或自相交(边与其他边交叉),但可以有非连续多顶点(顶点恰好具有相同的坐标但不是连续的)。输入多边形可以有 CW 或 CCW 缠绕顺序,这意味着 CW 输入是外部多边形,CCW 是一个孔。输入是 CW 或 CCW 多边形。

输入是一个多边形点数组,例如:

//这是弱简单多边形的真实示例:

var input = [{"X":270,"Y":520},{"X":130,"Y":490},{"X":210,"Y":250},{"X":60,"Y":170},{"X":130,"Y":490},{"X":20,"Y":410},{"X":60,"Y":300 },{"X":60,"Y":20},{"X":780,"Y":40},{"X":680,"Y":180},{"X":460 ,"Y":130},{"X":210,"Y":250},{"X":320,"Y":100},{"X":220,"Y":80}, {"X":210,"Y":250},{"X":520,"Y":250},{"X":680,"Y":180},{"X":770,"Y":480},{"X":540,"Y":470},{"X":520,"Y":250},{"X":380,"Y":280},{"X":430,"Y":390},{"X":540,"Y":470},{"X":270,"Y":520},{"X":330,"Y":350},{"X":210,"Y":250}];

这是上面的input多边形作为图像:



以下是编号的点,您可以在其中轻松查看哪些点是重复的:



如您所见,上面的多边形可以通过多种方式进行划分,例如:
- 一个带有五个孔的外多边形
- 五个外多边形,其中一个有一个孔

输出,简单多边形作为 exPolygon 结构

简单多边形是没有自相交,没有重复坐标,无论它们是连续的还是非连续的,没有孔的多边形。输出的简单多边形可以具有 CW 或 CCW 缠绕顺序。 CW 表示外孔和 CCW 孔。

输出可能有(并且在很多时候会有)孔,但在某些情况下,输出没有孔。输出总是至少有一个外部多边形,但也可以有多个具有零个或多个孔的外部多边形。

输出应该是具有属性“outer”和“holes”的 exPolygon 对象数组。 “outer”是点对象的数组,“holes”是点对象的数组。如果填充了“孔”,则其中的孔必须是 exPolygon 对象中“外部”多边形的孔。

输出示例:

//这是一个输出示例,但点是随机的:

[ { "外": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{ "X":10,"Y":50}],
“洞”:[[{“X”:0,“Y”:8},{“X”:60,“Y”:13},{“X”:21,“Y”:2},{“X":3,"Y":1}],
[{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}]]},
{“外”:[{“X”:54,“Y”:4},{“X”:2,“Y”:50},{“X”:30,“Y”:5},{“X":10,"Y":50}],
“洞”:[[{“X”:0,“Y”:8},{“X”:60,“Y”:13},{“X”:21,“Y”:2},{“X":3,"Y":1}],
[{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}]]},
{“外”:[{“X”:54,“Y”:4},{“X”:2,“Y”:50},{“X”:30,“Y”:5},{“X":10,"Y":50}],
“洞”:[] }
];

输出的“外部”多边形是 CW,而“孔”是 CCW。

多边形中的点数、exPolygons 对象数和孔数没有限制。

以下是弱简单多边形的其他示例:



除法示例

这是输入多边形的示例:



以下是它的划分方式:



其他一些多边形可以有多种可能的输出选择,具体取决于伪重复点的位置。

我的问题

如何以这种方式划分多边形并实现所需的输出结构?我不是在问完整的代码(但如果你有一些空闲时间并想证明这是可能的)。也欢迎对可能的算法的想法。

我已经搜索了几个小时的解决方案并试图找到一个算法。

如果您想尝试解决方案,我这里有一个代码,我用来查找重复项:http://jsbin.com/unuyev/7/edit .它在 SVG 中显示多边形,并将点显示为红色圆圈和每个点的数组索引(按下按钮“使用 JS 运行”后)。

这是相同的,但有 12 个示例多边形(在 Javascript 窗口中更改 pindex 以更改多边形):
http://jsbin.com/unuyev/4/edit

编辑:Javascript Clipper 6现已推出,并支持 StrictlySimple .但是根据文档“目前不能保证多边形会严格简单,因为'简化'仍在进行中”。我已经测试过 StrictlySimple,但在某些情况下它会失败:Orientation problemslack of rotation invariance .我们希望这些问题很快得到解决和 StrictlySimple按预期工作。

最佳答案

可能我遗漏了一些东西,但这看起来像是找到图的关节顶点的经典问题。本质上,您试图找到图形中最薄弱的点,这样当您在该点切割图形时,最终会得到两个单独的图形。所以在你的例子中,如果你在那个顶点切割多边形,你最终会得到多个多边形。您可以很容易地将多边形表示为图形,每个顶点代表一个图形顶点,多边形边作为图形边。

如果我必须解决这个问题,这就是我会采取的方法。您可以查看以下资源:

  • Articulation vertices from the Algorithm Design Manual - 这是你最好的选择。他用简单的术语解释了算法,还为您提供了可以轻松转换为 JavaScript 的 C 代码。如果我必须开始编写算法,这就是我要开始的地方。
  • Biconnected component
  • Detection of Articulation Points (搜索“清晰度”)

  • 更新

    我将尝试为您简要概述问题和解决方案,以指明正确的方向。使用图形实现该算法必然会涉及图形算法术语,因此如果您不熟悉图形,则可能需要阅读它们。

    在您的情况下,蛮力方法是遍历图形,暂时删除每个 vetex,然后在修改后的图形上执行 DFS/BFS 遍历时查看图形是否连接。这不是很有效,将在二次时间运行 O(n(m + n)) .但是有一种线性时间算法基于对由 DFS 遍历形成的结果 DFS 树的边缘进行分类。

    在不包含任何后缘的 DFS 树中(将“较低”节点连接到树中“较高”节点的边[假设“较高”节点是那些更靠近根的节点])叶节点不是关节节点,因为删除它们中的任何一个仍然会使图形保持连接。但是,删除任何内部节点都会断开其后的所有节点与根节点的连接。

    删除树的根取决于它是否有一个或多个子节点。如果它只有一个 child ,那么它或多或少是一片叶子,因此删除它没有任何效果。但是,删除具有多个子节点的根节点会断开图的连接。

    但在一般图形中,您可以有后边,因此删除中间的任何节点都不会断开图形。因此,确定关节顶点归结为确定树的哪些部分通过后边缘链接到祖先节点(即,确定顶点的“可达祖先”)。

    在我从算法设计手册链接到的页面中,Skiena 描述了三个顶点可以是关节顶点(根、桥和父切割节点)的情况。使用他描述的算法,您可以确定您正在处理的顶点是否满足这些条件中的任何一个。如果是,则它是一个关节节点。

    希望这可以帮助您入门!

    关于javascript - 将弱简单多边形拆分为真正的简单多边形或多边形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16194648/

    有关javascript - 将弱简单多边形拆分为真正的简单多边形或多边形的更多相关文章

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

    2. ruby - 简单获取法拉第超时 - 2

      有没有办法在这个简单的get方法中添加超时选项?我正在使用法拉第3.3。Faraday.get(url)四处寻找,我只能先发起连接后应用超时选项,然后应用超时选项。或者有什么简单的方法?这就是我现在正在做的:conn=Faraday.newresponse=conn.getdo|req|req.urlurlreq.options.timeout=2#2secondsend 最佳答案 试试这个:conn=Faraday.newdo|conn|conn.options.timeout=20endresponse=conn.get(url

    3. ruby - 用 Ruby 编写一个简单的网络服务器 - 2

      我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不,不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本,提供另一个脚本,它将在其标准输入上获取请求,并在其标准输出上返回完整的响应。到目前为止一切顺利,但事实证明这真的很脆弱,因为它在第二个请求上中断并出现错误:/usr/b

    4. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章? - 2

      我意识到这可能是一个非常基本的问题,但我现在已经花了几天时间回过头来解决这个问题,但出于某种原因,Google就是没有帮助我。(我认为部分问题在于我是一个初学者,我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI,但我仍然停留在这个问题上.我找到了一些关于多态关系的信息,但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

    5. ruby - 使用 Ruby 通过 Outlook 发送消息的最简单方法是什么? - 2

      我的工作要求我为某些测试自动生成电子邮件。我一直在四处寻找,但未能找到可以快速实现的合理解决方案。它需要在outlook而不是其他邮件服务器中,因为我们有一些奇怪的身份验证规则,我们需要保存草稿而不是仅仅发送邮件的选项。显然win32ole可以做到这一点,但我找不到任何相当简单的例子。 最佳答案 假设存储了Outlook凭据并且您设置为自动登录到Outlook,WIN32OLE可以很好地完成此操作:require'win32ole'outlook=WIN32OLE.new('Outlook.Application')message=

    6. postman——集合——执行集合——测试脚本——pm对象简单示例02 - 2

      //1.验证返回状态码是否是200pm.test("Statuscodeis200",function(){pm.response.to.have.status(200);});//2.验证返回body内是否含有某个值pm.test("Bodymatchesstring",function(){pm.expect(pm.response.text()).to.include("string_you_want_to_search");});//3.验证某个返回值是否是100pm.test("Yourtestname",function(){varjsonData=pm.response.json

    7. Qt Designer的简单使用 - 2

      在前面两节的例子中,主界面窗口的尺寸和标签控件显示的矩形区域等,都是用C++代码编写的。窗口和控件的尺寸都是预估的,控件如果多起来,那就不好估计每个控件合适的位置和大小了。用C++代码编写图形界面的问题就是不直观,因此Qt项目开发了专门的可视化图形界面编辑器——QtDesigner(Qt设计师)。通过QtDesigner就可以很方便地创建图形界面文件*.ui,然后将ui文件应用到源代码里面,做到“所见即所得”,大大方便了图形界面的设计。本节就演示一下QtDesigner的简单使用,学习拖拽控件和设置控件属性,并将ui文件应用到Qt程序代码里。使用QtDesigner设计界面在开始菜单中找到「Q

    8. ruby - 是否有内置的 Ruby 1.8.7 将数组拆分为相同大小的子数组? - 2

      我已经开始了:defsplit_array(array,size)index=0results=[]ifsize>0whileindex如果我在[1,2,3,4,5,6]上运行它,比如split_array([1,2,3,4,5,6],3)它将产生这个数组:[[1,2,3],[4,5,6]]。在Ruby1.8.7中是否已经有可用的东西可以做到这一点? 最佳答案 [1,2,3,4,5,6].each_slice(3).to_a#=>[[1,2,3],[4,5,6]]对于1.8.6:require'enumerator'[1,2,3,4

    9. ruby - 使用 Ruby,计算 n x m 数组的每一列中有多少个 true 的简单方法是什么? - 2

      给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true?”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组,其中每个子数组代表一列,然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本,应该在1.8.6上运行,没有任何依赖:arr.transpose.map{|subarr|subarr.in

    10. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法? - 2

      我遇到了一个非常奇怪的问题,我很难解决。在我看来,我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时,我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性,其中包括href和data-method。再次单击此链接后,我的服务器收到了对新href的请求,但使用的是旧的data-method,即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是,如果我刷新页面,HTML与"new"HTML相同(随返回的JS发生变化),但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

    随机推荐