Алгоритм поиска максимально удаленных точек между двумя другими точками

Question

Алгоритм поиска максимально удаленных точек между двумя другими точками

Рейтинг: 0Ответов: 1Опубликовано: 02.04.2023

имеется такая проблема: нужно найти максимально удаленные точки между двумя другими.

На первом рисунке найдены точки 1 и 2 ( 1 - это максимально удаленная от центра тяжести, 2 - максимально удаленная от 1ой). Далее точки находятся как наиболее удаленные от тех между которыми они находятся и отношение высоты, опущенной из найденной точки на основание получившегося треугольника не превышает определенного заданного значения. Например, точка 3 и 4 будут расположены как на втором рисунке, зеленая линия - высота, основание это отрезок от 1 до 2 точки.

Как составить цикл для нахождения всех таких точек? Поясню: дальше идет поиск между 1 и 3, 3 и 2 точками и т.д. Пока что есть криво написанный цикл, который не дает нужного результата (да и не должен по сути, я пока не могу его правильно написать).

pointset - это массив координат всех точек контура, имеющий вид: [[x1,y1,z1]...[xn, yn, zn]], z - это признак того, что это нужная точка (z = 1), если она еще не обработана z = 0, тут тоже вопрос, как отмечать обработанные и не попавшие под условие точки? в pointset координаты продублированы (то есть в нем два раза больше элементов, чтобы можно было идти как от 1 к 2 точке, так и от 2 к 1) и точки 1 и 2 уже имеют признак z = 1.

temp - массив индексов элементов, у которых z = 1

point_n = None
temp = []
max = 0
check = 0
n = 3
while check < 5: # 5 итераций для теста
    max = 0
    temp = [i for i in range(len(pointset)) if pointset[i][2] == 1]
    for d in range(len(temp)):
        for k in range(1, len(temp)):
            point_a = pointset[temp[d]]
            point_b = pointset[temp[k]]
            for j in range(temp[d]+1, temp[k]):
                dx1 = pointset[j][0] - point_a[0]
                dy1 = pointset[j][1] - point_a[1]
                dx2 = pointset[j][0] - point_b[0]
                dy2 = pointset[j][1] - point_b[1]
                r1 = math.sqrt(dx1 * dx1 + dy1 * dy1)
                r2 = math.sqrt(dx2 * dx2 + dy2 * dy2)
                r = r1 + r2
                if r > max:
                    max = r
                    point_n = pointset[j]
        print(point_n)
        a = math.sqrt((point2[0] - point1[0]) * (point2[0] - point1[0]) + (point2[1] - point1[1]) * (point2[1] - point1[1]))
        b = math.sqrt((point2[0] - point_n[0]) * (point2[0] - point_n[0]) + (point2[1] - point_n[1]) * (point2[1] - point_n[1]))
        c = math.sqrt((point1[0] - point_n[0]) * (point1[0] - point_n[0]) + (point1[1] - point_n[1]) * (point1[1] - point_n[1]))
        p = (a + b + c) / 2
        h = (2 * math.sqrt(p * (p - a) * (p - b) * (p - c))) / a
        e = h / a
        if e > 0.05:
            point_n[2] = 1
        else:
            point_n[2] = -1
        for point in pointset:
            if point[0] == point_n[0] and point[1] == point_n[1]:
                point = point_n
        cv2.circle(img_contours, (point_n[0], point_n[1]), 5, (255, 255, 255), -1)
        cv2.putText(img_contours, f"{n}", (276, 198), font, 0.5, (255, 255, 255), 2)
        cv2.line(img_contours, (point_a[0], point_a[1]), (point_n[0], point_n[1]), (255, 255, 255), 1)
        cv2.line(img_contours, (point_b[0], point_b[1]), (point_n[0], point_n[1]), (255, 255, 255), 1)
        n += 1
    check += 1

python opencv массивы изображения циклы

Источник: Stack Overflow на русском

Answer 1

▲ 0

Можно воспользоваться преобразованием Радона и найти максимальную ширину уже на образе. Вот упрощенный пример:

import numpy as np
import cv2
im=cv2.imread('chip.png', cv2.IMREAD_GRAYSCALE)
im=cv2.threshold(im, 127, 255, cv2.THRESH_BINARY)[1]

def radon(im):
    angles=range(0, 180) # шаг поворота - 1 градус
    h,w=im.shape
    center=(w/2, h/2)
    res=[]
    for a in angles:
        m=cv2.getRotationMatrix2D(center, a, 1)
        rot_im=cv2.warpAffine(im, m, (im.shape[1], im.shape[0]))
        proj=cv2.reduce(rot_im, 0, cv2.REDUCE_MAX)[0] #  проекция на ось x
        nonzero=np.flatnonzero(proj) # индексы непулевых элементов
        width=np.ptp(nonzero) # расстояние между последним и первым ненулевым элементом в проекции.
        res.append(width)
    return max(res)
print(radon(im))

Для скорости при поиске максимума можно использовать бинарный поиск или SciPy

Алгоритм поиска максимально удаленных точек между двумя другими точками

Ответы