Сформируйте прямоугольник из точек плоскости

Я не могу говорить о том, чтобы найти подходящую функцию затрат для оценки того, что такое хороший прямоугольник. Судя по комментариям, есть много дискуссий, но нет единого мнения. Так что пока я собираюсь просто использовать функцию подсчета очков, которая штрафует четырехточечные формы за углы, которые дальше от 90 градусов. В частности, я суммирую квадрат расстояния. Если вы хотите иметь другую метрику оценки, вы можете заменить вычисление в функции scoreFunc.

Я настроил интерактивное окно, где вы можете щелкнуть, чтобы добавить точки. Когда вы нажмете «q», он возьмет эти точки, найдет все возможные комбинации (не перестановки) из 4 точек, а затем запустит функцию подсчета очков для каждой и выберет лучшую.

Я использую рекурсивный поиск грубой силы. Чтобы избежать тонны дубликатов, я придумал функцию хеширования, которая работает независимо от порядка. Я использовал простые числа для идентификации каждой точки, а функция хеширования просто берет произведение идентификаторов точек. Это гарантирует, что (1,3,5,7) совпадает с (3,1,7,5). Я использовал простые числа, потому что произведение простых чисел в этой ситуации уникально (их нельзя разложить на множители и сгруппировать, потому что они простые).

После поиска я должен убедиться, что точки расположены таким образом, что линии не пересекаются. Я использую в своих интересах контурную область OpenCV, чтобы сделать этот расчет для меня. Я могу поменять местами первую точку с ее соседями по горизонтали и вертикали и сравнить площади с оригиналом. Фигуры бабочки из пересекающихся линий будут иметь меньшую площадь (я почти уверен, что они на самом деле имеют нулевую площадь, потому что они не считаются замкнутыми фигурами), чем форма без пересечения.

import cv2
import numpy as np
import math

# get mouse click
click_pos = None;
click = False;
def mouseClick(event, x, y, flags, param):
    # hook to globals
    global click_pos;
    global click;

    # check for left mouseclick 
    if event == cv2.EVENT_LBUTTONDOWN:
        click = True;
        click_pos = (x,y);

# prime hash function
def phash(points):
    total = 1;
    for point in points:
        total *= point[0];
    return total;

# checks if an id is already present in list
def isInList(point, curr_list):
    pid = point[0];
    for item in curr_list:
        if item[0] == pid:
            return True;
    return False;

# look for rectangles
def getAllRects(points, curr_list, rects, curr_point):
    # check if already in curr_list
    if isInList(curr_point, curr_list):
        return curr_list;

    # add self to list
    curr_list.append(curr_point);

    # check end condition
    if len(curr_list) == 4:
        # add to dictionary (no worry for duplicates)
        rects[phash(curr_list)] = curr_list[:];
        curr_list = curr_list[:-1];
        return curr_list;

    # continue search
    for point in points:
        curr_list = getAllRects(points, curr_list, rects, point);
    curr_list = curr_list[:-1];
    return curr_list;

# checks if a number is prime
def isPrime(num):
    bound = int(math.sqrt(num));
    curr = 3;
    while curr <= bound:
        if num % curr == 0:
            return False;
        # skip evens
        curr += 2;
    return True;

# generate prime number id's for each point
def genPrimes(num):
    primes = [];
    curr = 1;
    while len(primes) < num:
        if isPrime(curr):
            primes.append(curr);

        # +2 to skip evens
        curr += 2;
    return primes;

# swap sides (fix intersecting lines issue)
def swapH(box):
    new_box = np.copy(box);
    new_box[0] = box[1];
    new_box[1] = box[0];
    return new_box;
def swapV(box):
    new_box = np.copy(box);
    new_box[0] = box[3];
    new_box[3] = box[0];
    return new_box;

# removes intersections
def noNoodles(box):
    # get three variants
    hbox = swapH(box);
    vbox = swapV(box);

    # get areas and choose max
    sortable = [];
    sortable.append([cv2.contourArea(box), box]);
    sortable.append([cv2.contourArea(hbox), hbox]);
    sortable.append([cv2.contourArea(vbox), vbox]);
    sortable.sort(key = lambda a : a[0]);
    return sortable[-1][1];

# 2d distance
def dist2D(one, two):
    dx = one[0] - two[0];
    dy = one[1] - two[1];
    return math.sqrt(dx*dx + dy*dy);

# angle between three points (the last point is the middle)
# law of cosines
def angle3P(p1, p2, p3):
    # get distances
    a = dist2D(p3, p1);
    b = dist2D(p3, p2);
    c = dist2D(p1, p2);

    # calculate angle // assume a and b are nonzero
    numer = c**2 - a**2 - b**2;
    denom = -2 * a * b;
    if denom == 0:
        denom = 0.000001;
    rads = math.acos(numer / denom);
    degs = math.degrees(rads);
    return degs;


# calculates a score
def scoreFunc(box):
    # for each point, calculate angle
    angles = [];
    for a in range(len(box)):
        prev = box[a-2][0];
        curr = box[a-1][0];
        next = box[a][0];
        angles.append(angle3P(prev, next, curr));

    # for each angle, score on squared distance from 90
    score = 0;
    for angle in angles:
        score += (angle - 90)**2;
    return score;

# evaluates each box (assigns a score)
def evaluate(boxes):
    sortable = [];
    for box in boxes:
        # INSERT YOUR OWN SCORING FUNC HERE
        sortable.append([scoreFunc(box), box]);
    sortable.sort(key = lambda a : a[0]);
    return sortable;

# set up callback
cv2.namedWindow("Display");
cv2.setMouseCallback("Display", mouseClick);

# set up screen
res = (600,600,3);
bg = np.zeros(res, np.uint8);

# loop
done = False;
points = [];
while not done:
    # reset display
    display = np.copy(bg);

    # check for new click
    if click:
        click = False;
        points.append(click_pos);

    # draw points
    for point in points:
        cv2.circle(display, point, 4, (0,200,0), -1);

    # show
    cv2.imshow("Display", display);
    key = cv2.waitKey(1);

    # check keypresses
    done = key == ord('q');

# generate prime number id's for each point
# if you have a lot of points, it would be worth it
# to just have a .txt file with a bunch of pre-gen primes in it
primes = genPrimes(len(points));
print(primes);
withPrimes = [];
for a in range(len(points)):
    withPrimes.append([primes[a], points[a]]);

# run brute-force search over all points
rects = {};
for a in range(len(withPrimes)):
    getAllRects(withPrimes, [], rects, withPrimes[a]);
print(len(rects));

# extract just the points (don't need the prime id's anymore)
boxes = [];
for key in rects:
    box = [];
    for item in rects[key]:
        box.append([item[1]]);
    boxes.append(np.array(box));

# go through all of the boxes and un-intersect their sides
for a in range(len(boxes)):
    boxes[a] = noNoodles(boxes[a]);

# draw each one to check for noodles
# for box in boxes:
#   blank = np.zeros_like(bg, np.uint8);
#   cv2.drawContours(blank, [box], -1, (255,255,255), -1);
#   cv2.imshow("Box", blank);
#   cv2.waitKey(0);

# noodles have been squared get best box
sortedBoxes = evaluate(boxes);
bestBox = sortedBoxes[0][1];

# draw
blank = np.zeros_like(bg, np.uint8);
cv2.drawContours(blank, [bestBox], -1, (255,255,255), -1);
for point in points:
    cv2.circle(blank, point, 4, (0,200,0), -1);
cv2.imshow("Best", blank);
cv2.waitKey(0);