CODEWITHSUNDEEP
pythonpygame
Drew
Drew

Reputation: 1261

pygame, get closest point on a polygon from point A

I have a polygon with n points and I want to find the closest point on this polygon to my player p. How do I go about doing this?

So for in doing this I iterate over each point in a polygon of n points like so:

for i in range(points.shape[0]-1):
    for j in range(i+1, points.shape[0):

This iterates over every pair of points in a polygon, which I use as the line segment to compare against.

Then I am checking the extreme points, and also attempting to see if a point on that line segment is closer. Here is my code:

def _get_closest_point(self, P1, P2, P3):
        if numpy.linalg.norm(P3) > numpy.linalg.norm(P2):
            tmp_p3 = P3
            P3 = P2
            P2 = tmp_p3

        Ax = P3[0] - P1[0]
        Ay = P3[1] - P1[1]

        Bx = P2[0] - P3[0]
        By = P2[1] - P3[1]

        t = (Ax*Bx + Ay*By)/(2*(math.pow(Bx, 2) + math.pow(By, 2)))

        f_prime_1 = 2*(math.pow(Bx, 2) + math.pow(By, 2))

        d3 = numpy.linalg.norm(P3 - P1)
        d2 = numpy.linalg.norm(P2 - P1)
        d1 = numpy.linalg.norm(P3 + t*(P2 - P3) - P1)

        print "d1 " + str(d1)
        print "d2 " + str(d2)
        print "d3 " + str(d3)

        if d2 < d3 and d2 < d1:
            return P2
        elif d3 < d2 and d3 < d1:
            return P3
        else:
            return P3 + t*(P2 - P3)

    def _get_closest_point_poly(self, points):
        p = None

        for x in range(points.shape[0]-1):
            for y in range(x+1, points.shape[0]):
                p1 = self.origin
                p2 = points[x]
                p3 = points[y]

                tmp_p = self._get_closest_point(p1, p2, p3)

                if not isinstance(p, list):
                    p = tmp_p
                elif numpy.linalg.norm(tmp_p) < numpy.linalg.norm(p):
                    p = tmp_p
        return p

This code was adapted from the one answer here which I have not marked either as solving my question yet as I am not able to confirm either one working. I am currently trying to adapt the "r(t)=(2,0)+tP3P2" question. As it stands right now it is not working. I believe it may be my code at the moment.

When I run the code, and test my point (which is in between two points and the line should be a perpendicular to the polygon) draws to the extreme.

My code prints that the distance d3 is less than d2 and d1, so it returns P3 as the closest point. However, it should return a point between P2 and P3.

The red line shows the point it is trying to get to.

enter image description here

I am using numpy to make it easier to work with points and vectors for the linear algebra. No point in re-inventing the wheel here.

Upvotes: 2

Views: 555

Answers (1)

Micheal O&#39;Dwyer
Micheal O&#39;Dwyer

Reputation: 1261

Very interesting question!

Let's say you have a list vertices and has two dimensions in order to store the x and y value of each vertex.

Simply iterate through the list and do a simple distance formula on each of the points and record the lowest distance.

I hope this answer helped! If you have any further questions please post them below!

vertices = [[100, 100], [200, 200], [300, 300]]

player = [100, 200]

closestVertex = -1
shortestDist = -1

for vertex in vertices:
    x, y = vertex

    distance = (((x - player[0]) ** 2) + ((y - player[1]) ** 2))

    if(distance < shortestDist or shortestDist == -1):
        shortestDist = distance
        closestVertex = vertex


print(closestVertex)

Upvotes: 3

Related Questions