java判断凸四边形代码,怎么判断凸四边形

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

递归寻找各个点最近的点，两点间距离可通过勾股定理求得。

两个最近的点连成一条直线，

然后判断各条直线的交点是否为输入的那些点。

如果交点均在输入的点处，则是凸多边形。

只要有任意两条线的交点不在输入的点处，就非凸多边形。但是要排除多点一线的情况。

求两条线交点可有参数方程求得。

如下

两点定一线，

线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时，两线相交于给定点，任意其他值，均交与其他点。

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

相关问答

Q1: C语言编程题 题目：任意输入4个点，求围成四边形的面积是多少？

我测试过了，四点一线，凹四边形，四边形，有两个点共点，都可以，这里使用一条知道N边形N个顶点坐标求N边形的面积的公式，这些情况其实已经可以不考虑，呵呵，自动求

凹四边形情况：

有三点共一线形成三角形的情况：

#include "stdio.h"

#include "math.h"

void main()

{

double x[4],y[4];

for(int i=0;i4;i++)

{

scanf("%lf%lf",x[i],y[i]);

}

double mianji=0.0;

for(int ii = 1 ; ii 4 ; ii++)

{

mianji+=(x[ii-1]*y[ii]-x[ii]*y[ii-1]);

}

mianji+=x[3]*y[0]-x[0]*y[3];

mianji= fabs(0.5*mianji);

printf("%lf\n",mianji);

}

Q2: 求用c语言写一个判断凹凸四边形的代码。

你可以参考下面的方法：

.判断一个封闭图形是凹集还是凸集

语法：result=convex(Point *p,int n);

参数：

*p： 封闭曲线顶点数组

n： 封闭曲线顶点个数

返回值： 1：凸集；-1：凹集；0：曲线不符合要求无法计算

注意：

默认曲线为简单曲线：无交叉、无圈

源程序：

typedef struct {

double x,y;

} Point;

int convex(Point *p,int n)

{

int i,j,k;

int flag = 0;

double z;

if (n 3)

return(0);

for (i=0;in;i++) {

j = (i + 1) % n;

k = (i + 2) % n;

z = (p[j].x - p[i].x) * (p[k].y - p[j].y);

z -= (p[j].y - p[i].y) * (p[k].x - p[j].x);

if (z 0)

flag |= 1;

else if (z 0)

flag |= 2;

if (flag == 3)

return －1; //CONCAVE

}

if (flag != 0)

return 1; //CONVEX

else

return 0;

}