# 1 - Intro/Geometric 1 Flashcards

1
Q

What time complexity algorithms are said to be efficient algorithms?

A

Polynomial-time algorithms

2
Q

What is a simple polygon?

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

What is a convex polygon?

A

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

4
Q

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

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

How to solve if two line segments intersect?

A
• Split into two subproblems:
• onOppositeSides test
• boundingBox test
6
Q

What is the onOppositeSides test?

A
• 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
7
Q

What is the boundingBox test?

A

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

8
Q

How to perform onOppositeSides test?

A
• 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
9
Q

What is the onOpposideSides test algorithm?

A

/** 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

}

10
Q

How to perform boundingBox test?

A
• 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
11
Q

Putting onOppositeSides and boundingBox tests together

A
• 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)
12
Q

What is the intersect algorithm?

A

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

13
Q
A