三角剖分x单调多边形

Question

我很难弄清楚如何三角剖分x单调多边形。我参考this article。我不明白如何检查顶点是否是耳朵，以及是否有对角线。

Answer 1

您可以参考ear cutting这是一个n^2时间算法。有很多简单的算法来对一个简单的多边形进行三角剖分。最简单的n log n时间算法之一包括首先将简单多边形分解为单调片段，然后对这些片段进行三角测量。这种情况下的分裂需要n log n。就你而言，因为你已经有单调片段，所以你可以在线性时间内很容易地对x单调多边形进行三角测量。

对这个简单算法的一个很好的解释例如在书Computational Geometry中给出。

粗略的想法是：你知道你的多边形是x-单调的。因此，你将它分成两个单调链（上和下）。现在，您可以沿着两条链走，并在两条链之间插入对角线，而无需查看可见性。只要下一个较低链的顶点具有较小的x值，就沿着上层链走。如果您的顶点是反射，则将其放在堆栈上，否则将对角线插入另一边。当您在另一条链上进行下一步时，首先将对角线插入堆栈中的每个顶点，然后继续执行此例程。

Answer 2

请参阅第13/25页“三角测量：理论”。该图说明了一个测试，看看p是否是耳朵上的顶点。它的邻居是q和r。如果线段qr是对角线，则p在耳朵上。

通过测试是否有其他顶点位于其上或其他任何边缘线段是否跨越线段，测试线段以查看其是否为对角线。