trapezium_vertex_approximation.py

#!/usr/bin/env python

from PIL import Image, ImageDraw

original_points = [[[1912, 197]],[[1909, 209]],[[1906, 220]],[[1891, 274]],[[1878, 318]],[[1863, 367]],[[1852, 402]],[[1841, 436]],[[1826, 482]],[[1820, 500]],[[1793, 578]],[[1782, 609]],[[1757, 678]],[[1741, 722]],[[1717, 787]],[[1694, 848]],[[1652, 958]],[[1626, 1025]],[[1624, 1029]],[[1623, 1030]],[[1608, 1031]],[[1552, 1033]],[[1522, 1034]],[[1478, 1035]],[[1419, 1036]],[[531, 1044]],[[314, 1044]],[[294, 1043]],[[293, 1042]],[[292, 1040]],[[284, 1019]],[[263, 962]],[[211, 817]],[[201, 789]],[[189, 755]],[[175, 715]],[[167, 692]],[[154, 654]],[[120, 552]],[[108, 515]],[[98, 484]],[[92, 465]],[[87, 449]],[[71, 397]],[[61, 364]],[[56, 347]],[[38, 284]],[[33, 266]],[[25, 237]],[[21, 222]],[[16, 203]],[[10, 180]],[[10, 176]],[[19, 175]],[[45, 173]],[[73, 171]],[[103, 169]],[[121, 168]],[[184, 165]],[[207, 164]],[[262, 162]],[[294, 161]],[[334, 160]],[[387, 159]],[[509, 158]],[[541, 158]],[[1424, 161]],[[1492, 162]],[[1542, 163]],[[1583, 164]],[[1619, 165]],[[1646, 166]],[[1694, 168]],[[1716, 169]],[[1737, 170]],[[1755, 171]],[[1790, 173]],[[1806, 174]],[[1836, 176]],[[1864, 178]],[[1877, 179]],[[1889, 180]],[[1893, 181]],[[1907, 188]],[[1912, 191]]]

def aproximate_rectangle(points):
    def _get_dimensions(points):
        dimensions = [
            [points[0][0], points[0][0]], 
            [points[0][1], points[0][1]]
        ]
        for p in points:
            if p[0] < dimensions[0][0]:
                dimensions[0][0] = p[0]
            if p[0] > dimensions[0][1]:
                dimensions[0][1] = p[0]

            if p[1] < dimensions[1][0]:
                dimensions[1][0] = p[1]
            if p[1] > dimensions[1][1]:
                dimensions[1][1] = p[1]

        return dimensions

    def _get_size(dimensions):
        return {
            'width': dimensions[0][1]-dimensions[0][0],
            'height': dimensions[1][1]-dimensions[1][0]
        }

    def _get_center_point(dimensions):
        return {
            'x': dimensions[0][1] / 2 - dimensions[0][0] / 2, 
            'y': dimensions[1][1] / 2 - dimensions[1][0] / 2
        }

    def _slice_by_zones(zones, points):
        """
        Рассовывем точки на четыре зоны: левая верхняя, левая нижняя, 
        правая верхняя и правая нижняя для рассчета площади треугольника в каждой из них
        """

        for p in points:
            if p[0] < center_point['x']:
                if p[1] < center_point['y']:
                    zones['tl'].append(p)
                else:
                    zones['bl'].append(p)

            if p[0] > center_point['x']:
                if p[1] < center_point['y']:
                    zones['tr'].append(p)
                else:
                    zones['br'].append(p)
        return zones


    def _triangle_area(point_1=(), point_2=(), point_3=()):
        return abs(
            0.5*(point_1[0]*(point_2[1]-point_3[1])+point_2[0] * 
            (point_3[1]-point_1[1])+point_3[0]*(point_1[1]-point_2[1]))
        )

    dimensions = _get_dimensions(points) # структура такая — (x0, x1, y0, y1)
    size = _get_size(dimensions)
    center_point = _get_center_point(dimensions)
    zones = {
        'tl': [],
        'tr': [],
        'bl': [],
        'br': []
    }
    final_coordinates = {
        'tl': None,
        'tr': None,
        'br': None,
        'bl': None
    }

    # получаем четыре зоны
    zones = _slice_by_zones(zones, original_points)

    # вычисляем габариты каждой зоны
    zones_dimensions = { zone: _get_dimensions(zones[zone]) for zone in zones.keys()}

    # это вершины треугольника внутри каждой зоны, две вершины мы берем из габаритов самого треугольника, 
    # третью будем вычислять
    vertex_by_zone = {
        'tl': (
            (zones_dimensions['tr'][0][0], zones_dimensions['tr'][1][1]), 
            (zones_dimensions['tr'][0][1], zones_dimensions['tr'][1][0])
        ),
        'tr': (
            (zones_dimensions['tr'][0][0], zones_dimensions['tr'][1][0]), 
            (zones_dimensions['tr'][0][1], zones_dimensions['tr'][1][1])
        ),
        'bl': (
            (zones_dimensions['bl'][0][0], zones_dimensions['bl'][1][0]), 
            (zones_dimensions['bl'][0][1], zones_dimensions['bl'][1][1])
        ),
        'br': (
            (zones_dimensions['br'][0][0], zones_dimensions['br'][1][1]), 
            (zones_dimensions['br'][0][1], zones_dimensions['br'][1][0])
        )
    }
    
    # считаем площадь для треугольников в каждой секции
    zones_areas = {}
    for zone in zones.keys():
        for p in zones[zone]:
            if zones_areas.get(zone, None) is None:
                zones_areas[zone] = {}
            zones_areas[zone][_triangle_area(vertex_by_zone[zone][0], vertex_by_zone[zone][1], p)] = p

    # вычисляем итоговые координаты крайних точек трапеции
    final_coordinates = {
        zone: zones_areas[zone][sorted(zones_areas[zone], reverse=True)[0]] \
        for zone in final_coordinates.keys()
    }
    
    return list((coord for coord in final_coordinates.values()))

def draw_rectangle(points, im=None, color=(255, 255, 255, 100)):
    if not im:
        im = Image.new('RGBA', (1920, 1280), (0, 0, 0, 100)) 
    draw = ImageDraw.Draw(im)
    draw.polygon(points, fill=color, outline=color)
    return im

if __name__ == "__main__":
    original_points = list(map(lambda  x: (x[0][0], x[0][1]), original_points))
    points = aproximate_rectangle(original_points)
    
    im = draw_rectangle(original_points) # рендерим оригинальный набор точек
    im = draw_rectangle(points, im=im, color=(255, 0, 0, 20)) # рендерим апроксимированный результат
    
    im.save("./rectange.png", "PNG")

    print(points)