Java: finding the outer vertices of a convex polygon

Question

Original post:

I am trying to find the outer vertices of a convex polygon (relative to point P outside the polygon). At the moment, I am only interested in rectangles (however, I need an algorithm that works with any convex polygon).

My plan is to build a line from the outer point P to the center point C. From this link line, I will build 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 reference line, they will be identified as the outermost vertices.

Is this the best algorithm to work with? How to calculate angles from a reference angle (preferably in Java)?

---

Update to clarify:

I drew the lines (link bar in red). As you can see, the line from P to 2 creates the largest angle on one side of the reference line, and the line from P to 4 creates the largest angle on the other side. Therefore, these are the outermost peaks.

Answer 1

I solved the problem as follows:

// code simplified for demonstration double angleBetweenVertices; double maxAngleBetweenVertices; vectorA.setStartingPoint(outerPoint); vectorA.setTerminationPoint(polygonCenter); vectorB.setStartingPoint(outerPount); // For each vertex, calculate the angle between the outer point, the polygon center and the vertex for (Point2D.Double vertex : vertices) { vectorB.setTerminationPoint(vertex); double angleBetweenVertices = Math.toDegrees( Math.atan2( (vectorA.perpDotProduct(vectorB)), (vectorA.dotProduct(vectorB)) ) ); // Update the min and Max if (angleBetweenVertices >= maxAngleBetweenVertices) { maxVertex = vertex; maxAngleBetweenVertices = angleBetweenVertices; } else if (angleBetweenVertices <= minAngleBetweenVertices) { minVertex = vertex; minAngleBetweenVertices = angleBetweenVertices; } } 

Answer 2

This is pretty much a convex hull problem. You will look for a set of vertices (x ₁ , x ₂ ) around the polygon. The methodology that will be applied is called the “quick case”, similar to quick sorting (in this case, we each time separate our region of points). It is also a safe assumption that P can be used as an intermediate point between an arbitrary starting point and its parallel end point, so you get a convex body around P.

It will take some time to create robust Java to deflate (from my case), but I think the Wikipedia entry will give you a great starting point.

Answer 3

Using trigonometry is extremely slow. You should use a different angle comparison.

For the angle between two plane vectors:

cos (OA, OB) = (OA _x * OB _x + OA _y * OB _y ) / sqrt ((OA _x ² + OA _y ² ) * (OB _x ² + OB _y ² ))

I think you can compare angles with cosines.