Java: Finding the Outermost Vertices of a Convex Polygon

Question

Original post:

I'm trying to find the outermost vertices of a convex polygon (with relation to a point P outside the polygon). For now, I'm only concerned with rectangles (however, I'd like an algorithm that works with any convex polygon).

My plan is to construct a line from external point P to central point C. From this line of reference, I will construct lines from point P to points 1, 2, 3 and 4. Since points 2 and 4 will have the largest (most positive) and smallest (most negative) angles from the line of reference, they will be identified as the outermost vertices.

Is this the best algorithm for the job? How does one calculate angles from a reference angle (preferably in Java)?

---

Update for clarification:

I've drawn the lines (line of reference in red). As you can see, the line from P to 2 creates the largest angle on one side of the line of reference, while the line from P to 4 creates the largest angle of the other side. Hence, these are the outermost vertices.

Answer 1

This is pretty much the convex hull problem. You would be looking for a set of vertices (x₁, x₂) around a polygon. The methodology that would be applied is called "quick-hull", analogous to quicksort (in that we divide our region of points every time we step through). It is also a safe assumption that P can be used as a mid-point between an arbitrary starting point and its parallel ending point, so you would get a convex hull around P.

It would take a while to produce some reliable Java to poke at (from my happenstance), but I think that the Wikipedia entry will give you a great starting point.