我有一个定义多边形的顶点列表，一个连接这些顶点并定义多边形轮廓的周边边列表，以及一个连接顶点的内边列表，有效地分割多边形。没有一条边相互相交(它们只在起点和终点相交)。
我想通过在内部边缘将较大的多边形分割成较小的部分。基本上我需要知道哪些顶点集是没有相交边的多边形的一部分。
基本上，这是我掌握的信息:
顶点 [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)
参见 atan2
边 (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>关于algorithm - 是否有一种算法可以分离共享一条边的多边形？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57827915/