输入N个点的坐标,判断这N个点能否构成一个凸多边形.这是我们实验周的课题之一…求好人…求高手…求问题

输入N个点的坐标,判断这N个点能否构成一个凸多边形.这是我们实验周的课题之一…求好人…求高手…求问题

首先要弄清这N个点是否是连续（顺序）的,即1连2,2连3,3连4..N连1如果这N点是随机（任意次序）的,目前我没想出很好的办法,也许对某点可以将相邻最近的两点与其连起来?如果这N个点是连续（顺序）的,那么对于凸多边形,某顶点临近的两顶点的连线必然在多边形内部,反之则不是凸多边形.比如点1连2,2连3,则1、3连线必在多边形内部,也即抹去12连线和23连线,连接13,2必在新多边形外.如何判断某点在一个多边形外或内?通过这一点的一条直线如果穿过多边形,那么与多边形边界的两个交点在这点的两边的,这点在多边形内,在同一边的,这点在多边形外.如何找通过某点的直线,此直线穿过多边形?可以试此点与多边形各定点的连线,这些连线应该有穿过多边形的.定下算法后,接下去就是高中解析几何的问题了.（一堆直线方程的计算）写了这么多,希望楼主认真看看,欢迎跟我讨论

收益了