查找多个多边形的共同轮廓 [英] Finding common outline of multiple polygons

问题描述

我正在尝试找到一种在多个多边形之间绘制公共轮廓的算法. 我的意思是像这张照片:

Im trying to find an algorithm for drawing a common outline between multiple polygons. What I mean is like on this picture:

我们有两个矩形(在我的情况下，它们将不是矩形，而是大多数角度为直角的多边形)，Im在图像的第二部分上寻找一条像红色路径一样的公共轮廓.我看到的最大问题是找到新点，我在图像的第二部分上将其标记为黄色. 多边形永远不会相交或接触自身.我按逆时针顺序将多边形存储为点.

We have two rectangles (In my case they will not be rectangles, but polygons with most of their angles as right angle) and Im looking for common outline like a red path on second part of image. The biggest problem as I see it is finding new points which I marked yellow on the second part of image. The polygons will never intersect or touch itselfs. Im storing a polygon as points in counter-clockwise order.

我正在寻找一些应该在Google上搜索的线索，资源或关键词，这可能会使我的任务变得更简单...

Im looking for some clues, sources or even keywords on which I should google, which could make my task little easier...

有点像凸包，但是看边缘而不是顶点，黄点可能在我看边缘的连续性上.

its kind like in convex hull but looking at the edges not at the vertices, yellow point are probably on the continuaion of the edges as I look at it.

好的，我需要在多边形周围绘制给定大小的边界，但是这样，如果两个多边形比边界大小更近，它们将具有公共边界，这是两个边界之和，而不是'inner的一部分，这两个多边形将被视为一个形状.因此，我试图找到将用于在其周围绘制边框的红色多边形.

Ok, I need to draw a border of given size around polygons, but in such way that if two polygons are closer than the border size they will have common border which is kind of a sum of two borders without 'inner' part of it and this two polygons will be treated as a one shape. So Im trying to find this red polygon which will be used to draw this border around it.

推荐答案

首先，通过将所有边与延伸到无穷大的所有其他边剪裁，将额外的顶点添加到多边形(您的黄色边)中(例如，将边变成无限线)

Start by adding extra vertices to your polygons (your yellow ones) by clipping all edges against all other edges extended to infinity (e.g. turn your edges into infinite lines).

将新顶点连接到延伸的边缘.这将为您提供一个多边形网格.

Connect the new vertices to the extended edges. This will give you a polygonal mesh.

现在就来了:

开始条件:

• 选择最左上角的顶点，只能有一个！

• Pick the most top-left vertex, there can be only one!

选择具有最小斜率的边缘，该边缘连接到以1找到的顶点并向右延伸.该边缘将始终位于最终多边形的周长上.

Pick the edge with the least slope that connects to the vertex found by 1 and extends to the right. This edge will always be on the perimeter of your final polygon.

迭代:

• 从当前边缘开始，沿顺时针方向沿着其他边缘走动. 这样做会遇到新的顶点，这些顶点可能会连接到其他多个边.始终选择最逆时针的位置并继续.这将始终使您处于最终多边形的边界.

• From your current edge, walk along the other edges in clockwise order. You will encounter new vertices as you do this, and these vertices may connect to multiple other edges. Always pick the most counter-clockwise one and continue. This will always keep you on the perimeter of your final polygon.

结束条件:

• 再次到达左上角顶点时就停止.

恭喜，您刚刚走到多边形的外边缘.

Congratulations, you just walked around the outer edge of your polygon.

这篇关于查找多个多边形的共同轮廓的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！