[Разминка для ума] Отсечение отреза брезенхема.

Посты с пометкой с тегом [Разминка для ума] содержат простые задачи на программирование, решение которых не тривиально.

Дано:
Отрезок, аппроксимированный алгоритмом Брезенхема на двумерной дискретной плоскости. Иными словами - последовательность пикселов изображения, аппроксимирующих отрезок прямой.
У отрезка есть начальные координаты int X, Y; и конечные int X_last, Y_last.
Для простоты будем считать, что 0=Y=X, Y < Y_last, X < X_last и Y_last < X_last. Т.е все безобразие происходит в нижней восьмушке первого квадранта и дальнейшие выкладки сильно упрощены.
Дабы не было недопонимания - я пользую метод Брезенхема в котором:
на 0ой итерации

 di = 2*Y_last - X_last;

на каждой следующей итерации

 if(di >= 0){
  di -= 2*X_last;
  Y += 1;
 }
 X += 1;
 di += 2*Y_last;

Задача1:
Для любого X <= int X` <= X_last найти соответствующий ему Y` и di.

Задача2:
Для любого Y <= int Y` <= Y_last найти соответствующий ему наименьший X` и di.

Условие - не использовать итеративный метод. Т.е. цикл Брезенхема от начала до точки X` (Y`) не считается (слишком дорого). Нужно решение фиксированной сложности.

В чем подвох: Т.к. di может быть и положительным и отрицательным и принимать достаточно большие значения как "туда" так и "обратно" не совсем понятно что надо делить и как потом "подправлять".

У меня на первую головоломку ушло чуть меньше 2х дней. Решение простое, но не тривиальное. Вторую буду решать завтра. Надеюсь, что решение будет аналогичным.

Что такое хорошо и что такое плохо.

Что такое хорошо и что такое плохо.

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

Однако, давно известно, что то, что хорошо себя показала в частных, мелких случаях, как правило, не работает в масштабных проектах. Наглядно мне эту мысль продемонстрировал в университете преподаватель теории игр. Звучит она приблизительно так:

Возьмем человеческого младенца, вот он лежит на спине, машет руками и ногами, его скорость перемещения равна нулю. Спустя какое-то время, он научиться переворачиваться и ползать на четвереньках, его скорость перемещения станет отличной от нуля. Затем, он подрастет, встанет на ноги и научиться ходить. Скорость перемещения значительно вырастит. Далее, с возрастом, он научиться бегать. Потом, если его хорошо тренировать и правильно кормить, он будет бегать очень быстро, может даже поставит мировой рекорд. Однако, как бы мы ни старались, как бы ни тренировали и ни кормили, этот человек не сможет преодолеть звуковой барьер и достичь космической скорости! Для решения этих задач нужны принципиально другие методы. Нужна работа многих инженеров и проектировщиков, создающих летательные и космические аппараты, нужна целая промышленная индустрия, со множеством заводов, чтобы эти аппараты создать, нужно целое государство, чтобы это все профинансировать, нужна слаженная работа огромного количества людей для того, чтобы этот человек смог таки преодолеть эти рубежи.

Так-же и в области высоких технологий. Для решения задач, отличных по сложности от студенческой курсовой, нужны совершенно другие методы работы.

В чем-же разница?

Чтобы понять, чего же мы упустили, посмотрим на примеры тех, кто давно занимается подобными вещами, но в других областях.

Например — строители: Сначала дизайнер продумывает основную идею. Затем, архитектор создаст проект. После чего, инженеры рассчитают все необходимые нагрузки, допуски, коэффициенты, свойства материалов. Потом, управленцы заключат все необходимые договора о поставках и услугах и утвердят подробный график строительства. И на конец, произойдет собственно стройка. Все предварительные этапы могут длиться годами. Планы могут меняться, переписываться, переутверждаться... На это не надо много сил и денег, т.к. этим всем занимается небольшое количество людей, а результат их труда хранится на бумаге, а не закатан в бетон. Последний этап — результат проведенной колоссальной работы. За считанные месяцы, как грибы после дождя, вырастают небоскребы. Сценарий стройки разыгрывается как по нотам. Не без ошибок, конечно, но в пределах погрешностей. Посмотрим теперь, как строится шалаш. Собирается подручный материал и используется в строительстве по мере необходимости. Как по вашему, что лучше приспособлено для жилья?

Аналогичная ситуация в кинематографе. Собственно съемкам предшествует длительная предварительная работа со сценарием, графикам, договорами, резервированием... Съемки — это небольшой, но самый дорогой, эпизод в процессе создания фильма. В противовес можно привести сказку, которую рассказывают на ночь ребенку...

Художник, перед созданием картины, делает множество зарисовок, продумывает композицию, идею и цветовое решение. Нанесение красок — это финишная прямая. Школьник берет краски и садится рисовать чего-нибудь...

Можно продолжать очень долго.

В данной работе я постараюсь пройти от идеи до продукта используя по пути больших индустрий.

Вот так, приблизительно, будет выглядеть процесс создания программного продукта:

1. Описание идеи. Ответ на вопросы «Что мы делаем кому?»
   На этом этапе требуется 2 — 3 человека, способных генерировать идеи. Их задача найти потребность, которую нужно удовлетворить. Не менее 2х для того, чтобы они могли спорить друг с другом. Не более 5ти, чтобы они не начали друг-другу мешать и слишком много спорить.


2. Проектирование модели использования продукта. Ответ на вопрос «Почему мы это делаем именно так?»
   Тут требуется максимум человек 5. Основная задача — моделирование использования будущего продукта. Нахождение «тонкостей» и «моментов», на которых следует сконцентрировать внимание и силы.


3. Проектирование структуры продукта. Ответ на вопрос «Зачем нам нужны все эти компоненты и связи?»
   Тоже не более 5ти человек, лишние будут только мешать. Основная задача — структура будущего продукта, описывающая все его модули и интерфейсы между ними. Эта структура обязана быть следствием шага 2 и «ложиться» на модели использования.


4. Разработка спецификаций модулей продукта. Ответ на вопрос «Как мы создадим эти модули?»
   Детальная разработка модулей. Проектирование структуры исходного кода. Утверждение соглашений по различным конвенциям, стилям, используемым инструментам и решениям, сборкам и тестированию и проч. Создание расписания предстоящих работ по программированию. Количество человек может быть несколько больше, чем на предыдущих шагах.


5. Написание кода.
   Тут можно и нужно использовать столько человек, сколько вы можете себе позволить. Основное правило — все они обязаны неукоснительно следовать спецификациям предыдущего шага.


6. Выпуск и сопровождение

Количество человек зависит от размера продукта и количества потребителей.

Особенно хочу обратить внимание на то, что было-бы замечательно, если бы на шагах 1+2 и 3+4, а так-же и 5+6 были бы совершенно разные люди.

К сожалению, в данный момент, кроме меня этим продуктом никто не занимается, а потому возможны некоторые авторитарные решения и отвлечения от поставленных целей.

Начало.

О себе.

По некоторым соображениям я не буду называть своих личных данных. Просто постараюсь описать свой путь до сегодняшнего момента.
Родился и живу, учился и работаю в одном из городов-миллионников страны Россия (не в столице, чему сильно рад). Со школьной скамьи я увлекся компьютерами и это увлечение определило мою дальнейшую жизнь. После школы поступил в местный ВУЗ, с громким именем, на «программистский» факультет, где закончил магистратуру. Еще будучи студентом устроился в небольшую программистскую фирму, оутсорсившую проекты у крупной транснациональной (Американской) корпорации. Со временем эта корпорация выкупила местную фирму и превратила в свой филиал. Таким образом я уже несколько лет работаю на самом пике индустрии высоких технологий в области программного обеспечения.
По соображениям «конфиденциальности» я не буду распространяться на темы «где» и «что». Скажу только, что бардак программистских проектов, разрабатываемых в стенах супер-пупер корпораций мне знаком изнутри.

О блоге.

Насмотревшись и наработавшись с тем, как оно есть, очень захотелось хоть кому-то рассказать, как оно должно быть на самом деле. Особенно сильно на это желание оказали влияния такие хорошие книги, как «Программист прагматик» (Эндрю Хант), «Дедлайн. Роман об управлении проектами» (Том Демарко), «Человеческий Фактор» (Том Демарко) и «Психбольница в руках пациентов» (Алан Купер). Очень советую их почитать. Последнюю обязательно, даже если вы не программист.
Сначала я хотел писать сюда заметки вида «вот как делают обычно, а на самом деле нада делать вот-так». Но столкнулся с такой проблемой: у меня нету уверенности в том, что мною самим не опробовано то, что я считаю «правильным». Т.е. это будут рассуждения об устройстве утопического мира, а не советы практика.
После некоторых рассуждение я решил выбрать формат новостной ленты, детально описывающий процесс создания реального программного продукта. Этот формат не отменяет полностью различные лирические отступления о том, «что такое хорошо и что такое плохо», а наоборот — становиться их обоснованием и практическим подкреплением.

О продукте.

На данный момент у меня есть идея создать электронный ежедневник, воплощающий такую штуку, как «Успеватель Василия Кислого». Однако, я не думаю ограничиваться только этим продуктом. Возможно, в будущем, линейка расшириться и другими творениями. У меня уже есть задумки, но пока тссс. Я никому ничего не обещал ;)
В виду того, что я фанат открытых технологий, результат моего труда будет доступен любому желающему под лицензией GPL и на платформе Linux. Скорее всего, под Винду я его тоже портирую, но тут, если повезет с успехом, уже буду продавать за деньги. Соображения простые: вы нашли много денег на покупку Винды — найдите немного и на мой успеватель. Однако не будем раскатывать губу и мечтать о журавлях в небе. Посмотрим внимательно на синицу в руках и подумаем, что и как с нею делать.