多边形三角剖分反射顶点 [英] polygon triangulation reflex vertex

问题描述

我正在尝试执行多边形三角剖分。我了解简单的Polygon（凹形或凸形）的剪耳方法。我被困在寻找一个顶点是否反射。我在多个地方读到的内容都是我无法理解的顺时针和逆时针方向。简而言之，这些方向指的是什么，请给我一些检查顶点是否反射的提示。

让我们选择a =（2 1），b =（5 4）和c =（3 6）。因此，如右图所示的取向由s ＝ b-a ＝（3 3）和t ＝ c-b ＝（-2 2）给出。现在 det（s t）给我们 s.x * t.y-t.x * s.y = 3 * 2-（-2）* 3 = 12> 0 。因此，如果我们站在点a并步行到b，则必须向左转达到c。

Hi i am trying to perform polygon triangulation. I understood the ear clipping method for a simple Polygon ( Concave or Convex ). i am stuck at finding whether a vertex is reflex or not . what i have read at multiple places is about clock-wise and counter clockwise orientations which i am unable to understand . in short what are those orientations referring to and please give me some hint on checking whether the vertex is reflex or not . here is the link of an article i am following:

and here is formula they have used:

  // Input
    VECTOR a, b, c; // the parts of our triangle.
    // if (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0
    // we are counter-clockwise

whats the point here i am unable to comprehend.

解决方案

Your input polygon is in most cases a list of consecutive vertices, they represent your polygon in counter clockwise order. That means when walking along the boundary of the polygon (if without holes) the interior of it should be to the left of every edge traversed. If one wants to know if a single vertex is convex or reflex (convex meaning internal angle smaller than 180°, reflex otherwise) then there are several methods. The most commonly used is to apply the determinate. The determinate gives us as result greater zero if the vertices form a left turn, which means that three consecutive vertices a,b, and c form a convex angle at b; and less than zero otherwise. Now the formula: (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y) > 0 does exactly that. It transforms the three vertices into two direction vectors: b-a and c-b then the determinate of this is already the given formula and tells us if a left or right turn occurs on b.

Edit, due to the question in the comment:

Let us choose a=(2 1), b=(5 4), and c=(3 6). Thus, the orientation as shown on the right picture is given by s=b-a=(3 3) and t=c-b=(-2 2). Now det(s t) gives us s.x*t.y - t.x*s.y = 3*2 - (-2)*3 = 12 > 0. Therefore, if we stand at point a and we walk to b, we have to take a left turn to get to c.

这篇关于多边形三角剖分反射顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！