1 - Intro/Geometric 1

Question 1

What time complexity algorithms are said to be efficient algorithms?

Answer 1

Polynomial-time algorithms

Question 2

What is a simple polygon?

Answer 2

• No self-intersections
• it encloses a region, its inside

Question 3

What is a convex polygon?

Answer 3

Any line between two points inside the polygon don’t leave the boundary of the polygon

Question 4

Problem with “high school” method of determining if two lines intersect

Answer 4

• Involves division
  
  • costly
  • inaccurate (due to floating point representation)

Question 5

How to solve if two line segments intersect?

Answer 5

• Split into two subproblems:
  
  • onOppositeSides test
  • boundingBox test

Question 6

What is the onOppositeSides test?

Answer 6

• If two points p, q lie on opposite sides of a line through points r and s
• and whether points r, s lie on opposite sides of a line through p and q

Question 7

What is the boundingBox test?

Answer 7

Determine if the smallest rectangles whose sides are parallel to x and y axes containing each of p-q and r-s intersect

Question 8

How to perform onOppositeSides test?

Answer 8

• Determine if points a and b are on opposite sides of line l = –p1–p2–
• Equation of line l is = (l.p2.x - l.p1.x)(y - l.p1.y) - (l.p2.y - l.p1.y)(x - l.p1.x) = 0 (*)
• a and b lie on opposite sides of l if and only if LHS of (*) has opposite signs when substituted with each of a and b

Question 9

What is the onOpposideSides test algorithm?

Answer 9

/** Input: two points a, b, and a line l = —p1—p2— * Output: true if a and b lie on opposite sides of l, or if a or b lies on l; false otherwise */

private boolean onOppositeSides (Point2D.Double a, Point2D.Double b, Line l) { double g, h;

g = (l.p2.x - l.p1.x) * (a.y - l.p1.y) - (l.p2.y - l.p1.y) * (a.x - l.p1.x); h = (l.p2.x - l.p1.x) * (b.y - l.p1.y) - (l.p2.y - l.p1.y) * (b.x - l.p1.x);

return g * h

}

Question 10

How to perform boundingBox test?

Answer 10

• The bounding box of a line segment p—q is the smallest rectangle containing p—q whose sides are parallel to the x and y axes
• Two lines can’t possibly intersect if their bounding boxes don’t intersect

Question 11

Putting onOppositeSides and boundingBox tests together

Answer 11

• Line segments p—q and r—s intersect if and only if all three tests return true
• onOppositeSides(p,q,—r—s—)
  
  • onOppositeSides(r,s,—p—q—)
    
    • boundingBox(p—q,r—s)

Question 12

What is the intersect algorithm?

Answer 12

Determines if two lines intersect using onOpposideTests and boundingBox tests

/** Input: two line segments l1 (p—q) and l2 (r—s) * Output: returns true if the two line segments have a point in common; returns false otherwise */

public boolean intersect (Line l1, Line l2 ) {

Point2D.Double p = l1.p1;

Point2D.Double q = l1.p2;

Point2D.Double r = l2.p1;

Point2D.Double s = l2.p2;

return (onOppositeSides(p, q, l2) && onOppositeSides(r, s, l1) && boundingBox(p—q, r—s));

}

Intersect is O(1) complexity