0

What is the best way to do this only using python's built-in libraries?

Here is my code so far.

class Quadrilateral:

    class Point:
        def __init__(self, x, y):
            self.x = x
            self.y = y
  
    def __init__(self, Ax, Ay, Bx, By, Cx, Cy, Dx, Dy):
        self.A = self.Point(Ax, Ay)
        self.B = self.Point(Bx, By)
        self.C = self.Point(Cx, Cy)
        self.D = self.Point(Dx, Dy)

    # checks if a point is in the Quadrilateral
    def check(self, x, y):
        pass
Joseph Montrose
  • 5
  • 1
  • Can you precise a bit ? From what I see, the quadrilateral can be any quadrilateral. The four points could be aligned, making it a line. Three of the points could be aligned, making it a triangle. The quadrilateral could be not convex (segments AB and CD crossing eachother for instance, forming two triangles). What is the edge case when a point is strictly on one of the segment ? And when the point is on one of the segment but the quadrilateral is actually a line (first edge case listed) ? – Jenny Feb 10 '22 at 16:04
  • Does this answer your question? [How can I determine whether a 2D Point is within a Polygon?](https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon) – Jenny Feb 10 '22 at 16:10
  • @Jenny For simplicity, I'm assuming that the quadrilateral will not form a line and that none of the sides intersect. – Joseph Montrose Feb 10 '22 at 16:57
  • And do you assume it is convex as well ? edit: non convex is as soon as an angle inside the quadrilateral is above 180°, a classic arrowhead (like that: ➤) for instance is non convex – Jenny Feb 10 '22 at 17:01
  • @Jenny edit Yes, I do. – Joseph Montrose Feb 10 '22 at 17:04

1 Answers1

0

This should do it (adapted to python and your case from there):

def check(self, testx, testy):
  vertx = [self.A.x, self.B.x, self.C.x, self.D.x]
  verty = [self.A.y, self.B.y, self.C.y, self.D.y]

  c = False
  j = len(vertx)-1

  for i in range(len(vertx)):
    if ( ((verty[i]>testy) != (verty[j]>testy)) and
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ):
       c = not c

    j = i

  return c;

What it does is "tracing" an horizontal ray starting from the test point and going to the right at infinity, and counting the number of times that ray crosses one of the segments. An even number means outside, an odd number means inside, hence the c = not c each time a new segment is crossed.

The second index j is there to close the quadrilateral.

It's both short and efficient and works both for convex and concave polygons.

This will work for n-polygon, so not only quadrilaterals.

Jenny
  • 601
  • 3
  • 11