Python-сообщество

Есть координаты m красных точек и n черных точек (n,m ≥ 1). Используя только базовые библиотеки, нужно проверить, можно ли красные и черные точки разделить прямой линией. То есть ничего предсказывать не нужно, саму линию определять тоже, только напечатать “да” или “нет”.

Я читал про выпуклые оболочки, но реализация требует использования shapely или scipy + это не сработает в некоторых случаях (т.к. convexhull'ы не строятся для ≤2 точек). Насколько понял, нужно как-то задать систему неравенств и попытаться найти коэффициенты, но в линейном программировании не силен.

Отредактировано yesenya (Дек. 24, 2018 23:34:32)

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

Если можно получить две отдельные области разных цветов, то линию можно провести между ними.

Для плоскости алгоритм может быть достаточно простым, исходя из того факта, что
наборы точек линейно разделимы только тогда, когда существует прямая, проходящая через пару точек из одной группы так, чтобы точки принадлежащие этим двум группам были по разные стороны от этой прямой. Проверит лежат ли
точки по одну сторону, или по разные просто используя нормальное уравнение прямой (уравнение прямой нормальное/нормализованное, если A*x+B*y + C =0, A**2+B**2 = 1).
Фактическим нужно построить n*(n-1)/2 + m*(m-1)/2 прямых, привести их к нормализованному виду и проверить выполняется ли условие разделимости. Если выполняется, то перебор прекратить.
Поначалу думал, что можно упростить алгоритм и рассматривать только одну группу с минимальным числом точек,
и только для нее строить разделяющие прямые, однако, это неправильно. Можно построить пример, линейно разделимых , когда все прямые, построенные только для одной группы, покажут неразделимость. Рассматривать нужно все возможные прямые n*(n-1)/2 + m*(m-1)/2 штук. (Это фактически проверка того, что не содержит ли выпуклая оболочка данной группы представителя другой группы).

scidam
Для плоскости алгоритм может быть достаточно простым, исходя из того факта, что наборы точек линейно разделимы только тогда, когда существует прямая, проходящая через пару точек из одной группы так, чтобы точки принадлежащие этим двум группам были по разные стороны от этой прямой. Проверит лежат ли точки по одну сторону, или по разные просто используя нормальное уравнение прямой (уравнение прямой нормальное/нормализованное, если A*x+B*y + C =0, A**2+B**2 = 1).Фактическим нужно построить n*(n-1)/2 + m*(m-1)/2 прямых, привести их к нормализованному виду и проверить выполняется ли условие разделимости. Если выполняется, то перебор прекратить. Поначалу думал, что можно упростить алгоритм и рассматривать только одну группу с минимальным числом точек, и только для нее строить разделяющие прямые, однако, это неправильно. Можно построить пример, линейно разделимых , когда все прямые, построенные только для одной группы, покажут неразделимость. Рассматривать нужно все возможные прямые n*(n-1)/2 + m*(m-1)/2 штук. (Это фактически проверка того, что не содержит ли выпуклая оболочка данной группы представителя другой группы).

Отредактировано yesenya (Дек. 25, 2018 12:02:44)

yesenya
у меня просто сильное ощущение, что это должна быть в принципе несложная задача

Отредактировано py.user.next (Дек. 25, 2018 14:38:37)

yesenya
но это же как-то супер неоптимально с учетом еще и проверок для всех точек, разве нет?

 def graham_convex_hull(array):
    '''Graham's scan for convex hull of a set of 2D points
       This algorithm is named after Ronald Graham, who published the original
       algorithm in 1972.
    **Parameters**
        :param array: an array of points [(x1, y1), (x2, y2), ..., (xN, yN)]
        :type array: list
        :rtype: list
        :returns: convex hull presented as a list of points
    **References**
        Graham, R.L. (1972). "An Efficient Algorithm for Determining the Convex
        Hull of a Finite Planar Set" (PDF). Information Processing Letters. 1:
        132–133. doi:10.1016/0020-0190(72)90045-2
    '''
    import math
    EPS = 1.0e-15 # very small number, epsilon1 value
    # the lesser numbers are treated as zero
    if len(array) < 3:
        raise Exception("Input array should have length greater or equal 3.")
    # helper function
    cross_product = lambda p, q: p[0] * q[1] - q[0] * p[1]
    # Additionally, one could perform checking for collinearity here
    if len(array) == 3:
        return array
    # get min index
    ys = list(map(lambda x: x[-1], array))
    y_min_ind = ys.index(min(ys))
    xmin, ymin = array[y_min_ind]
    # create array of angles
    angles = list()
    for x, y in array:
        if abs(x - xmin) > EPS:
            angles.append(math.atan((y - ymin) / (x - xmin)))
        elif abs(x - xmin) < EPS and abs(y - ymin) < EPS:
            angles.append(0.0)
        else:
            angles.append(math.pi / 2.0)
        if angles[-1] < -EPS:
            # ensure that all atan values are in [0, pi]
            angles[-1] = math.pi - angles[-1]
    # sorting array of angles
    angles_sorted_inds = sorted(range(len(angles)), key=lambda k: angles[k])
    sorted_array = [array[j] for j in angles_sorted_inds]
    stack = list()
    stack.append(sorted_array[0])
    stack.append(sorted_array[1])
    for i in range(2, len(array)):
        c, p, q = stack[-2], stack[-1], sorted_array[i]
        cross_value = cross_product([p[0] - c[0], p[1] - c[1]],
                                    [q[0] - c[0], q[1] - c[1]])
        while len(stack) >= 2 and cross_value <= -EPS:
            stack.pop()
            c, p, q = stack[-2], stack[-1], sorted_array[i]
            cross_value = cross_product([p[0] - c[0], p[1] - c[1]],
                                        [q[0] - c[0], q[1] - c[1]])
        stack.append(q)
    return stack
if __name__ == '__main__':
    test_data = [(2, 4),
                 (1, 5),
                 (2, -1),
                 (7, 3),
                 (5, 4),
                 (2, 1),
                 (7, 0),
                 (3, 1),
                 (4, 0),
                 (3.2, 3)
                 ]
    try:
        import matplotlib.pyplot as plt
    except ImportError:
        plt = None
    if plt:
        print("Lets gonna do some visualization here... ")
        plt.scatter(*zip(*test_data), s=5, marker='o')
        chull = graham_convex_hull(test_data)
        plt.scatter(*zip(*chull), s=10, marker='s')
        plt.show()
    print("=" * 40)
    print("Graham's convex hull is: ", graham_convex_hull(test_data))
    print("=" * 40)

py.user.next
Если стороны не пересекаются, то можно провести прямую между многоугольниками.

Прикреплённый файлы:
Безымянный.jpg (21,4 KБ)

Romissevd
Не всегда так будет, как пример на картинке.