Андрей

вот результат обработки верхней половинки по алгоритму:
1) black&white
2) threshold
3) gauss by 1-pixel
Если какой-то из этих шагов вызывает у Вас сложность - пишите ...

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

Если кроме маркера-круга есть крупные темные области (крупнее маркера) - а размер маркера фиксирован, придумайте функцию, которая штрафует за светлые пиксели внутри круга радиуса равного маркеру и за темные пиксели вне этого круга.

В-общем, осознайте/уточните допущения и просто разработайте штрафную функцию. Если она окажется работоспособной, но медленной - возникнет второй вопрос - ее оптимизации (возможно с некоторыми потерями в качестве распознавания).

stackoverflow.com/questions/10349622/extract-thumb...

краткое описание Вашей "некоей памяти" (thumbnail) - в ответе, помеченном как решение

• аддитивный шум по заданному закону распределения (в т.ч. возможно зависящему от соседних пикселей)
  
• мультипликативный шум по заданному закону распределения (в т.ч. возможно зависящему от соседних пикселей)
  
• перестановка пикселей в заданной области по определенному закону
  
• геометрические искажения (как с вычислениями,так и исключительно за счет перестановок)
  
• перевод двумерных областей в частотную область, применение изменений в ней (аддитивные, мультипликативные шумы - частный случай фильтрация ВЧ, НЧ, полосовая), возвращение в обычное пространство
  

+ последовательное объединение перечисленных выше алгоритмов

В случае выпуклого многоугольника (кстати, многогранник - это термин "из 3D") никакие две соседние вершины вписанного прямоугольника не могут одновременно НЕ принадлежать периметру многоугольника (поскольку в противном случае мы имеем возможность расширять прямоугольник в сторону этих двух вершин, получая большую итоговую площадь).

Таким образом необходимо рассмотреть два случая -
1) касаются периметра многоугольника верхний-левый + правый-нижний углы прямоугольника
2) касаются периметра многоугольника верхний-правый + левый-нижний углы прямоугольника.

Возможно, Вам хватит быстродействия 2*O(N^2) (дважды полный перебор диагональных вершин вдоль периметра многоугольника) ?

По второму вопросу - можно ввести следующие функции :

А) ( (отношение модуля разности диагоналей к их сумме) + (отношение модуля разности одной пары противоположных сторон к их сумме)/2 + (отношение модуля разности пары других противоположных сторон к их сумме)/2 )

Для прямоугольника = "0"
Для параллелограммов нарастает компонента 1
Для трапеций нарастают компоненты 2 и/или 3

Б) Сумму модулей отклонений всех четырех углов от 90 градусов