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

@Oberok · Регистрация: 11.03.2011

Author24 — интернет-сервис помощи студентам

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

За ранее спасибо.

@kabenyuk · 18.08.2015, 15:36

Другими словами. Некто нарисовал на черном экране белый четырехугольник. Наша задача найти его вершины. Так?
Если так, то алгоритм может быть основан на следующем замечании. Пиксель является вершиной (многоугольника) если в достаточно малом круге с центром в этом пикселе черных и белых пикселей примерно поровну.

@Igor3D · 18.08.2015, 17:49

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

@Oberok · 18.08.2015, 18:15 **[ТС]**

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

Задача решена !

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

@Igor3D · 18.08.2015, 18:36

Сообщение от Oberok

Задача решена !

А все-таки хорошо быть молодым

@Alex5 · 19.08.2015, 00:50

Сообщение от Oberok

расположены зигзагом а не на одной прямой

Можно взять несколько пикселей (граничных). Вычислить средние значения (например, методом наименьших квадратов). Проверить, что среднее отклонение не очень большое.

@kabenyuk · 20.08.2015, 07:12

Сообщение от Oberok

Получил четыре вершины многоугольника.

Либо вершины, либо точки на сторонах четырехугольника. Надо бы дополнительное исследование проводить. Лень рисовать соответствующие картинки.

@AncientPenguin · 20.08.2015, 07:44

Сообщение от Oberok

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

Пройти по всем пикселям в цикле найти минимум и максимум белых точек (по X и Y) это и будут вершины? Там же дырок не будет в квадрате. Как раз получатся 4 точки минимум по X и Y, максимум по X и Y. Так или иначе если квадрат хоть чуть повернут вершины будут в минимумах и максимумах, если не повернут то нужно по два минимума и максимума (они совпадут у пар вершин).
Хотя может я где неправ, все что успел придумать на ходу.

@Oberok 6 / 6 / 2 Регистрация: 11.03.2011 Сообщений: 40
		1
	Вершины четырехугольника по множеству принадлежащих ему точек 17.08.2015, 22:17. Показов 659. Ответов 7 Метки нет (Все метки) Доброго времени суток, подскажите пожалуйста алгоритм нахождения вершин четырехугольника по содержащимся в нем точкам. Допустим у меня есть черное изображение, содержащее четырехугольник( белые пиксели ). как по этим белым пикселям определить вершины четырехугольника? Изображение нижедля примера, на практике четырехугольники могут быть произвольной формы. За ранее спасибо. Изображения 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	18.08.2015, 15:36	2
	Другими словами. Некто нарисовал на черном экране белый четырехугольник. Наша задача найти его вершины. Так? Если так, то алгоритм может быть основан на следующем замечании. Пиксель является вершиной (многоугольника) если в достаточно малом круге с центром в этом пикселе черных и белых пикселей примерно поровну. 1

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,744
	18.08.2015, 17:49	3
	Не вижу здесь никакой связи с геометрией - это скорее "распознавание образов" что нынче довольно модно. Для начала я бы "продифференцировал" имедж, заменив каждый пиксель его разницей с соседями. Потом отсечка по амплитуде. Потом для каждого пикселя искал бы 2 соседей отличающихся на приличный угол. Ну и если угол между этими соседями достаточно далек от 180 - вот она, искомая точка (одна из 4). Думаю такого примитивного алгоритма здесь вполне достаточно - но, повторюсь, сейчас есть много теорий. 1

@Oberok 6 / 6 / 2 Регистрация: 11.03.2011 Сообщений: 40
	18.08.2015, 18:15 [ТС]	4
	Спасибо всем за ответы. Я решил по своему, я очертил минимальный квадрат в которую помещается фигура, получилось четыре вершины квадрата, затем нашел к каждой вершине квадрата, пиксель который наиболее близко к ней расположен. Получил четыре вершины многоугольника. Задача решена ! По поводу вычисления углов между пикселями то это не катит так как онт расположены зигзагом а не на одной прямой, и углы между соседними пиксялми может быть совершенно разное независимо от положения 0

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,744
	18.08.2015, 18:36	5
	Сообщение от Oberok Задача решена ! А все-таки хорошо быть молодым 0

@Alex5 1130 / 789 / 232 Регистрация: 12.04.2010 Сообщений: 2,012
	19.08.2015, 00:50	6
	Сообщение от Oberok расположены зигзагом а не на одной прямой Можно взять несколько пикселей (граничных). Вычислить средние значения (например, методом наименьших квадратов). Проверить, что среднее отклонение не очень большое. Миниатюры 0

@kabenyuk $Эксперт по математике/физике$ 4166 / 3038 / 914 Регистрация: 19.11.2012 Сообщений: 6,182
	20.08.2015, 07:12	7
	Сообщение от Oberok Получил четыре вершины многоугольника. Либо вершины, либо точки на сторонах четырехугольника. Надо бы дополнительное исследование проводить. Лень рисовать соответствующие картинки. 0

@AncientPenguin 99 / 46 / 18 Регистрация: 09.08.2015 Сообщений: 367
	20.08.2015, 07:44	8
	Сообщение от Oberok Доброго времени суток, подскажите пожалуйста алгоритм нахождения вершин четырехугольника по содержащимся в нем точкам. Допустим у меня есть черное изображение, содержащее четырехугольник( белые пиксели ). Пройти по всем пикселям в цикле найти минимум и максимум белых точек (по X и Y) это и будут вершины? Там же дырок не будет в квадрате. Как раз получатся 4 точки минимум по X и Y, максимум по X и Y. Так или иначе если квадрат хоть чуть повернут вершины будут в минимумах и максимумах, если не повернут то нужно по два минимума и максимума (они совпадут у пар вершин). Хотя может я где неправ, все что успел придумать на ходу. 0