# 2 - Geometric 2 Flashcards

How to connect a set of points to form a simple polygon?

- Use a circular scan
- start at a point p (pivot) and connect each points as encountered as you scan over them in a circle

What is the problem with a circular scan?

Can have lines between points that cross over regions belonging to other lines (Extend each line out to edge of circular scan to form regions)

How to successfully perform circular scan?

- Choose the pivot, p to be a particular point in the input set
- e.g. point with largest x coord

When is a circular scan successfull?

When each line resides in its own region in the circle and no line crosses into other regions

What is the simplePolygon algorithm?

/** Input: an arbitrary polygon, points, of n points, * i.e., a sequence of n points * Output: points, sorted to give a simple polygon */

public void simplePolygon (PointSet points) {

double num, denom;

double [] angle = new double[points.length];

select_largest_xcoord(points); /* modifies points so that points[0] contains the point with * largest x-coord (and smallest y-coord if a tie) */ for (int i=1; i

What is the complexity of the simplePolygon algorithm?

- loop is O(n) where n is number of points
- sort is O(n log n)
- so overall O(n log n)

What complication can occur in simplePolygon algorithm?

- If two or more points are collinear with the pivot (points[0])
- If so, further sort these points in increasing order of distance from pivot

How can simplePolygon be simplified?

- don’t need to use arctan
- can sort on line gradients don’t need to compute square root to sort on distances

What is the convex hull problem?

- convex hull of a set of points is the smallest (total length of edges, or area) possible polygon that contains the points
- given a set P of n points, find their convex hull
- Uses Graham Scan algorithm, O(n log n) time

convex hull example

the convex hull doesn’t need to include all points in P 1 2 3 4 4!=24 ways to connect, only 3 give distinct polygons 1234 1243 1324 none are convex 124 (with 3 in middle) gives a convex polygon

What are the properties of a convex hull

- Every point of the convex hull of P is itself a member of P
- the points of P with largest/smallest x/y coords are points of the convex hull of P the furthest pair of points in P of the convex hull of P

What is the Graham Scan algorithm?

- Choose a point known to be on the hull as pivot – say the point with the largest x coordinate (using the smallest y coordinate to break a tie if necessary)
- Scan the remaining points in order of angle to the pivot
- For each point, include it in temporary hull, possibly excluding one or more of its predecessors

How to perform Graham Scan algorithm?

- As we trace out the potential hull, we expect to ‘turn left’ along each point from the pivot point
- If we ‘turn right’ we must exclude one or more points p5 must be excluded because the angle between -p4 — p5- and -p5 — p6- is 180º p4 must be excluded because the angle between -p3 — p4- and -p4 — p6- is 180º need to exclude points that would cause lines to exit polygon boundary, should only be the furthest boundary points

What is the Graham Scan algorithm code?

/** Input: an arbitrary polygon p of n points, * i.e., a sequence of n points * Output: q, a simple polygon that is the convex hull * of the points in p */

public PointSet grahamScan(PointSet p) {

simplePolygon(p); // earlier algorithm

PointSet q = new PointSet(p.length);

q[0..2] = p[0..2]; // deep copy

int m = 2;// m points other than pivot in current hull

for (int k = 3; k = Math.PI)

m–; // exclude q[m]

q[++m] = p[k]; // add p[k] to the current hull

}

return q[0..m];

}

What is the complexity of Graham Scan?

- Complexity of grahamScan simplePolygon is O(n log n)
- angle function has O(1) complexity - gives the anticlockwise angle between the positive
- direction of - -q[m-1]—q[m]- and the positive direction of -q[m]—p[k]- - in fact only need to know whether angle is - can be implemented without using trig functions Main loop has O(n) complexity (a point is eliminated at most once) - So overall O(n log n) - consequence of sorting

- check this slide