欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

判断凸多边形并排序算法

程序员文章站 2022-04-12 19:57:10
在平面直角坐标系中,给定一个点序列,判断这些点是否能够构成凸多边形, 并且按照顺时针方向输出这些点。 其他要求: 1.输出的起始的为距离原点最近的点,如果多点距离原点相等...

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

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

其他要求:
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)); } }