Geometric Algorithms

 

Let

p=(x,y), q=(x',y'), r=(x'',y'')

 

sign det(p,q,r) is the same as sinf where f is slope angle of vector p->r to vector p->q

 

 

---

 

Determining whether two line segments P—Q and R—S intersect

• Determine whether points P, Q lie on opposite sides of the line containing line segment R—S, and whether points R, S lie on  opposite sides of the line containing line segment P—Q

sgn(det(p,q,r))<>sgn(det(p,q,s))

  and

sgn(det(r,s,p))<>sgn(det(r,s,q))

 

---

 

Point inside polygon

 

Given a simple polygon P and a point q, 

determine whether q is inside P.

 

Basic idea: 

’draw’ an ’infinite’ straight line from q; 

count the number of intersections with edges of P;

q is inside P if and only if this number is odd.

 

Problems

(a) Point q may lie on an edge of P

(b) Line L may overlap an edge of P

(c) Line L may pass through a point of P

(a) is easy to check, so ignore

Each of (b) or (c) should in some cases be counted as an intersection, in other cases not.

 

---

 

Finding the convex hull

The convex hull of a set of points (in the plane) is:

• the smallest convex polygon that contains the points.

• shortest fence surrounding the points

• intersection of halfplanes defined by point pairs

 

Gift-wrapping algorithm

(Operates like selection sort)

• choose a point on the hull as pivot- say the one with largest x coordinate, using smallest y coordinate to break a tie if necessary

• scan anticlockwise until we “hit” another point q - add q to the hull computed so far

• carry on the scan from point q

int wrap(POINT p[], int N)

{ int i, min, M; float th, v; struct point t;

    for (min = 0, i = 1; i < N; i++)

        if (p[i].y < p[min].y) min = i;

    p[N] = p[min]; th = 0.0;

    for (M = 0; M < N; M++)

    {

        t = p[M]; p[M] = p[min]; p[min] = t;

        min = N; v = th; th = 360.0;

        for (i = M+1; i <= N; i++)

            if (theta(p[M], p[i]) > v)

                if (theta(p[M], p[i]) < th)

                    { min = i; th = theta(p[M], p[min]);}

        if (min == N) return M;

     }

 }

 

Graham Scan

Sort points on angle with bottom point as origin forms simple closed polygon

Proceed through polygon discard points that would cause a CW turn

 

int grahamscan(struct point p[], int N)

{ int i, min, M; struct point t;

    for (min = 1, i = 2; i <= N; i++)

        if (p[i].y < p[min].y) min = i;

    for (i = 1; i <= N; i++)

        if (p[i].y == p[min].y)

        if (p[i].x > p[min].x) min = i;

        t = p[1]; p[1] = p[min]; p[min] = t;

        quicksort(p, 1, N);

        p[0] = p[N];

        for (M = 3, i = 4; i <= N; i++)

        {

            while (ccw(p[M],p[M-1],p[i]) >= 0) M--;

            M++; t = p[M]; p[M] = p[i]; p[i] = t;

        }

        return M;

}