How to know if a point is on the perimeter of a QPolygon (PyQt4)

Question

Is there any function in PyQt4 to help me decide if a point is on the perimeter of a QPolygon? For example:

from PyQt4 import QtGui
from PyQt4.QtCore import Qt, QPoint as QP

polygon = QtGui.QPolygon([QP(0, 1),  QP(3,7), QP(4, 6), QP(4,3), QP(2,1), QP(0,1])

The function should return true if I pass QP(1,3), QP(4,5), QP(3,2) or QP(1,1) to it.

Answer 1

This is a tough one indeed. I played around a lot with several methods of QPolygon like intersected, united, subtracted but none brought any success.

For example I thought this might work: Copy the polygon, add the point to the copy and then check if the result is empty. If the point lies on the perimeter of the polygon both the original and the copy should have the same shape and therefore the result should be empty.

def on_perimeter(poly, point):
    poly2 = poly + QtGui.QPolygon()  # copy the polygon
    poly2.add(point)
    return poly.subtracted(poly2).isEmpty()

However a polygon seems to be 'drawn' in the order the points are given thus if you just add the point this leads to some other shape. For example consider the points (0,0) (0,2) (2.2) (2,0) which form a square and you want to check (0,1). Then if you just add the point at the end this will 'connect" (2,0) with (0,1) and (0,1) with (0,0) since a polygon has to be a closed form. This gives some other shape. Thus you would have to insert the point at the right position to get the same shape. For this example it would be right after (0,0). So I thought, ok, lets try the above with all possible permutations and there will be only one configuration (and its transformations resulting from rotation and inversion) such that the result of the subtraction is empty.

import itertools

def on_perimeter(poly, point):
    points = [point]  # the points of the new polygon
    for ii in range(0, poly.size()):
        points += [poly.point(ii)]

    permuts = list(itertools.permutations(points))  # all possible permutations

    checks = 0
    for permut in permuts:
        checks += int(poly.subtracted(QtGui.QPolygon(list(permut))).isEmpty())

    return checks

But somehow this doesn't work either. Trying out your example I get for QP(4,5) and QP(3,2) a value of checks = 10 for QP(1,1) checks = 20 and for QP(1,3) checks = 0. What I would have expected is to get checks = 12 for all of the points (since they all lie on the perimeter). 12 because poly2 is made of 6 points so you can rotate the points 6 times and do the same after you inverted the order so have 12 different configurations contained in permuts leading to the same shape. Furthermore if the subtraction is performed the other way round (i.e. QtGui.QPolygon(list(permut)).subtracted(poly).isEmpty()) I get True for every point also for points not even lying within the polygon but outside.

I tried similar things using united and intersected instead of isEmpty in the above function:

tmp = QtGui.QPolygon(list(permut))
checks += int(poly.intersected(tmp) == poly.united(tmp))

Same here, it should only evaluate as True if the point is actually lying on the perimeter. But this gives back False for almost every point I checked of your above example.

I didn't take a look at the source code of the methods of QPolygon (if any available) but it appears that there is some weird stuff happening.

So I would suggest you to write an own method which evaluates for all lines in the polygon if the point lies on one of it.

def on_perimeter(poly, point):
    lines = []
    for ii in range(1, poly.size()):
        p1 = poly.point(ii-1)
        p2 = poly.point(ii)
        lines += [ ( (p1.x(), p1.y()), (p2.x(), p2.y()) ) ]
    lines += [ ( (poly.last.x(), poly.last.y()), (poly.first.x(), poly.first.y()) ) ]

    for line in lines:
        dx = line[1][0] - line[0][0]
        dy = line[1][1] - line[0][1]

        if abs(dx) > abs(dy) and dx*dy != 0 or dx == 0 and dy == 0:  # abs(slope) < 1 and != 0 thus no point with integer coordinates can lie on this line
            continue

        if dx == 0:
            if point.x() == line[0][0] and (point.y()-line[[0][1])*abs(dy)/dy > 0 and (line[1][1]-point.y())*abs(dy)/dy > 0:
                return True

        if dy == 0:
            if point.y() == line[0][1] and (point.x()-line[[0][0])*abs(dx)/dx > 0 and (line[1][0]-point.x())*abs(dx)/dx > 0:
                return True

        dx2 = point.x() - line[0][0]
        dy2 = point.y() - line[0][1]

        if dx*dx2 < 0 or dy*dy2 < 0:
            continue

        if abs(dx) % abs(dx2) == 0 and abs(dy) % abs(dy2) == 0:
            return True

    return False

This appears to be a bit heavy but it is important to perform all calculations with integers only since you could get wrong results due to floating point precision (QPolygon takes integer points only anyway). Although not tested yet it should work.