我正在尝试在C++中实现 Graham Scan,但无法正常工作,也找不到原因。如果有任何线索,将不胜感激。经过几次尝试,似乎我总是有
使用叉积来确定是右转还是左转。
点积除以范数得到
将点保存到
m_M = 2
,而这两个点是最高的y点,如果这有帮助的话。使用叉积来确定是右转还是左转。
qreal Interpolation::ccw(QPointF pt1, QPointF pt2, QPointF pt3)
{
return (pt2.x()-pt1.x())*(pt3.y()-pt1.y()) - (pt2.y()-pt1.y())*(pt3.x()-pt1.x());
}
点积除以范数得到
cos
,因为按角度排序与在[0, Pi]
中排序cos
是相同的。qreal Interpolation::dp(QPointF pt1, QPointF pt2)
{
return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y()));
}
主要功能:
void Interpolation::ConvexHull()
{
QPointF points[m_N+1]; // My number of points
QPointF pt_temp(m_pt[0]);
qreal angle_temp(0);
int k_temp(0);
请填充数组points,使得points[1]
为较低的y点:
for (int i(1); i < m_N; ++i)
{
if (m_pt[i].y() < pt_temp.y())
{
points[i+1] = pt_temp;
pt_temp = m_pt[i];
}
else
{
points[i+1] = m_pt[i];
}
}
points[1] = pt_temp;
将点数组按照角度排序,并执行points[m_N] = points[0]
for (int i(2); i <= m_N; ++i)
{
pt_temp = points[i];
angle_temp = dp(points[1], pt_temp);
k_temp = i;
for (int j(1); j <= m_N-i; ++j)
{
if (dp(points[1], points[i+j]) < angle_temp)
{
pt_temp = points[i+j];
angle_temp = dp(points[1], points[i+j]);
k_temp = i+j;
}
}
points[k_temp] = points[i];
points[i] = pt_temp;
}
points[0] = points[m_N];
执行 Graham 扫描
m_M = 1; // Number of points on the convex hull.
for (int i(2); i <= m_N; ++i)
{
while (ccw(points[m_M-1], points[m_M], points[i]) <= 0)
{
if (m_M > 1)
{
m_M -= 1;
}
else if (i == m_N)
{
break;
}
else
{
i += 1;
}
}
m_M += 1;
pt_temp = points[m_M];
points[m_M] = points[i];
points[i] = points[m_M];
}
将点保存到
m_convexHull
中,它应该是凸包上的点列表,其中ConvexHull[m_M]=[ConvexHull[0]
。 for (int i(0); i < m_M; ++i)
{
m_convexHull.push_back(points[i+1]);
}
m_convexHull.push_back(points[1]);
}