Разделение выпуклой оболочки на две отдельные части

Я пытаюсь решить довольно сложную для меня проблему. Я не новичок в программировании, но я действительно не знаю, как понять эту проблему. Ему задан набор точек (точка []) с координатами Xi и Yi в качестве входных данных. Программа должна выводить длину окружности выпуклой оболочки многоугольника, но при необходимости может разделить эту оболочку на две части, на две отдельные выпуклые оболочки, каждая из которых будет содержать некоторое количество точек. Целью этого деления является получение более короткой окружности (если сумма окружностей этих двух корпусов короче окружности одного корпуса, например: два кластера точек далеко друг от друга). Проблема также в том, что не может быть больше двух корпусов. Буду признателен за любые идеи.

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

ДОБАВИТЬ: На самом деле, под «окружностью» я подразумеваю периметр.

Вот ключевая часть моего кода:

m.x = (a.x + b.x)/2;
    m.y = (a.y + b.y)/2;

    ab.first = b.x - a.x;
    ab.second = b.y - a.y;

    for (i=0; i<n; ++i)
    {
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 > 0)
            left[l++]=p[i];
        else if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 < 0)
            right[r++]=p[i];
        if (p[i].x * ab.first + p[i].y * ab.second - (SQ(ab.second) + SQ(ab.first))/2 == 0)
            mid[md++]=p[i];
    }

algorithm geometry polygon convex
person Community    schedule 31.10.2013    source источник
comment
должен вывести минимальную окружность выпуклой оболочки многоугольника. Для чего бы это ни стоило, выпуклая оболочка уникальна (т. Е. Есть только одна), поэтому я не уверен, какой минимум вы хотите взять.   -  person Dennis Meng    schedule 01.11.2013
comment
Да, извините за неясность. Программа должна вывести длину окружности выпуклой оболочки, вот и все. Но если можно создать две выпуклые оболочки и длина окружности каждой из них короче окружности одной, она выводит сумму этих оболочек.   -  person    schedule 01.11.2013
comment
Звучит разумно. Не возражаете ли вы отредактировать вопрос, чтобы сделать этот момент более ясным?   -  person Dennis Meng    schedule 01.11.2013
comment
Я думаю, вы хотели использовать hull1 + hull2 < big hull?   -  person sdasdadas    schedule 01.11.2013
comment
Кроме того, я не думаю, что можно найти такое деление, чтобы периметр двух корпусов был меньше, чем у большого. Вероятно, это математически доказуемо в нескольких строках.   -  person sdasdadas    schedule 01.11.2013
comment
@sdasdadas - как насчет <===>, который можно разделить на < и >? это говорит о том, что может сработать разрыв двух самых больших несмежных ребер.   -  person andrew cooke    schedule 01.11.2013
comment
Я отредактировал вопрос и добавил простое изображение. Спасибо, парни.   -  person    schedule 01.11.2013
comment
@Clu: Итак, что нужно для решения проблемы? Вы работаете с точками или с полигонами? Из чего вы строите выпуклую оболочку? Из того, что вы написали выше, ничего не понятно. В одной части как бы говорится, что вы строите выпуклую оболочку для многоугольника(ов), в другой - для точек. Изначально вы говорите, что вам дан многоугольник. Означает ли это, что вам разрешено разрезать этот многоугольник на части, чтобы построить новую выпуклую оболочку?   -  person AnT    schedule 10.11.2013
comment
Входные данные представляют собой набор точек, поэтому сначала вам нужно построить выпуклую оболочку. Я опубликую свой исходный код, чтобы сделать его более понятным, потому что я действительно не знаю, как действовать дальше.   -  person    schedule 10.11.2013
comment
@Clu: Во-первых, ваш вопрос начинается с Ему задан многоугольник (точка []) с координатами Xi и Yi в качестве входных данных. Программа должна вывести длину окружности выпуклой оболочки многоугольника.... О каком полигоне вы говорите? Каково значение этого многоугольника? Во-вторых, если вам просто дан набор разбросанных точек, то важный вопрос заключается в том, сколько выпуклых нулей вы можете сгенерировать? Два? Три? Сколько хочешь?   -  person AnT    schedule 10.11.2013
comment
Там написано, что не может быть больше двух корпусов. Я имею в виду, что вам нужно построить выпуклую оболочку из заданного набора точек. Но если было бы более эффективно/выгодно построить два корпуса, вы должны это сделать. И все это из-за окружности, которая должна быть максимально короткой. Я думаю, что ответ там правильный, но я не очень хорошо знаю С++, чтобы продолжить. Я закончил тем, что нашел диаметр выпуклого корпуса с вращающимися штангенциркулем.   -  person    schedule 10.11.2013
comment
Вы можете создать две выпуклые оболочки, если это выгодно, не более того.   -  person    schedule 10.11.2013

Ответы (2)


arrow_upward
4
arrow_downward

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

construct convex hull
find the farthest pair of points (A, B) in hull with rotating calipers
divide all the points with middle perpendicular to AB segment
find hulls of resulted clouds and calculate profit or loss

введите здесь описание изображения

Добавлено: поиск самой дальней пары точек с вращающейся ссылкой измерителя

Добавлено 2: Как разделить облако точек средним перпендикуляром:

Средняя точка: M = (A + B)/2
(M.X = (A.X + B.X)/2, M.Y = (A.Y + B.Y)/2)

Вектор AB: (B.X-A.X, B.Y-A.Y)

Средняя перпендикулярная линия имеет общее уравнение:

(y-M.Y) / AB.X = - (x-M.X) / AB.Y
(y-M.Y) * AB.Y + (x-M.X) * AB.X = 0
//incorrect  x * AB.X + y * AB.Y - (AB.Y^2 + AB.X^2)/2 = 0
x * AB.X + y * AB.Y - (B.Y^2 - A.Y^2 + B.X^2 - A.X^2)/2 = 0

Когда вы используете P[i].X и P[i].Y для каждой точки вместо x и y в последнем уравнении, вы получите положительное значение для точек слева и отрицательное значение для точек справа от линии (и нулевое значение для точек на линии)

person MBo    schedule 01.11.2013
comment
Вау, это похоже на то, что я искал. Я отредактировал вопрос, чтобы сделать его более понятным. Корпусов может быть максимум два. Но хорошо, я не уверен, правильно ли я понял. Мне нужно найти дальнюю пару точек A и B, хорошо. Затем я начинаю создавать корпуса вокруг этих точек? Я не уверен, что такое вращающиеся штангенциркули и как разделить точки. - person ; 01.11.2013
comment
@user2943215 user2943215 Нет, вы начинаете создавать одну оболочку для точек слева от разделительной линии и другую оболочку для точек справа от этой линии. - person MBo; 01.11.2013
comment
Привет, я только что вернулся к этой проблеме, потому что у меня не было много времени в последние дни. Теперь я построил выпуклую оболочку и вычислил длину окружности. На самом деле я собираюсь вычислить диаметр, но не могли бы вы дать мне некоторое представление о том, как разделить точки средним перпендикуляром (я не знаю, имеет ли это значение или нет, но я программирую на С++)? - person ; 07.11.2013
comment
У меня есть еще один вопрос. При расчете средней точки M = (A + B)/2 вектор AB (B.X-A.X, B.Y-A.Y) (A + B)/2 умножается на вектор (B.X-A.X, B.Y-A.Y) ? Извините, я не очень разбираюсь в векторах, недавно программировал только на C. - person ; 09.11.2013
comment
Нет, не умножается. Просто ссылка. - person MBo; 10.11.2013
comment
Чувак, я понимаю твое предложение и думаю, что твой ответ правильный. Но я не настолько силен в C++, поэтому не знаю, как реализовать вращающиеся штангенциркули и как правильно использовать векторы. Если бы вы могли просто сделать это и разместить это здесь, я был бы так счастлив. Я загрузил то, что я закодировал до сих пор. - person ; 10.11.2013
comment
Извините, я недостаточно хорошо знаю C++ и не реализовал повернутые суппорты. Но предполагаю, что где-то в инете есть реализации - person MBo; 11.11.2013
comment
Я успешно реализовал вращающиеся суппорты. Теперь я думаю, что это последнее, что мне нужно знать. При вычислении средней точки M, как я могу получить сумму двух точек, если эти точки имеют значения X и Y? Вы не упомянули об этом в своем посте. Должна ли она быть M = (A.x - B.x)+ (A.y - B.y)/2? Извините, если я что-то не так понимаю. Кроме того, что означают эти две строки о последнем уравнении? Спасибо. - person ; 14.11.2013
comment
Добавлено описание М. Две последние строки о методе разделения точек на две части. - person MBo; 14.11.2013
comment
Я чертовски тупой :D Я написал это на доске и сразу понял, но на экране это было не так ясно. Извините еще раз за беспокойство. - person ; 14.11.2013
comment
Последний вопрос, обещаю! Почему это должен быть вектор AB, а не просто точка M? Почему это важно ? - person ; 14.11.2013
comment
Кроме того, если я использую только последнее уравнение, почему для меня важна средняя точка, если ее там нет? - person ; 15.11.2013
comment
Я загрузил свою реализацию деления точек. Кажется, это не работает для меня. Не могли бы вы взглянуть? - person ; 15.11.2013

arrow_upward
1
arrow_downward

Я согласен с MBo в том, что хитрость заключается в том, чтобы найти большое расстояние, в пределах которого можно разрезать два корпуса. Но я не согласен с тем, что вращающиеся суппорты - правильный подход. Вас волнуют не внешние измерения, а внутренние. Если у вас есть очень широкий набор точек, которые организованы в две параллельные горизонтальные линии, вы хотите разрезать между двумя линиями, а не посередине каждой.

По сути, я думаю, вы хотите найти «толстую» разделяющую линию, которая разрезает набор точек на две части и которая максимально удалена от точек с обеих сторон. Это известно как «самая дальняя проблема гиперплоскости» и обычно используется для неконтролируемого варианта алгоритма машины опорных векторов.

Это сложная (NP-сложная) задача, но существуют алгоритмы аппроксимации. Основная идея состоит в том, чтобы взять много потенциальных углов для линии и выяснить, где провести линию с этим углом, чтобы максимизировать ее разделение.

person Sneftel    schedule 15.11.2013