1 Востаннє редагувалося Адріян Ігорович (07.01.2013 21:28:45)

Тема: Перевірка на правильність виділеної області

Хм, назва теми трохи дивно звучить, та все ж.
Є значить багато багато блоків жовтого кольору розміру 10х10 px;
http://hanter.name/files/replace/%D0%B7%D0%BD%D1%96%D0%BC%D0%BE%D0%BA2.png
Насправді їх набагато більше, але не в цьому суть.
Кожен квадратик можна виділити, при виділенні, він стає чорного кольору.
Також кожен квадратик має свій числовий ідентифікатор 1,2,3,4,5...100..1000 і тд.
А задача полягає у тому, щоб перевірити чи було (відмічено|намальовано) фігуру тільки з чотирьма кутами, і тільки одну.
Тобто такий варіант нормальний:
http://hanter.name/files/replace/%D0%B7%D0%BD%D1%96%D0%BC%D0%BE%D0%BA3.png
А такий
http://hanter.name/files/replace/%D0%B7%D0%BD%D1%96%D0%BC%D0%BE%D0%BA4.png
або такий
http://hanter.name/files/replace/%D0%B7%D0%BD%D1%96%D0%BC%D0%BE%D0%BA5.png
Вже не підходять.
Можливо хтось має якісь здогади нарахунок такого алгоритму?

2

Re: Перевірка на правильність виділеної області

А квадратики яким чином занумеровані?

3 Востаннє редагувалося Patron (07.01.2013 21:59:22)

Re: Перевірка на правильність виділеної області

Я думаю що можна так, але я не перевіряв на практиці. Находимо чотири точки фігури: top-left (min x & min y), top-right (max x & min y), bottom-left (min x & max y), bottom-right (max x & max y). Якщо top-left і top-right мають одинакове значення координати y то вони на одному рівні по ігрику а також якщо top-right і bottom-right мають одинакове значення координати x то вони на одному рівні по іксу а також якщо bottom-right і bottom-left  мають одинакове значення координати x то вони на одному рівні по іксу а також якщо bottom-left і top-left мають одинакове значення координати y то вони на одному рівні по ігрику а це значить що фігура або прямокутник або квадрат.
п.с. якщо щось не зрозуміло у моїй логіці то питайте я спробую детальніше пояснити.

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }
Подякували: Адріян Ігорович1

4 Востаннє редагувалося Patron (07.01.2013 22:07:32)

Re: Перевірка на правильність виділеної області

Хоча ні це не правильний алгоритм) сорі) До алгоритму потрібно додати перевірку чи немає у фігурі незафарбованих квадратів щоб вже остаточно зрозуміти чи вона "правильна".

Щоб зрозуміти рекурсію потрібно спочатку зрозуміти рекурсію.
int fac(int n) { return n < 2 ? 1 : n*fac(n-1); }

Re: Перевірка на правильність виділеної області

Patron написав:

Хоча ні це не правильний алгоритм) сорі) До алгоритму потрібно додати перевірку чи немає у фігурі незафарбованих квадратів щоб вже остаточно зрозуміти чи вона "правильна".

Замальовані фігури не можна відмічати, тобто юзер не зможе позначити її ще раз.

6

Re: Перевірка на правильність виділеної області

Можна спробувати піти поелементно з виставлянням певних проміжних змінних-прапорців.
Скажімо, рухаємося по елементах від 1 до кінця по рядках. Якщо знайшли відмічений, запам'ятовуємо. Усі наступні мають бути відмічені, аж поки не попадемо на невідмічений, який свідчитиме про валідний кінець фігури. Запам'ятовуємо його теж. І продовжуємо пошук далі по рядку, щоб у випадку діагностування відміченого елемента крикнути "Halt!" і зупинити перевірку.
Спустившись на рядок нижче, повторюємо процедуру, і так по всій сукупності елементів, тільки далі перевірка відповідності меж фігури робиться за раніше зафіксованими елементами першого рядка.

I belong to the Dead Generation.
Подякували: Voron, Адріян Ігорович2

7

Re: Перевірка на правильність виділеної області

як на мене потрібно провести спочатку базові провірки.
1. вибираємо 4 точки
крайню ліву верхню, крайню праву верхню, крайню ліву нижню, крайню праву верхню
2. Перевіряємо їх на правило: крайні ліві точки мають бути розташовані на одній лінії по вертикалі, крайні праві теж, 2 верхні мають бути розташовані на 1ній горизонталі і дві нижні точки теж на одній горизонталі
якщо правило 2 не виконується значить фігура не підходить
3. наступним кроком ми маємо визначити чи у фігурі є пусті проміжки. Тобто це може бути прямокутник але в середині може бути пустий квадрат
беремо координати крайньої лівої верхньої точку і ідемо по лінії до того часу поки не дійдемо до крайньої правої координати
якщо один з квадратів на цій лінії  не заповнений тоді у фігурі є пробіли значить фігура не підходить
дальше перевіряємо наступну лінію і так до того часу поки не дійдемо до крайньої нижньої правої точки)
Здається такий алгоритм якщо я вас правильно зрозумів ;)

Подякували: Voron, Адріян Ігорович2

8

Re: Перевірка на правильність виділеної області

Гадаю краще використати двомірний масив для квадратиків.
Мова йде про довільний чотирикутник?

Re: Перевірка на правильність виділеної області

Voron написав:

Мова йде про довільний чотирикутник?

Так.

10

Re: Перевірка на правильність виділеної області

Гадаю можна спробувати щось таке:
Скануємо порядково зображення.
Коли вперше натикаємось на один чорний квадратик - це наша перша знайдена вершина,
якщо вперше натикаємося на чорний відрізок - маємо дві вершини (початок і кінець відрізка),
Якщо натикаємося на два окремих чорних квадратики - маємо дві вершини,
Якщо "знаходимо" більш ніж три вершини в першому ж рядку - виходимо з фунції і виводимо помилку.
Якщо все гаразд - записуємо знайдені вершини у масив вершин, запам'ятовуємо координати крайнього лівого та крайнього правого чорного квадратика у поточному рядку (якщо квадратик один - його координати запам'ятовуємо двіччі).
Переходимо на наступний рядок, визначаємо координати крайнього лівого та крайнього правого чорного квадратика у поточному рядку - запам'ятовуємо ці координати, визначаємо зміщення крайніх квадратиків відносно відповідних крайніх квадратиків у минулому рядку.
Надалі контролюємо зміщення, якщо воно змінилося - ми знайшли нову вершину, якщо ми знайшли більше ніж 4 вершини - виводимо помилку і виходимо з фунції.
Якщо після закінчення сканування, знайдено 4 вершини - значить все гаразд.

P.S. Гадаю простіше реалізувати інструмент для коректного виділення області ніж подібну перевірку.

Подякували: Адріян Ігорович1

11

Re: Перевірка на правильність виділеної області

А довільним чотирикутником в цій геометрії може бути лише прямокутник. І за умовою цей прямокутник лише один. Тому, я думаю робити так:

1. знаходимо найвищий найлівіший вибраний: (x_min, y_min).
2. Знаходимо найнижчий найправіший вибраний: (x_max, y_max).
3. Для всіх квадратиків перевіряємо умову:
    вибраний(x, y) == (x >= x_min) and (y >= y_min) and (x <= x_max) and (y <= y_max)
4. Якщо умова всюди виконалась - область правильна, інакше ні.

Подякували: Адріян Ігорович1

12

Re: Перевірка на правильність виділеної області

На скільки зрозумів, може бути і такий випадок:
http://clip2net.com/clip/m40453/thumb640/1357641911-2013-01-08-124506_427x364_scrot-4kb.png

13

Re: Перевірка на правильність виділеної області

А там не більше 20 кутівт? І той квадратик справа вгорі хіба суміжний?

14

Re: Перевірка на правильність виділеної області

Voron написав:

На скільки зрозумів, може бути і такий випадок:
http://clip2net.com/clip/m40453/thumb640/1357641911-2013-01-08-124506_427x364_scrot-4kb.png

Таке теж юзер може зробити, але воно не допускається.

15 Востаннє редагувалося Voron (08.01.2013 14:11:48)

Re: Перевірка на правильність виділеної області

На моїй світлині запікселений чотирикутник)

2 Hanter Тобто допускається лише прямокутник?
Якщо так то це простіше:
Скануємо пострічково зображення, запам'ятовуємо координату x крайніх точок першого зустрічного відрізка з чорних квадратиків, якщо у рядку більше одного відрізка - помилка.
Далі перевіряємо чи координати x крайніх точок наступних відрізків рівні x координатам першого відрізку, якщо координати не збігаються, або знайдено більш ніж два відрізки - помилка.
Відколи зустрічаємо рядок без чорних відрізків - слідкуємо щоб надалі чорних квадратиків не було, якщо є - помилка.

16 Востаннє редагувалося Voron (08.01.2013 14:44:23)

Re: Перевірка на правильність виділеної області

Власне цей алгоритм запропонував раніше Bartash.
Алгоритм від funivan теж вірний, але на мій погляд менш раціональний (потрібно пройти всі клітинки а далі ще раз пройти сам прямокутник), хоча мабуть простіший.

17 Востаннє редагувалося funivan (08.01.2013 15:17:27)

Re: Перевірка на правильність виділеної області

Взагалі алгоритми подібні можна просто звести все в правильний ланцюжок, оптимізувати можна на етапі коли юзер малює фігуру, на цьому кроці можна простою формулою оприділяти крайні точки)

Отже самий оптимальний алгоритм.
Юзерів клікнув ми записуємо кількість кліків на дошці. Тобто лічильник чорних квадратів $numberOfBlack++ (якось так)
На цьому етапі ми перераховуємо крайні точки. Тобто маємо 4 точки   якщо юзер клікнув дальше за нашу крайню точку переписуємо координати
Юзер от так поклікав і ми маємо 4 крайні точки і кількість чорних квадратів.

Валідація: 1н крок)
Відносно крайніх точок визначаємо скільки в середині є квадратів отримуємо число і порівнюємо з $numberOfBlack
Якщо рівне все ок, якщо не рівно не все ок :)

18

Re: Перевірка на правильність виділеної області

funivan написав:

Взагалі алгоритми подібні можна просто звести все в правильний ланцюжок, оптимізувати можна на етапі коли юзер малює фігуру, на цьому кроці можна простою формулою оприділяти крайні точки)

Отже самий оптимальний алгоритм.
Юзерів клікнув ми записуємо кількість кліків на дошці. Тобто лічильник чорних квадратів $numberOfBlack++ (якось так)
На цьому етапі ми перераховуємо крайні точки. Тобто маємо 4 точки   якщо юзер клікнув дальше за нашу крайню точку переписуємо координати
Юзер от так поклікав і ми маємо 4 крайні точки і кількість чорних квадратів.

Валідація: 1н крок)
Відносно крайніх точок визначаємо скільки в середині є квадратів отримуємо число і порівнюємо з $numberOfBlack
Якщо рівне все ок, якщо не рівно не все ок :)

Та, цей алгоритм буде швидким у реалізації. Тільки ще додати перевірку кліку на вже відмічених клітинках варто.

I belong to the Dead Generation.

19

Re: Перевірка на правильність виділеної області

Ще один нюанс якщо юзер знімає виділення треба брати бокові точки і перераховувати чи вони попадають під оприділення крайніх точок чи ні:) Ну взагалі реалізація реальня і не складна )

20

Re: Перевірка на правильність виділеної області

Варіант від мене. Має вхідний масив чорних точок(унікальні значення). Шукаємо крайні значення по вертикалі і горизонталі. Якщо розмір масиву не дорівнює (у1-у2)*(х1-х2), то це не прямокутник.