algorithm - 有没有一种算法可以分离共享一条边的多边形？
问题描述
我有一个定义多边形的顶点列表，一个连接这些顶点并定义多边形轮廓的周边边缘列表，以及一个连接顶点的内边缘列表，有效地分割多边形。没有一条边彼此相交（它们只在起点和终点相遇）。
我想通过在内部边缘将更大的多边形分割成更小的组件。基本上我需要知道哪些顶点集是没有相交边的多边形的一部分。
基本上，这是我掌握的信息：
顶点 [0, 1, 3, 5, 7, 9, 11, 13, 15] 定义了我的多边形的外周长，蓝色边 (5, 13) 是将该周长分成两个多边形的内边。（忽略水平紫色线，它们是多边形梯形化找到边（5, 13）的结果。它们没有进一步的意义）
这就是我想要达到的目的：
一个多边形由顶点 [0, 1, 3, 5, 13, 15] 定义，另一个由 [5, 7, 9, 11, 13] 定义。
我需要一个适用于任意数量的分裂内边缘的解决方案。最后，我希望能够像下面这样划分多边形：
子多边形不一定是凸的。这对于任何依赖它的算法都可能很重要。例如，红色子多边形有一个凹顶点 (13)。
我最初的想法是沿顺时针或逆时针方向遍历每个子多边形的内部，跟踪我遇到的顶点及其顺序。但是，我无法找到起始边/顶点并保证下一个 cw 或 ccw 点实际上位于我要提取的那个子多边形的内部。
我试图用谷歌搜索解决方案，但这是一个我太陌生的数学领域，不知道要搜索什么。如何解决这个问题的想法/算法将不胜感激！（我不需要任何实际代码，只需解释如何执行此操作或伪代码就足够了）
现在，不幸的是我没有一些代码可以展示，因为我需要一个概念来首先尝试。我不知道如何解决这个问题，因此无法编写任何可以完成我需要它做的事情的代码。
编辑：
这只是我最终要做的事情的一步，即多边形三角剖分。我已经阅读了该问题的许多解决方案，并希望通过梯形化来实现它以获得单调多边形并最终对它们进行三角剖分。这基本上是梯形化的最后一步（或者我猜是下一步），在我能找到的任何关于该主题的资源中都没有解释过。
梯形化的最终结果是定义分割为（在我的情况下是垂直单调）多边形的内部边缘。我只需要“数据结构”沿着这些边缘分割多边形，这样我就可以单独处理子多边形。我希望这有助于澄清事情。
解决方案
您需要的算法的关键是知道如何对边进行排序：
找出哪个是（逆）顺时针方向的下一条边
您可以使用以下公式计算从节点i到节点j的边的绝对角度：
atan2(jy-iy, jx-ix)
边(i, j)和(j, k)之间的相对角度由下式给出：
atan2(ky-jy, kx-jx) - atan2(jy-iy, jx-ix)
此表达式可能会产生 [-, ] 范围之外的角度，因此您应该通过加或减 2 将结果映射回该范围。
因此，当您遍历了一条边(i, j)并需要选择下一条边(j, k)时，您可以选择相对角度最小的边。
算法
分区算法实际上并不需要预先知道哪些边是内部边，所以我假设你只有一个边列表。该算法可能如下所示：
- 创建一个邻接列表，这样您就有每个顶点的相邻顶点列表。
- 将每条边都添加到这个邻接列表中，因此实际上为每个原始边添加了两条有向边
- 从邻接列表中选择一条有向边(i, j)，并将其从那里删除。
- 定义一个新多边形并添加顶点i作为它的第一个顶点。
- 重复直到你回到正在构建的多边形中的第一个顶点：
- 将顶点j添加到多边形
- 在不是顶点i的顶点j的邻居中找到顶点k，并且使用上面给定的公式最小化相对角度。
- 将此角度加到总和上
- 从顶点j的邻居中删除这条有向边，因此它永远不会被再次访问
- 让i = j, j = k
- 如果角度总和为正（将为 2），则将多边形添加到“正”多边形列表中，否则（将为 -2）将其添加到替代列表中。
- 从第 2 步开始重复，直到邻接列表中不再有有向边。
- 最后，您将有两个多边形列表。一个列表将只有一个多边形。这将是原始的外部多边形，可以忽略。另一个列表将具有分区。
作为演示，这里是可运行的 JavaScript 片段中的一些代码。它使用您在问题中描绘的示例之一（但将连续顶点编号），根据此算法找到分区，并通过着色识别的多边形来显示结果：
function partition(nodes, edges) {
// Create an adjacency list
let adj = [];
for (let i = 0; i < nodes.length; i++) {
adj[i] = []; // initialise the list for each node as an empty one
}
for (let i = 0; i < edges.length; i++) {
let a = edges[i][0]; // Get the two nodes (a, b) that this edge connects
let b = edges[i][1];
adj[a].push(b); // Add as directed edge in both directions
adj[b].push(a);
}
// Traverse the graph to identify polygons, until none are to be found
let polygons = [[], []]; // two lists of polygons, one per "winding" (clockwise or ccw)
let more = true;
while (more) {
more = false;
for (let i = 0; i < nodes.length; i++) {
if (adj[i].length) { // we have unvisited directed edge(s) here
let start = i;
let polygon = [i]; // collect the vertices on a new polygon
let sumAngle = 0;
// Take one neighbor out of this node's neighbor list and follow a path
for (let j = adj[i].pop(), next; j !== start; i = j, j = next) {
polygon.push(j);
// Get coordinates of the current edge's end-points
let ix = nodes[i][0];
let iy = nodes[i][1];
let jx = nodes[j][0];
let jy = nodes[j][1];
let startAngle = Math.atan2(jy-iy, jx-ix);
// In the adjacency list of node j, find the next neighboring vertex in counterclockwise order
// relative to node i where we came from.
let minAngle = 10; // Larger than any normalised angle
for (let neighborIndex = 0; neighborIndex < adj[j].length; neighborIndex++) {
let k = adj[j][neighborIndex];
if (k === i) continue; // ignore the reverse of the edge we came from
let kx = nodes[k][0];
let ky = nodes[k][1];
let relAngle = Math.atan2(ky-jy, kx-jx) - startAngle; // The "magic"
// Normalise the relative angle to the range [-PI, +PI)
if (relAngle < -Math.PI) relAngle += 2*Math.PI;
if (relAngle >= Math.PI) relAngle -= 2*Math.PI;
if (relAngle < minAngle) { // this one comes earlier in counterclockwise order
minAngle = relAngle;
nextNeighborIndex = neighborIndex;
}
}
sumAngle += minAngle; // track the sum of all the angles in the polygon
next = adj[j][nextNeighborIndex];
// delete the chosen directed edge (so it cannot be visited again)
adj[j].splice(nextNeighborIndex, 1);
}
let winding = sumAngle > 0 ? 1 : 0; // sumAngle will be 2*PI or -2*PI. Clockwise or ccw.
polygons[winding].push(polygon);
more = true;
}
}
}
// return the largest list of polygons, so to exclude the whole polygon,
// which will be the only one with a winding that's different from all the others.
return polygons[0].length > polygons[1].length ? polygons[0] : polygons[1];
}
// Sample input:
let nodes = [[59,25],[26,27],[9,59],[3,99],[30,114],[77,116],[89,102],[102,136],[105,154],[146,157],[181,151],[201,125],[194,83],[155,72],[174,47],[182,24],[153,6],[117,2],[89,9],[97,45]];
let internalEdges = [[6, 13], [13, 19], [19, 6]];
// Join outer edges with inner edges to an overall list of edges:
let edges = nodes.map((a, i) => [i, (i+1)%nodes.length]).concat(internalEdges);
// Apply algorithm
let polygons = partition(nodes, edges);
// Report on results
document.querySelector("div").innerHTML =
"input polygon has these points, numbered 0..n<br>" +
JSON.stringify(nodes) + "<br>" +
"resulting polygons, by vertex numbers<br>" +
JSON.stringify(polygons)
// Graphics handling
let io = {
ctx: document.querySelector("canvas").getContext("2d"),
drawEdges(edges) {
for (let [a, b] of edges) {
this.ctx.moveTo(...a);
this.ctx.lineTo(...b);
this.ctx.stroke();
}
},
colorPolygon(polygon, color) {
this.ctx.beginPath();
this.ctx.moveTo(...polygon[0]);
for (let p of polygon.slice(1)) {
this.ctx.lineTo(...p);
}
this.ctx.closePath();
this.ctx.fillStyle = color;
this.ctx.fill();
}
};
// Display original graph
io.drawEdges(edges.map(([a,b]) => [nodes[a], nodes[b]]));
// Color the polygons that the algorithm identified
let colors = ["red", "blue", "silver", "purple", "green", "brown", "orange", "cyan"];
for (let polygon of polygons) {
io.colorPolygon(polygon.map(i => nodes[i]), colors.pop());
}<canvas width="400" height="180"></canvas>
<div></div>推荐阅读
- c# - 如何获取包含给定数据作为一部分的 SQL 数据
- c# - 该程序无法找到 MediatR 查询 ASP.Net Core 的处理程序
- c - 在c中水平翻转BMP图像
- c++ - C++ 工厂模式实现 - 示例、问题和关注点
- jsp - Tomcat：在上下文参数名称中使用双引号字符
- python - 如何建立一个神经网络，使其输出只有 0 或 1？
- uml - 这个UC图正确吗？
- javascript - 使用带有人员字段的 MS Graph API 将新项目发布到 SharePoint 列表
- c++ - 如何修复 C3861：“...”：找不到标识符
- machine-learning - tf-idf 中的文档和语料库是什么？