网纹蟒,红绸绮梦,拜月式
在平面直角坐标系中，给定一个点序列，判断这些点是否能够构成凸多边形，
并且按照顺时针方向输出这些点。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
我要评论
* @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(); } /** * 点是否在直线的左边(按照线的起点到终点的方向来看点是左边还是右边)
* @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)); } }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论