[edit: я попытался переписать свой вопрос немного, потому что кажется, что никто не понимает, чего я хочу ... и я подумал, что это сложный алгоритм только для меня :)]
Проблема, с которой я сталкиваюсь, это соединение отдельных полигонов. Каждый представляет собой 4-х точечный многоугольник. Окончательный результат - это слияние / объединение двух полигонов.
На следующем рисунке показана одна версия возможного результата (результаты могут отличаться, потому что эта часть с черным заполнением может отличаться для каждого результата).
Я начинаю с чего-то вроде:
Polygon one = [A,B,C,D]; // (A/B/C/D) might look like : new Point {x = 10, y = 15}
Polygon two = [E,F,G,H];
И мне нужен алгоритм для вычисления объединения этих двух множеств, поэтому я получу результат, подобный:
Polygon total = [I,J,K,L,M,N]; // = new points
Мне не нужно визуализировать это (даже когда я это делаю ..), мне просто нужен набор точек, определяющих новый многоугольник (объединение этих двух), потому что мой конечный результат будет центроид этого объединенного многоугольника.
У меня уже есть алгоритм для расчета центроида на основе набора точек ввода. Но сначала мне нужно набрать правильные очки.
До сих пор я нашел упоминания об алгоритме выпуклой оболочки, но я боюсь, что он сгенерирует следующий многоугольник (что неверно):
EDIT:
Так по-другому, как посмотреть на эту проблему:
У меня есть программа, которая умеет работать с объектами, которые представлены 4 баллами. Каждая точка имеет два атрибута (координата x, координата y).
Тогда программа умеет рисовать линии между этими точками. Эти линии будут выглядеть как квадрат, прямоугольник или многоугольник ... этот результат зависит от заданных координат, но я знаю, что я всегда буду использовать точки, которые будут генерировать многоугольники. Как только точки соединены, программа может заполнить эту соединенную область. После того, как это нарисовано, вы можете увидеть следующее изображение:
http://i51.tinypic.com/28037ee.png
НО: программа не знает, что он только что сделал многоугольник. Он только знает, что получил от меня 4 очка, он их связал и наполнил.
Тогда у меня есть второй объект (= многоугольник), который определяется другим набором точек (разные координаты). Программа снова не знает, что он создает заполненный многоугольник ... он просто сделал несколько операций с 4 заданными точками. Результатом в этом случае является еще один многоугольник:
http://i53.tinypic.com/qnog9w.png
Теперь мы просто рисуем два многоугольника на дисплее ... и мы дали им такие координаты, что они перекрывают друг друга. Результат выглядит так (учитывая только заполненную область):
Моя программа просто рисует два полигона. Хорошо. Вы можете видеть на своем экране только один многоугольник (потому что есть два перекрывающихся = они похожи на один кусок) и Мне нужно посчитать центроид этого ОДНОГО кусочка .
У меня уже есть алгоритм, который будет принимать набор точек (представляющих точки, образующие многоугольник) и считать центроид из этих точек. Но я не могу сейчас использовать алгоритм, потому что не могу дать ему необходимые очки, потому что я их не знаю.
Вот пункты, которые я хочу получить в результате:
http://i51.tinypic.com/1z19vtj.png
Таким образом, мой алгоритм должен начинаться с точек A, B, C, D, E, F, G, H, и в результате он должен давать мне точки I, J, K, L, M, N.
Резюме: мне нужно посчитать центроид многоугольника, который является результатом объединения / слияния двух отдельных многоугольников, которые перекрываются.
И я подумал, что union of two polygons будет достаточно, чтобы объяснить:)