Как узнать, находится ли точка по периметру QPolygon (PyQt4)

Question

Есть ли в PyQt4 какая-либо функция, помогающая мне определить, находится ли точка по периметру QPolygon? Например:

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])

Функция должна вернуть true, если я передам ей QP(1,3), QP(4,5), QP(3,2) или QP(1,1).

Answer 1

Это действительно сложный вопрос. Я много играл с несколькими методами QPolygon лайк intersected, united, subtracted но никто не принес успеха.

Например, я подумал, что это может сработать: Скопируйте многоугольник, добавьте точку к копии, а затем проверьте, является ли результат пустым. Если точка лежит по периметру многоугольника, то и оригинал, и копия должны иметь одинаковую форму и, следовательно, результат должен быть пустым.

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

Однако, кажется, что многоугольник "нарисован" в том порядке, в котором указаны точки, поэтому, если вы просто добавите точку, это приведет к некоторой другой форме. Например рассмотрим точки (0,0) (0,2) (2.2) (2,0) которые образуют квадрат, и вы хотите проверить (0,1), Тогда, если вы просто добавите точку в конце, это "соединится" (2,0) с (0,1) а также (0,1) с (0,0) так как многоугольник должен быть замкнутой формы. Это дает другую форму. Таким образом, вам придется вставить точку в правильном положении, чтобы получить ту же форму. Для этого примера это будет сразу после (0,0), Итак, я подумал, хорошо, давайте попробуем описанное выше со всеми возможными перестановками, и будет только одна конфигурация (и ее преобразования, являющиеся результатом вращения и инверсии), такая, что результат вычитания будет пустым.

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

Но почему-то это тоже не работает. Испытывая свой пример, я получаю за QP(4,5) а также QP(3,2) значение checks = 10 за QP(1,1)checks = 20 и для QP(1,3)checks = 0, То, что я ожидал, это получить checks = 12 для всех точек (так как все они лежат по периметру). 12 так как poly2 сделан из 6 точки, чтобы вы могли вращать точки 6 раз и сделать то же самое после того, как вы изменили порядок, так что 12 различные конфигурации, содержащиеся в permuts приводя к той же форме. Кроме того, если вычитание выполняется наоборот (то есть QtGui.QPolygon(list(permut)).subtracted(poly).isEmpty()) Я получил True для каждой точки также для точек, даже не лежащих внутри многоугольника, но снаружи.

Я пробовал похожие вещи, используя united а также intersected вместо isEmpty в вышеуказанной функции:

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

То же самое здесь, это следует оценивать только как True если точка фактически лежит по периметру. Но это возвращает False почти для каждого пункта я проверил ваш пример выше.

Я не смотрел на исходный код методов QPolygon (если таковые имеются), но кажется, что происходит что-то странное.

Поэтому я бы предложил вам написать собственный метод, который оценивает все линии в многоугольнике, если точка лежит на одной из них.

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

Это кажется немного тяжелым, но важно выполнять все вычисления только с целыми числами, поскольку вы можете получить неправильные результаты из-за точности с плавающей запятой (QPolygon в любом случае принимает целочисленные баллы). Хотя еще не проверено, все должно работать.