algorithm - 如何确定标签偏移量以使标签始终位于多边形的外部？

Question

我有一些多边形的顶点，上面有标签。我想放置标签，使它们始终位于多边形的外部。所以在上图中，除了#3 和#4 之外，所有标签都很好，我希望它们位于多边形外部的底部。所以一般来说，对于一个特定的顶点，我如何确定如何偏移它以使其位于多边形之外？

标签： algorithmmathgeometrycomputational-geometry

Answer 1

由于您没有显示任何自己的代码，我将仅陈述一些想法。如果您想要包括代码在内的更多详细信息，请展示您自己的更多努力然后询问。

我在这里假设多边形是一个简单的多边形——一个不与自身相交的多边形。如果一个多边形确实与自身相交，那么它的“内部”的定义就不是那么简单了，并且内部有多个定义。我不会假设多边形是凸的——所有的内角都小于 180°。（这将允许一个更简单的答案。）我还假设您希望标签的中心位于多边形之外，但允许标签的角落或一小部分位于内部。

首先，遍历多边形并找到它的“缠绕角”，即在遍历过程中方向角的变化量。如果多边形很简单，则角度将为 +180° 或 -180°。其中之一意味着您顺时针遍历多边形，另一个意味着逆时针。（这取决于您的坐标系：笛卡尔或图形或其他。）

然后再次遍历多边形。现在您知道多边形的方向，在每个顶点处，您可以找到外角从进入线段顺时针还是逆时针。找到那个方向和角度的大小，然后在那个方向移动那个角度的一半。沿该角度从顶点移动给定距离，您将获得标签中心的位置。

这应该适用于绝大多数多边形。在非凸多边形的某些边缘情况下，该位置从多边形移到多边形的另一部分。然后，您减少标签与其顶点的距离，直到标签移回多边形的外部。

我回答了一个相关问题： 如何有效地确定多边形是凸面、非凸面还是复面？.