如何判断多边形的类型
How to determine the type of polygon
用户输入第n个点。我需要检查多边形是否存在,然后确定类型 - 凹多边形或凸多边形。我知道如果每个角都在 180 度以下,则多边形是凸的。所以问题归结为找到多边形的每个内角。我一直在寻找公式或算法,但没有成功。
示例:
输入:n=4;
点 1:(5;6)
点 2: (4;-5)
点 3:(-5;4)
Point4: (-5;5)
预期输出:多边形是凸的
这是目前为止的代码:现在它只找到平面中各点之间的最大和最小距离。
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
double a[15][2];
int n;
cin >> n;
if (n <= 0 && n > 15)
return 1;
for (int i = 0; i < n; i++)
{
cout << "x" << i << " = , y" << i << " = ";
cin >> a[i][0] >> a[i][1];
}
double maxDistance = 0.0;
double minDistance = 0.0;
double maxpoint1[2];
double maxpoint2[2];
double minpoint1[2];
double minpoint2[2];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (j != i)
{
double x1 = a[i][0];
double x2 = a[j][0];
double y1 = a[i][1];
double y2 = a[j][1];
double currentDistance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
if (currentDistance > maxDistance)
{
maxDistance = currentDistance;
maxpoint1[0] = x1;
maxpoint1[1] = y1;
maxpoint2[0] = x2;
maxpoint2[1] = y2;
}
if (minDistance > currentDistance)
{
currentDistance = minDistance;
minpoint1[0] = x1;
minpoint1[1] = y1;
minpoint2[0] = x2;
minpoint2[1] = y2;
}
cout << "x1 = " << x1 << " y1 = " << y1 << " x2 = " << x2 << " y2 = " << y2;
cout << endl << "Distance is " << currentDistance;
cout << endl;
}
}
}
cout << "The max distance is: " << maxDistance << " between x1 = " << maxpoint1[0] << " y1 = " << maxpoint1[1] << " and x2 = " << maxpoint2[0] << " y2 = " << maxpoint2[1];
cout << "The min distance is: " << minDistance << " between x1 = " << minpoint1[0] << " y1 = " << minpoint1[1] << " and x2 = " << minpoint2[0] << " y2 = " << minpoint2[1];
return 0;
}
如果你想求两条边的夹角,用向量的叉积或点积。
a 点 b = |a||b| cos(angle_between_vectors) = a[0]*b[0] + a[1]*b[1] + a[2]*b[2]
内角为 (pi - angle_between_vectors)
哦,顺便说一句,多边形可能会自相交,这在许多用例中也是有害的问题。您的定义将无法检测到......例如复杂四边形的所有角度都小于 90 度。
这不是确定多边形是否为凸面的唯一方法,而且可能是计算最丰富的方法之一?
点积的问题在于,如果角度小于或大于 pi/2,它的符号就会显示。确定多边形是否复杂或非凸的正确方法是检查转弯方向是否改变。为此,您需要叉积。对于二维向量,它们的叉积结果只有 z 分量(垂直于平面),它的符号决定旋转发生的方向。
问题已经在这里了。
How do determine if a polygon is complex/convex/nonconvex?
要确定多边形是凸面还是凹面,只需检查所有连续点三元组的叉积符号 CrossProduct(P[0], P[1], P[2]) etc
。例如
CrossProductSign(A, B, C) =
SignOf((B.X - A.X) * (C.Y - B.Y) - (B.Y - A.Y) * (C.X - B.X))
对于凸一,所有叉积必须具有相同的符号(+ 或 -)。
工作原理:对于凸多边形,每个三元组在同一侧转弯(或顺时针或逆时针,具体取决于行走方向)。对于凹形,一些标志会有所不同(内角超过 180 度)。请注意,您不需要计算角度值。
用户输入第n个点。我需要检查多边形是否存在,然后确定类型 - 凹多边形或凸多边形。我知道如果每个角都在 180 度以下,则多边形是凸的。所以问题归结为找到多边形的每个内角。我一直在寻找公式或算法,但没有成功。
示例:
输入:n=4;
点 1:(5;6)
点 2: (4;-5)
点 3:(-5;4)
Point4: (-5;5)
预期输出:多边形是凸的
这是目前为止的代码:现在它只找到平面中各点之间的最大和最小距离。
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
double a[15][2];
int n;
cin >> n;
if (n <= 0 && n > 15)
return 1;
for (int i = 0; i < n; i++)
{
cout << "x" << i << " = , y" << i << " = ";
cin >> a[i][0] >> a[i][1];
}
double maxDistance = 0.0;
double minDistance = 0.0;
double maxpoint1[2];
double maxpoint2[2];
double minpoint1[2];
double minpoint2[2];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (j != i)
{
double x1 = a[i][0];
double x2 = a[j][0];
double y1 = a[i][1];
double y2 = a[j][1];
double currentDistance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
if (currentDistance > maxDistance)
{
maxDistance = currentDistance;
maxpoint1[0] = x1;
maxpoint1[1] = y1;
maxpoint2[0] = x2;
maxpoint2[1] = y2;
}
if (minDistance > currentDistance)
{
currentDistance = minDistance;
minpoint1[0] = x1;
minpoint1[1] = y1;
minpoint2[0] = x2;
minpoint2[1] = y2;
}
cout << "x1 = " << x1 << " y1 = " << y1 << " x2 = " << x2 << " y2 = " << y2;
cout << endl << "Distance is " << currentDistance;
cout << endl;
}
}
}
cout << "The max distance is: " << maxDistance << " between x1 = " << maxpoint1[0] << " y1 = " << maxpoint1[1] << " and x2 = " << maxpoint2[0] << " y2 = " << maxpoint2[1];
cout << "The min distance is: " << minDistance << " between x1 = " << minpoint1[0] << " y1 = " << minpoint1[1] << " and x2 = " << minpoint2[0] << " y2 = " << minpoint2[1];
return 0;
}
如果你想求两条边的夹角,用向量的叉积或点积。
a 点 b = |a||b| cos(angle_between_vectors) = a[0]*b[0] + a[1]*b[1] + a[2]*b[2]
内角为 (pi - angle_between_vectors)
哦,顺便说一句,多边形可能会自相交,这在许多用例中也是有害的问题。您的定义将无法检测到......例如复杂四边形的所有角度都小于 90 度。
这不是确定多边形是否为凸面的唯一方法,而且可能是计算最丰富的方法之一? 点积的问题在于,如果角度小于或大于 pi/2,它的符号就会显示。确定多边形是否复杂或非凸的正确方法是检查转弯方向是否改变。为此,您需要叉积。对于二维向量,它们的叉积结果只有 z 分量(垂直于平面),它的符号决定旋转发生的方向。
问题已经在这里了。
How do determine if a polygon is complex/convex/nonconvex?
要确定多边形是凸面还是凹面,只需检查所有连续点三元组的叉积符号 CrossProduct(P[0], P[1], P[2]) etc
。例如
CrossProductSign(A, B, C) =
SignOf((B.X - A.X) * (C.Y - B.Y) - (B.Y - A.Y) * (C.X - B.X))
对于凸一,所有叉积必须具有相同的符号(+ 或 -)。
工作原理:对于凸多边形,每个三元组在同一侧转弯(或顺时针或逆时针,具体取决于行走方向)。对于凹形,一些标志会有所不同(内角超过 180 度)。请注意,您不需要计算角度值。