判断凸多边形并排序算法

在平面直角坐标系中，给定一个点序列，判断这些点是否能够构成凸多边形，

并且按照顺时针方向输出这些点。

其他要求：
1.输出的起始的为距离原点最近的点，如果多点距离原点相等，取其中任一点即可；
2.如果有3个或者以上点在一条直线上，输出"ERROR";

输入输出格式要求：
1.输入为用逗号分隔的10进制整形数字序列的字符串形式，两两组成一个坐标点，如：
"0,0,1,0,1,1"，代表输入了P(0,0),P(1,0),P(1,1)三个点；

2.输出形式同输入一致；

 

解析：

一、构造顺时针多边形顺序算法：

1.先找一个距离原点最近的点A，然后随便选一个点B，组成直线集合，可以理解成向量L(A,B)，即A->B；

2.再依次遍历剩下的点，向直线集合中插入；

2.1.依次遍历直线集合；

2.2.当点X在直线(L1,由L1(startPoint,endPoint)左边时，记录L1位置i，并从直线集合中移除，同时在i,i+1位置依次插入L2(L1.startPoint,X),L3(X,L1.endPoint)，执行2；

2.3.当点X在所有直线的右侧时，添加队尾直线的end节点到X的直线，执行2；

3.全部点遍历完毕并插入后，添加队尾直线的end节点到A点的直线；

4.直线集合中的起点顺序即为所有点的顺时针顺序；

 

二、判断是否是凸多边形算法

1.在获取到顺时针的直线集合后，依次遍历直线，如果剩下的点在直线两侧，则说明是非凸多边形，否则是凸多边形；

 

三、判断点是否在线上，还是在左边，需要根据斜率来计算，计算斜率时，又要注意有些特殊的直线的斜率是不能直接计算的(除数为0的特殊情况)

 

四、源码解析

1、定义一个点对象，包含x,y坐标，距离原点的距离

 

/*
 * 

* 文 件 名: Point.java * 描 述: <描述> * 修改时间: 2016-4-17 * 

*/ package com.justinsoft.polygon.model; /** * 点 */ public class Point implements Comparable { private final int x; private final int y; /** * 距离(原点)的平方 */ private final Integer distance; public Point(int x, int y) { this.x = x; this.y = y; this.distance = calcDistance(x, y); } /** * 获取 x * * @return 返回 x */ public int getX() { return x; } /** * 获取 y * * @return 返回 y */ public int getY() { return y; } /** * 重载方法 * * @return */ @Override public String toString() { return "Point [x=" + x + ", y=" + y + "]"; } /** * 重载方法 * * @param o * @return */ @Override public int compareTo(Point o) { return getDistance().compareTo(o.getDistance()); } /** * 计算距离(距离原点的) * *

     * @param x
     * @param y
     * @return
     * 

*/ private static int calcDistance(int x, int y) { return x * x + y * y; } /** * 获取 distance * * @return 返回 distance */ private Integer getDistance() { return distance; } }

 

 

2、定义直线对象（向量），包含起点、终点、斜率

 

/*
 * 

* 文 件 名: Line.java * 描 述: <描述> * 修改时间: 2016-4-17 * 

*/ package com.justinsoft.polygon.model; /** *

 * 线
 * 

*/ public class Line { /** * 起点 */ private final Point start; /** * 终点 */ private final Point end; /** * 斜率 */ private final float slopeRate; /** * <默认构造函数> */ public Line(Point start, Point end) { this.start = start; this.end = end; this.slopeRate = calcSlopeRate(start, end); } /** * 点是否在直线上 * * @param point * @return */ public boolean containsPoint(Point point) { // 1.计算斜率 float slopeRate = calcSlopeRate(point, getStart()); // 2.如果斜率为0，需要判断是否是特殊情况 if (slopeRate == 0) { // 如果是分母相等，说明x坐标相等，则只有当当前点与另一个点的x坐标也相等时才在一条直线上 float delatX = point.getX() - getStart().getX(); if (0 == delatX) { return point.getX() == getEnd().getX(); } else { return point.getY() == getEnd().getY(); } } return slopeRate == getSlopeRate(); } /** * 点是否在直线的左边(按照线的起点到终点的方向来看点是左边还是右边)
*
* 取点的y坐标时，比较线上的x坐标与点的x坐标大小
* k= (y-y1)/(x-x1) x =(y-y1)/k+x1 * *

     * @param point
     * @return
     * 

*/ public boolean hasLeftPoint(Point point) { // 1.判断斜率的特殊情况 if (0 == getSlopeRate()) { // 1.1如果线是与x轴垂直的直线，则判断点的x坐标是否更小 if (getEnd().getX() == getStart().getX()) { return point.getX() < getStart().getX(); } } // 2.计算线上的点的x坐标 float xInLine = (point.getY() - getStart().getY()) / getSlopeRate() + getStart().getX(); return point.getX() < xInLine; } /** * 计算斜率 * *

     * @param p1
     * @param p2
     * @return
     * 

*/ private static float calcSlopeRate(Point p1, Point p2) { float delatY = p2.getY() - p1.getY(); float delatX = p2.getX() - p1.getX(); if (0 == delatX) { return 0; } return delatY / delatX; } /** * 获取 start * * @return 返回 start */ public Point getStart() { return start; } /** * 获取 end * * @return 返回 end */ public Point getEnd() { return end; } /** * 获取 slopeRate * * @return 返回 slopeRate */ private float getSlopeRate() { return slopeRate; } /** * 重载方法 * * @return */ @Override public String toString() { return "Line [start=" + start + ", end=" + end + ", slopeRate=" + slopeRate + "]"; } } 3、算法实现类

 

 

package com.justinsoft.polygon;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import com.justinsoft.polygon.model.Line;
import com.justinsoft.polygon.model.Point;

/**
 * 在平面直角坐标系中，给定一个点序列，判断这些点是否能够构成凸多边形，

 * 并且按照顺时针方向输出这些点。

 * 

 * 其他要求：

 * 1.输出的起始的为距离原点最近的点，如果多点距离原点相等，取其中任一点即可；

 * 2.如果有3个或者以上点在一条直线上，输出"ERROR";

 * 

 * 输入输出格式要求：

 * 1.输入为用逗号分隔的10进制整形数字序列的字符串形式，两两组成一个坐标点，如：

 * "0,0,1,0,1,1"，代表输入了P(0,0),P(1,0),P(1,1)三个点；

 * 2.输出形式同输入一致；

 * 

 * 

 */
public class PolygonSort
{
    /**
     * 多边形最少点数
     */
    private static final int MIN_POINT_SIZE = 3;
    
    /**
     * 点里面的元素
     */
    private static final int NUM_IN_POINT = 2;
    
    /**
     * 分隔符
     */
    private static final String SPLIT = ",";
    
    /**
     * 错误信息
     */
    private static final String ERROR = "ERROR";
    
    public static String findConvexPolygon(String input)
    {
        try
        {
            // 1.获取所有的点
            List allPoint = getAllPoint(input);
            
            // 总的点数
            int size = allPoint.size();
            
            // 2.判断是否有一点在其他两点所在的直线上
            boolean hasPointInLine = hasPointInLine(allPoint);
            if (hasPointInLine)
            {
                return ERROR;
            }
            
            // 3.取距离原点最近的一个点(之一)
            Point minPoint = getFirstPoint(allPoint);
            allPoint.remove(minPoint);
            
            // 4.再从队列中任意移除一个点
            Point point = allPoint.remove(0);
            
            // 5.组成任意一条直线(从距离原点最小的点开始)
            Line line = new Line(minPoint, point);
            
            List allLine = new ArrayList(size);
            allLine.add(line);
            
            // 6.向已经存在的线中加入点，重新按照顺时针连线(根据点在线的位置来进行判断)
            for (Point leftPoint : allPoint)
            {
                addPointToLine(allLine, leftPoint);
            }
            
            int lastIndex = allLine.size() - 1;
            Line lastLine = allLine.get(lastIndex);
            
            // 7.线还没有闭环，缺少从最后一个点到起点的直线
            Line tailLine = new Line(lastLine.getEnd(), minPoint);
            allLine.add(tailLine);
            
            // 8.判断多边形是否是凸多边形
            boolean isConvexPolygon = isConvexPolygon(allLine);
            if (!isConvexPolygon)
            {
                return ERROR;
            }
            
            // 8.拼装输出结果
            String seqOrder = getSeqOrder(allLine);
            
            return seqOrder;
        }
        catch (Exception e)
        {
            return ERROR;
        }
    }
    
    /**
     *
     * 拼装输出结果
     * 
     * @param allLine
     * @return
     * 
*/ private static String getSeqOrder(List allLine) { StringBuilder order = new StringBuilder(); for (Line line : allLine) { order.append(line.getStart().getX()); order.append(SPLIT); order.append(line.getStart().getY()); order.append(SPLIT); } if (order.toString().endsWith(SPLIT)) { order.deleteCharAt(order.length() - 1); } return order.toString(); } /** *
     * 判断是否是凸多边形
     * 
     * @param allLine
     * @return
     * 
*/ private static boolean isConvexPolygon(List allLine) { int size = allLine.size(); List allPoint = new ArrayList(size); for (Line line : allLine) { allPoint.add(line.getStart()); } for (int i = 0; i < size; i++) { boolean hasLeftPoint = false; boolean hasRightPoint = false; Line line = allLine.get(i); if (i + 2 < size) { // 获取线外的剩下的点 List allLeftPoint = getLeftPoint(allPoint, line); for (Point point : allLeftPoint) { if (line.hasLeftPoint(point)) { hasLeftPoint = true; } else { hasRightPoint = true; } // 按照顺时针连线后，如果有点在其中某条线的左边，同时还有点在其右边，说明是凹多边形 if (hasLeftPoint && hasRightPoint) { return false; } } } } return true; } /** *
     * 获取线外的所有点
     * 
     * @param allPoint
     * @param exceptLine
     * @return
     * 
*/ private static List getLeftPoint(List allPoint, Line exceptLine) { List allTempPoint = new ArrayList(allPoint); allTempPoint.remove(exceptLine.getStart()); allTempPoint.remove(exceptLine.getEnd()); return allTempPoint; } /** *
     * 向所有直线中加入点
     * 
     * @param allLine
     * @param point
     * 
*/ private static void addPointToLine(List allLine, Point point) { boolean hasLeftPoint = false; int size = allLine.size(); for (int i = 0; i < size; i++) { Line line = allLine.get(i); hasLeftPoint = line.hasLeftPoint(point); if (hasLeftPoint) { allLine.remove(i); Line newLeftLine1 = new Line(line.getStart(), point); Line newLeftLine2 = new Line(point, line.getEnd()); allLine.add(i, newLeftLine2); allLine.add(i, newLeftLine1); break; } } if (!hasLeftPoint) { int lastIndex = size - 1; Line newLine = new Line(allLine.get(lastIndex).getEnd(), point); allLine.add(newLine); } } /** *
     * 获取所有的点 
     * 
     * @param input
     * @return
     * @throws Exception
     * 
*/ private static List getAllPoint(String input) throws Exception { if (null == input) { throw new Exception(); } List allNum = Arrays.asList(input.split(SPLIT)); int numSize = allNum.size(); int pointSize = numSize / NUM_IN_POINT; // 组成点的元素个数如果不是2的倍数或者点的个数小于3，说明都不能组成多变性 if (0 != numSize % NUM_IN_POINT || pointSize < MIN_POINT_SIZE) { throw new Exception(); } List allPoint = new ArrayList(pointSize); try { for (int i = 0; i < numSize;) { int x = Integer.parseInt(allNum.get(i)); int y = Integer.parseInt(allNum.get(i + 1)); Point point = new Point(x, y); allPoint.add(point); i += 2; } return allPoint; } catch (NumberFormatException e) { throw new Exception(); } } /** * 判断是否有点在其他点的直线上 * *
     * 算法如下：
     * 1.从集合中的第一个点开始遍历，并出栈；
     * 2.遍历的当前点(i)和后面的每个点(序号为j,大小依次为i+1,i+2...)组成一条直线，由于当前点已出栈，j的实际序号为j-1；
     * 3.判断直线后面的点(序号为i+2，由于当前点已出栈，实际序号为i+1开始)，是否在这边直线上
     * @param allPoint
     * @return
     * 
*/ private static boolean hasPointInLine(List allPoint) { List allTempPoint = new ArrayList(allPoint); Iterator iterator = allTempPoint.iterator(); while (iterator.hasNext()) { Point point = iterator.next(); iterator.remove(); int size = allTempPoint.size(); for (int i = 0; i < size; i++) { Line line = new Line(point, allTempPoint.get(i)); if (i + 1 < size) { List allLeftPoint = allTempPoint.subList(i + 1, size); if (hasPointInLine(line, allLeftPoint)) { return true; } } } } return false; } /** *
     * 直线上是否有该点
     * 
     * @param line
     * @param otherPoint
     * @return
     * 
*/ private static boolean hasPointInLine(Line line, List otherPoint) { for (Point point : otherPoint) { if (line.containsPoint(point)) { return true; } } return false; } /** * 取距离原点最小的点 * *
     * @param allPoint
     * @return
     * 
*/ private static Point getFirstPoint(List allPoint) { List allTempPoint = new ArrayList(allPoint); Collections.sort(allTempPoint); return allTempPoint.get(0); } } 

4、单元测试类 /* *

 * 文 件 名:  PolygonSortTest.java
 * 描    述:  <描述>
 * 修改时间:  2016-4-17
 * 

*/ package com.justinsoft.polygon; import static org.junit.Assert.assertTrue; import org.junit.Test; /** *

 * <一句话功能简述>
 * 
 * 

*/ public class PolygonSortTest { /** * Test method for {@link com.justinsoft.polygon.PolygonSort#findConvexPolygon(java.lang.String)}. */ @Test public void testFindConvexPolygon1() { String input = "1,2,3"; String result = PolygonSort.findConvexPolygon(input); assertTrue("ERROR".equalsIgnoreCase(result)); } /** * Test method for {@link com.justinsoft.polygon.PolygonSort#findConvexPolygon(java.lang.String)}. */ @Test public void testFindConvexPolygon2() { String input = "0,0,1,1,0,1"; String result = PolygonSort.findConvexPolygon(input); assertTrue("0,0,0,1,1,1".equalsIgnoreCase(result)); } /** * Test method for {@link com.justinsoft.polygon.PolygonSort#findConvexPolygon(java.lang.String)}. */ @Test public void testFindConvexPolygon3() { String input = "0,0,1,1,0,1,1,0"; String result = PolygonSort.findConvexPolygon(input); assertTrue("0,0,0,1,1,1,1,0".equalsIgnoreCase(result)); } /** * Test method for {@link com.justinsoft.polygon.PolygonSort#findConvexPolygon(java.lang.String)}. */ @Test public void testFindConvexPolygon4() { String input = "0,0,1,1,0,3,3,0"; String result = PolygonSort.findConvexPolygon(input); assertTrue("ERROR".equalsIgnoreCase(result)); } }