Нарисуйте контур объединенных прямоугольников на холсте

Есть ли хороший алгоритмический способ объединить несколько квадратов (каждый имеет четыре точки x / y), чтобы нарисовать контур объединенного рисунка на холсте?

Цифры, на которых я бы хотел убедиться, следующие:

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

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

Спасибо!

Обновление: причина, по которой мы хотим это сделать, заключается в том, что мы хотим показать квадраты из одной группы, которые расположены рядом друг с другом в массиве 2xn (но в некоторых случаях также может быть 1xn). . Может быть, есть более простой ответ, если я просто перебираю разные квадраты и сформирую группы как-то иначе?


javascript canvas html5-canvas draw convex-hull
person Chris Butler    schedule 26.02.2012    source источник
comment
Любые языковые предпочтения?   -  person GambitGeoff    schedule 26.02.2012
comment
Поскольку в браузере используется холст HTML, я думал о JavaScript с jQuery или Underscore.js для утилит.   -  person Chris Butler    schedule 26.02.2012
comment
возможный дубликат многоугольника, охватывающего набор точек   -  person Steve    schedule 27.02.2012

Ответы (2)


arrow_upward
1
arrow_downward

Вы смотрите на это с точки зрения «у меня есть квадраты».

Но нужно смотреть на это с точки зрения «у меня есть очки» (каждый квадрат всего 4 точки).

То, что вы на самом деле ищете, называется «Выпуклая оболочка», и вопрос уже был дан ответ на SO здесь:

Многоугольник, охватывающий набор точек

Я фактически начал рисовать ваше решение, чтобы приступить к его решению - и тогда это пришло мне в голову.

Когда я делал свои диаграммы, я понял, что контур этих фигур имеет несколько интересных свойств - и тогда я подумал: «Да, верно - кто-то уже сделал это - это уже должно быть».

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

И нашел другого С.О. вопрос.

Хотя у вас есть два, казалось бы, несовместимых требования:

два квадрата, диагональные, как прямоугольник, с треугольниками на каждом конце под углом 45 градусов - это, вероятно, самый необычный / особый случай ... три или четыре квадрата, соединенных в выпуклую форму, как L-образная фигура Тетриса (TM)

В первом примере выше вы говорите, что вам нужна «выпуклая оболочка».

Но во втором примере выше (части тетриса) вам понадобится «Вогнутый корпус».

Удачи.

Вот мои схемы:

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

person Steve    schedule 26.02.2012

arrow_upward
0
arrow_downward

Мне любопытно, зачем тебе это нужно.

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

Прочтите этот вопрос и посмотрите если это то что ты хочешь.

Изменить: также этот вопрос на gis.stackexchange.com

person Zecc    schedule 26.02.2012
comment
Кроме того, чтобы ответить на ваш вопрос, почему: мы хотим показать квадраты, принадлежащие к одной группе, которые расположены рядом друг с другом в массиве 2xn. Может быть, есть более простой ответ, если я просто перебираю разные квадраты и сформирую группы как-то иначе? - person Chris Butler; 28.02.2012