CODEWITHSUNDEEP
python-3.xcsvmathgeometry
SadPaleontologist444
SadPaleontologist444

Reputation: 11

Finding the average centroid of all possible triangles given (x,y) coordinates

I have a csv file of numerous (x,y) coordinates in the first quadrant. I want to find three things:

  1. All possible triangles that can be created from the points
  2. The centroids of all of the possible triangles that can be created from the points
  3. The average of all possible centroids

I am using the code below for step 1:

def det(x1, y1, x2, y2, x3, y3):
    return (x1 * (y2 - y3) - y1 *
            (x2 - x3) + 1 * (x2 *
                             y3 - y2 * x3))
def countPoints(Point, n):
    result = 0 
       for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if (det(Point[i][0], Point[i][1],
                        Point[j][0], Point[j][1],
                        Point[k][0], Point[k][1])):
                    result = result + 1
    return result
Point = [[0, 0], [1, 1],
         [2, 0], [2, 2]]
n = len(Point)
print(countPoints(Point, n))

Now I am having trouble finding the coordinates of the number of possible triangles. Ex: If there are 3 possible triangles, I want to know their 3 vertex coordinates.

Upvotes: 0

Views: 86

Answers (1)

Christopher Miller
Christopher Miller

Reputation: 3461

To find all possible triangles that can be created from the set of points, P, you can try every possible set of 3 points from P. However, keep in mind that three points can create a triangle if and only if they are not collinear, meaning that they can't lie on the same line. This gives an O(N^3) algorithm for step number one.

The centroid of a triangle is defined as the intersection of all its medians, which seems like it would require processing the intersection point of three lines, which would be very tedious. However, if you simplify all the math, you'll find that the centroid of a triangle with coordinates (x1, y1), (x2, y2), and (x3, y3) is actually equal to ((x1+x2+x3)/3, (y1+y2+y3)/3). In other words, given a triangle, you can calculate its centroid in constant time.

For (#3), you can simply store all the centroids from the previous step in a list, and find the average by using the arithmetic mean formula:

The arithmetic mean of a set of numbers is equal to the cumulative sum of all the elements in that set divided by the number of elements in that set. The average of all the centroids can be calculated by summing all the x-values and dividing it by the number of centroids, and vice versa for the y-coordinates.

Upvotes: 1

Related Questions