判斷凸多邊形並排序算法

在平面直角坐標系中，給定一個點序列，判斷這些點是否能夠構成凸多邊形，

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 * 

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

/*
 * 

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

 * 線
 * 

     * @param point
     * @return
     * 

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

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); } } 

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

 * <一句話功能簡述>
 * 
 *