是否有一种算法可以分离共享一条边的多边形？
Is there an algorithm to separate polygons that share an edge?
我有一个定义多边形的顶点列表，一个连接这些顶点并定义多边形轮廓的周界边列表，以及一个连接顶点的内边列表，有效地分割多边形。 None 条边相交（它们只在起点和终点相交）。
我想通过在内部边缘将较大的多边形分割成较小的部分。基本上我需要知道哪些顶点集是没有相交边的多边形的一部分。
基本上，这是我掌握的信息：
顶点 [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)。
我最初的想法是以顺时针或逆时针方向遍历每个子多边形的内部，跟踪我遇到的顶点及其顺序。但是，我无法找到起始 edge/vertex 并保证下一个 cw 或 ccw 点实际上位于我要提取的子多边形的内部。
我试图 google 寻找解决方案，但这是一个我太不熟悉的数学领域，不知道要搜索什么。 idea/algorithm 如何解决这个问题将不胜感激！
（我不需要任何实际代码，只需解释如何执行此操作或伪代码就足够了）
现在，不幸的是我没有一些代码可以展示，因为我需要先尝试一个概念。我不知道如何解决这个问题，因此无法编写任何可以完成我需要它做的事情的代码。
编辑：
这只是我最终要做的事情的第一步，即多边形三角剖分。我已经阅读了该问题的许多解决方案，并希望通过梯形化来实现它以获得单调多边形并最终对这些多边形进行三角剖分。这基本上是梯形化的最后一步（或者我猜是之后的下一步），在我能找到的关于该主题的任何资源中都没有解释过。
梯形化的最终结果是定义分割成（在我的例子中垂直单调）多边形的内边缘。我只需要沿着这些边 "datastructurally" 拆分多边形，这样我就可以单独处理子多边形了。我希望这有助于澄清事情。
您需要的算法的关键是知道如何对边进行排序：
按（逆）时针顺序找出下一个边
可以计算出节点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添加到多边形
- 在顶点j的邻居中找到不是顶点i的顶点k,并最小化上述给定公式的相对角度。
- 将这个角度加到总和
- 从顶点j的邻居中删除这条有向边，这样它就再也不会被访问了
- 让i = j, j = k
- 如果角度之和为正（将为 2），则将多边形添加到 "positive" 多边形列表中，否则（将为 -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>
我有一个定义多边形的顶点列表，一个连接这些顶点并定义多边形轮廓的周界边列表，以及一个连接顶点的内边列表，有效地分割多边形。 None 条边相交（它们只在起点和终点相交）。
我想通过在内部边缘将较大的多边形分割成较小的部分。基本上我需要知道哪些顶点集是没有相交边的多边形的一部分。
基本上，这是我掌握的信息：
顶点 [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)。
我最初的想法是以顺时针或逆时针方向遍历每个子多边形的内部，跟踪我遇到的顶点及其顺序。但是，我无法找到起始 edge/vertex 并保证下一个 cw 或 ccw 点实际上位于我要提取的子多边形的内部。
我试图 google 寻找解决方案，但这是一个我太不熟悉的数学领域，不知道要搜索什么。 idea/algorithm 如何解决这个问题将不胜感激！ （我不需要任何实际代码，只需解释如何执行此操作或伪代码就足够了）
现在，不幸的是我没有一些代码可以展示，因为我需要先尝试一个概念。我不知道如何解决这个问题，因此无法编写任何可以完成我需要它做的事情的代码。
编辑：
这只是我最终要做的事情的第一步，即多边形三角剖分。我已经阅读了该问题的许多解决方案，并希望通过梯形化来实现它以获得单调多边形并最终对这些多边形进行三角剖分。这基本上是梯形化的最后一步（或者我猜是之后的下一步），在我能找到的关于该主题的任何资源中都没有解释过。
梯形化的最终结果是定义分割成（在我的例子中垂直单调）多边形的内边缘。我只需要沿着这些边 "datastructurally" 拆分多边形，这样我就可以单独处理子多边形了。我希望这有助于澄清事情。
您需要的算法的关键是知道如何对边进行排序：
按（逆）时针顺序找出下一个边
可以计算出节点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添加到多边形
- 在顶点j的邻居中找到不是顶点i的顶点k,并最小化上述给定公式的相对角度。
- 将这个角度加到总和
- 从顶点j的邻居中删除这条有向边，这样它就再也不会被访问了
- 让i = j, j = k
- 如果角度之和为正（将为 2），则将多边形添加到 "positive" 多边形列表中，否则（将为 -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>