问题
- 如何识别多边形中一个顶点的凹凸性
- 如何判断一个多边形的凹凸性（若多边形有一个点为凹的，则多边形为凹的）
- 如何通过填充凹坑的方式将凹多边形转化为凸多边形
方法
将多边形点集顺序修改为逆时针顺序
判断多边形点击顺序的方法可以参考判断多边形点集顺序，如果判断出多边形点击顺序为顺时针的话，直接将集合反转一下即可
判断一个点是否为凹点
注意：使用这方法判断的前提是多边形点击顺序是逆时针的才行
最终实现
/** * 将凹多边形转化为凸多边形 */ public class ConcaveToConvexApi { /** * 将凹多边形转化为凸多边形 * * @param pointList * @return */ public List<Point> concaveToConvex(List<Point> pointList) { List<Point> pointListClone = (List<Point>) deepClone(pointList); 将点集方向转化为逆时针方向 this.correctPolygonDirection(pointListClone); 删除掉凹点 int j = 0; while (j < pointListClone.size()) { int i = (j - 1 + pointListClone.size()) % pointListClone.size(); int k = (j + 1) % pointListClone.size(); double x1 = pointListClone.get(j).getX() - pointListClone.get(i).getX(); double y1 = pointListClone.get(j).getY() - pointListClone.get(i).getY(); double x2 = pointListClone.get(k).getX() - pointListClone.get(i).getX(); double y2 = pointListClone.get(k).getY() - pointListClone.get(i).getY(); //叉积 double crossProduct = x1 * y2 - x2 * y1; if (crossProduct > 0) { //凸顶点 j++; } else { //凹顶点或者共线 pointListClone.remove(j); if (j == pointListClone.size()) { /* 一开始是 A B C D E F G 开始时j=0，GAB不触发删除 但是FGA触发删除之后，序列变成A B C D E F，可能FAB也会触发删除，因此需要将j重置于0 */ j = 0; } else { if (j > 0) { //这里为什么j--，可以看程序下面的图 j--; } } } } return pointListClone; } /** * 修正零件的点位方向 * 先找出最高那个点的索引i，然后在对{i.x-(i-1).x，i.y-(i-1).y}和{(i+1).x-(i-1).x，(i+1).y-(i-1).y}来求叉积，看正负就知道了 * * @param pointList */ private void correctPolygonDirection(List<Point> pointList) { if (pointList.size() == 0) { return; } 找到零件的最高点 int highestPointIndex = -1; double highestY = -Double.MAX_VALUE; for (int i = 0; i < pointList.size(); i++) { if (pointList.get(i).getY() > highestY) { highestY = pointList.get(i).getY(); highestPointIndex = i; } } 纠正坐标 ///判断随着索引的进位，夹角是否为正数 //存储方向，1:顺时针；-1：逆时针 int direction = 0; Point lastPoint = pointList.get((highestPointIndex - 1 + pointList.size()) % pointList.size()); Point curPoint = pointList.get(highestPointIndex); Point nextPoint = pointList.get((highestPointIndex + 1) % pointList.size()); double x1 = curPoint.getX() - lastPoint.getX(); double y1 = curPoint.getY() - lastPoint.getY(); double x2 = nextPoint.getX() - lastPoint.getX(); double y2 = nextPoint.getY() - lastPoint.getY(); //计算向量的叉积 double crossProduct = x1 * y2 - x2 * y1; if (crossProduct > 0) { direction = -1; } else if (crossProduct < 0) { direction = 1; } //如果是顺时针的话，需要改为逆时针 if (direction == 1) { //将集合的元素反转 Collections.reverse(pointList); } } }
测试
