三个点的位置.Graham scan.Convex Hull

Leave a comment

June 18, 2017 by oneOokay

解决的是几何问题…

  • 两条直线是否相交
  • 二维数组标示x,y的点的集合, Find simple closed path. 就是点集外檐的一个轮廓.(connect the dots without crossing)
  • 同样点的集合,求形成一个凸包的边缘点的集合.

Orientation of 3 ordered points

http://www.geeksforgeeks.org/orientation-3-ordered-points/

给3个点,判断这三个点的相对位置. 假设点p,q,r: 沿p,q,r的顺序连一条线,形成一个以q为顶点的角:从p,q到r:

  • 左转: left turn: counter clock wise
  • 右转: right turn: clock wise
private int orientation(Point p, Point p1, Point p2){
return (p1.y - p.y) * (p2.x - p1.x) - (p1.x - p.x) * (p2.y - p1.y);
//if p, p1, p2: left turn: counter clock wise: < 0; 
//if p, p1, p2: right turn: clock wise: > 0;
//if p, p1, p2: 在一条直线上collinear: = 0 
}

接下来就可以根据这个orientation 的返回值来解决那三个问题了.

直线相交: 直线1(a1, a2) 和直线2(b1, b2)相交:

http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

  • 当orientation(a1,a2,b1)与orientation(a1,a2,b2)的值符号不同且orientation(b1,b2,a1)与orientation(b1,b2,a2)的值的符号不同(互为正负或者一个为正负,另一个为0)
  • 特殊情况: 当以上四个的值都为0的时候(四个点都在一条直线上)且a1a2,b1b2的x和y都有相交的

Find Simple Closed Path for a given set of points: 

  1. 找到bottom点:y坐标最低的点,如果存在y坐标相同的点,那么取x坐标较小的.
  2. 把bottom的点换到array的第一个,接着对array的第二个到最后一个元素进行排序.

排序:

取orientation(bottom, p1, p2)的值,如果bottom,p1到p2是一个left turn的话(此时返回值为负值), p1应该排在p2之前. 如果bottom,p1,p2是在一条直线上的话,那么离bottom距离短的值放前面.反之如果是一个right turn, p2应该排在p1之前.(注意comparator的写法)

注意比较两点的距离:x坐标差的平方加上y坐标差的平方.

private void sort(Point[] points, Point p){
Arrays.sort(points, 1, points.length, new Comparator(){
public int compare(Point p1, Point p2){
	int value = orientation(p.x, p.y, p1.x, p1.y, p2.x, p2.y);
	if (value == 0) return dist(p1, p) - dist(p2, p);
return value;
}});
}
private int dist(Point p1, Point p2){
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y); 
}

凸包: (Graham Scan)

首先也是对点的orientation值进行排序(排序的和点的处理根据要求会有不同)

  • 如果是边缘的点只去收尾的话,那么当orientation== 0的时候取距离最大的点就可以.
  • 如果是需要包含处于边缘的点的话,在排序的时候,end到bottom的那条线上的点,是需要根据到bottom的距离从大到小倒序排序.

之后对排好序的点进行三个三个判断,如果有右转的点,将其跳过.实现过程是用stack,看代码…

public List outerTrees(Point[] points) {
        List res = new ArrayList<>();
        Point bottom = points[0];
        int index = 0;
        for (int i = 1; i < points.length; i ++){
            if (points[i].y < bottom.y || points[i].y == bottom.y && points[i].x < bottom.x){
                bottom = points[i];
                index = i;
            }
        }
        Point tmp = points[0];
        points[0] = points[index];
        points[index] = tmp;
        sort(points, bottom);
        if (points.length < 3) return Arrays.asList(points);
        Stack stack = new Stack<>();
        stack.push(points[0]);
        stack.push(points[1]);
        for(int i = 2; i < points.length; i ++){
             Point top = stack.pop();
             while (!stack.isEmpty() && orientation(stack.peek(), top, points[i]) > 0){ //right turn
                top = stack.pop();
            }
            stack.push(top);
            stack.push(points[i]);
        }
        return new ArrayList<>(stack);
        
    }
    
    private int orientation(Point p, Point p1, Point p2){
        return (p1.y - p.y) * (p2.x - p1.x) - (p1.x - p.x) * (p2.y - p1.y);
        //left turn : < 0; right turn > 0
    }
    
    private int dist(Point p1, Point p2){
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
    
    private void sort(Point[] points, Point o){
        Arrays.sort(points, 1, points.length, new Comparator(){
           public int compare(Point p1, Point p2){
               int value = orientation(o, p1, p2);
               return value == 0? dist(p1, o) - dist(p2, o) : value;
           } 
        });
        //对end到bottom一条线上的点进行逆序排序调整
        Point start = points[0];
        Point end = points[points.length - 1];
        int index = points.length - 2;
        while(index >= 0 && orientation(start, end, points[index]) == 0){
            index --;
        }
        int left = index + 1;
        int right = points.length - 1;
        while (left < right){
            Point tmp = points[left];
            points[left] = points[right];
            points[right] = tmp;
            left ++;
            right --;
        }
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: