11 Feb 10 An efficient algorithm for straight line in convex polygon queries

Description

Given a single convex polygon and a sequence of straight lines, quickly determine whether the straight line intersect with the convex polygon for each query straight line.

Algorithm

I’ll show you an efficient algorithm which can run in O(n – log(n)). It can also report the two intersections after running binary search. (more…)

Tags: Computational Geometry

09 Feb 10 Two efficient algorithms about Point in convex polygon queries

This problem can be described like this: Given a single convex polygon and a sequence of query points, quickly determine whether a point is in the polygon or not.

I’ll show you two efficient algorithm which can both run in O (n – log(n)). In addition, the first algorithm can expand to star-shaped polygon and the second can expand to monotone polygon.

Star-shaped polygon: a polygon P is called star-shaped if and only if there exists a point z such that for each point p of P the segment zp lies entirely within P.

Monotone polygon: a polygon P is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice. We call straight line L as the normal line of the polygon P.

Convex polygon is star-shaped and is also monotone with respect to any straight line.

The first algorithm:

1. Choose an edge AB and its midpoint P.

2. Link P to every vertex on the polygon so we can get n vectors which are already sorted by those slopes.

3. For each point X of a query, check if it is on the right side of vector AB. If it does, then return X is outside of the polygon. If it’s on line AB, then check if it is on the segment AB. If it does, then return X is on the edge AB of the polygon.

4. Now, we are sure that X is on the left side of vector AB. The next step, we use new vector PX to run a binary search which is based on the vectors we got at step 2, then we can get an interval where vector PX belongs. There must be an edge of the polygon in that interval.

5. Check the relation between the edge and the vector PX. Finally, we can get the answer.

In step 4, function atan2 can be use to get the slope of each vector, and then we run binary search by those slopes. Actually, we can run binary search on any objects as long as we define the “less” between them. Slope of course can be used to define “less”, but to be better we can use cross product to define “less” to get a more graceful implement.

Extend to star-shaped polygon:

Similar algorithm is possible for star-shaped polygon where we need to calculate the kernel first. Point P can be found in the kernel and “less” can also be defined by slopes or product cross.

(more…)

Tags: Computational Geometry