Question

求用java编写，输入N个点的坐标，判断这N个点能否构成一个凸多边形。有问题可以一起讨论

Answer 1

递归寻找各个点最近的点，两点间距离可通过勾股定理求得。
两个最近的点连成一条直线，
然后判断各条直线的交点是否为输入的那些点。
如果交点均在输入的点处，则是凸多边形。
只要有任意两条线的交点不在输入的点处，就非凸多边形。但是要排除多点一线的情况。

求两条线交点可有参数方程求得。
如下
两点定一线，
线1，点1(x1,y1) 点2 (x2,y2)
线2，点3(x3,y3) 点4 (x4,y4)
t=[(y4-y3)(x3-x1)-(y3-y1)(x4-x3)] ÷ [(y4-y3)(x2-x1)-(y2-y1)(x4-x3)]
注意不要用整数计算，要用浮点数，否则会得不到准确的t值
交点处坐标为
x = x1+(x2-x1)t
y = y1+(y2-y1)t

简单点说，t=0或者1时，两线相交于给定点，任意其他值，均交与其他点。

原理就是这些了，自己写代码吧

Answer 2

算法是假设你沿着边走,如果是凸的就会一直向一个方向转弯,例如都向左拐,突然向右拐说明不是凸的
/*
* Variable polygon is a vector of points.
* Returns true if polygon is convex, otherwise false.
*/
public boolean checkConvexity()
{
if (polygon.size() < 3) return false;

Point p;
Point v;
Point u;
int res = 0;
for (int i = 0; i < polygon.size(); i++)
{
p = polygon.get(i);
Point tmp = polygon.get((i+1) % polygon.size());
v = new Point();
v.x = tmp.x - p.x;
v.y = tmp.y - p.y;
u = polygon.get((i+2) % polygon.size());

if (i == 0) // in first loop direction is unknown, so save it in res
res = u.x * v.y - u.y * v.x + v.x * p.y - v.y * p.x;
else
{
int newres = u.x * v.y - u.y * v.x + v.x * p.y - v.y * p.x;
if ( (newres > 0 && res < 0) || (newres < 0 && res > 0) )
return false;
}
}
return true;
}

追问

请问中间一段代码的数学意思是什么？怎么判断的额？

追答

知道给出两个坐标怎么求通过这两点的直线的方程吗y=ax+b
你把b的表达式用(x1,y1)和(x2,y2)表达出来,然后吧(x3,y3)带入方程得出b3-b1就是newres

追问

如果四个点在一条直线，这个算法好像不好判断。代码如何修改？

Answer 3

n>=5 且任意两点A B如果存在位于他们之间的点(x1<x<x2 y1<y<y2)与其他点都位于AB连线的同一侧 则一定不是凸多边形