Начертайте контур на комбинирани правоъгълници в платно

Има ли добър алгоритмичен начин за комбиниране на множество квадрати (всеки има четири x/y точки), за да начертаете контур на съединената фигура в платно?

Цифрите, които бих искал да се уверя, че работят, са следните:

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

Има ли лесен начин за изчисляване на външните точки, които да се използват за начертаване на линия (и може би запълнена фигура) от всички точки на квадратите?

Благодаря!

Актуализация: причината, поради която искаме да направим това, е, че искаме да покажем квадрати, които са от една и съща група, които са един до друг конкретно в масив 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 тук:

Многоъгълник, обхващащ набор от точки

Всъщност започнах да чертая вашето решение, за да го реша - и тогава това ми хрумна.

Когато правех диаграмите си, разбрах, че очертанията на тези фигури имат няколко интересни свойства - тогава си помислих "да, точно така - някой вече е направил това - това трябва вече да е наоколо".

Така че аз потърсих в Google „конструиране на най-малкия многоъгълник, обхващащ други многоъгълници“

И намери другия S.O. въпрос.

Въпреки че имате две на пръв поглед различни изисквания:

два квадрата, които са диагонални като правоъгълник с триъгълници във всеки край на 45 градуса - това е може би най-неправилният/специален случай... три или четири квадрата, съединени, за да направят изпъкнала форма като Tetris(TM) парче 'L' парче

В първия пример по-горе казвате, че искате „Изпъкнал корпус“.

Но във втория пример по-горе (частите от тетрис), ще ви трябва "Вдлъбнат корпус".

Късмет.

Ето моите диаграми:

въведете описание на изображението туквъведете описание на изображението тук въведете описание на изображението туквъведете описание на изображението тук

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