# 1 - Intro/Geometric 1 Flashcards

What time complexity algorithms are said to be efficient algorithms?

Polynomial-time algorithms

What is a simple polygon?

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

What is a convex polygon?

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

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

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

How to solve if two line segments intersect?

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

What is the onOppositeSides test?

- 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

What is the boundingBox test?

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

How to perform onOppositeSides test?

- 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

What is the onOpposideSides test algorithm?

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

}

How to perform boundingBox test?

- 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

Putting onOppositeSides and boundingBox tests together

- 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)

- onOppositeSides(r,s,—p—q—)

What is the intersect algorithm?

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