0
$\begingroup$

Say I have a arbitrary convex polygon, what I wonder is the longest length from its centroid to its vertex, and which vertex it is.

I've looked it up on Wikipedia finding that I have to calculate its area firstly, then there's a formula determine the coordinates of centroid. I can then calculate all the lengths. Is there any other way faster?

$\endgroup$
1
  • $\begingroup$ Is your polygon regular? How may sides does it have? Could you show us it's form? $\endgroup$ – Guilherme Thompson Dec 16 '15 at 13:09
0
$\begingroup$

Actually the area of a convex polygon is computationally quite easy: it is the sum of the (oriented) areas of all the triangles formed by the origin of the coordinate system and two adjacent vertices (in a fixed order around the circumference of the polygon).

The double of the oriented area of such an individual triangle is $A_i=v_{i,x}v_{i+1,y}-v_{i,y}v_{i+1,x}.$ You will also need the individual $A_i,$ not just their sum, in your formula for the centroid.

The idea is that you can apply the "subdivision" from Wikipedia using any point of the plane as the third vertex of your triangles, even if it lies outside the polygon (as the origin of the coordinate system might), as long as you use oriented areas. Remember that oriented areas may be negative.

The centroid of an individual triangle is also easily computed as (two thirds of) $v_i+v_{i+1}.$

This means that your computation has to loop through the vertices once to calculate the $x$ and $y$ coordinates of the centroid of the polygon, and one more time to find the vertex (or vertices) with minimal distance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.