Комментарии 19
Начинать с бумаги и карандаша (или ручки, если вы любите рисковать) — один из лучших способов восприятия задачи, и это относится не только к созданию алгоритмов (и даже не только к программированию). Разумеется, программирование — не исключение, поэтому давайте приступим и начнём с самого начала.
Как раз программирование — исключение. Для восприятия задачи не обязательно использовать бумагу и карандаш — это дело привычки. Я приучил себя все сразу записывать в цифровом виде, если это не касается сложных рисунков, даже схемы. Хотя возможно и они не являются проблемой, если использовать хороший графический планшет и инструменты.
Бумага и карандаш обычно устраняют многие неочевидные вещи (неочевидные понимается в прямом смысле).
Поясню — глядя на чертеж вы видите сразу дефектные вершины, и, кажется, вот решение — связать дефектность с углом
Но лучше сразу обдумывать не картинку, а совокупность данных.
То есть дана совокупность точек (скажем, координатами x и y).
Наверное, она должна быть упорядочена. Последовательное соединение точек дает некую многоугольную фигуру.
Теперь, задаем вопрос, как определить какая точка дает дефектную вершину.
Думается алгоритм изменится существенным образом.
Об этом было правильно сказано выше.
2) однажды не нашёл готовый алгоритм, пришлось решать самостоятельно задачу по геометрии
3) как же я хорош, задача ведь наверняка сложная, и только моя смелость и жизненные установки помогли мне её решить!
4) мне пора учить людей тему, как решать задачи!
Напишите лучше.
Вполне себе рабочий алгоритм. Правда задачу быстрее решить по другому. Сначала построить конвекс ( это О(n) на плоскости ) для всех вершин каждого объекта и проверить пересекаются ли с конвексами других объектов а потом проверять по треугольникам
Не возражайте мне, лучше напишите комментарий к статье лучше моего. То-то же!
Универсальный метод решения задач:
1 сформулируй условия задачи
2 поищи, возможна она уже решена, если да то используй готовое решение
3 если нет готового решения включи мозг напиши минимальное решение
4 если нет решения заплати тому кто может решить
5 если нет решения брось эту задачу, попробуй вернуться к первому пункту попозже или возьми другую задачу.
Чем не универсальный метод? Первые три пункта описаны в статье
Это же статья -перевод. Не стоит воспринимать ее буквально, возможно та часть которая Вам не понравилась переведена неточно. А конкретно по поводу алгоритма — примитив конечно, но большинство типичных программистов решают большую часть времени именно такие задачи, эта ещё не самая худшая
Может оно и так, но:
1. кто считал эти %? кто делал исследования?
2. у каких программистов?
3. что такое «реальных» задач? есть и нереальные?
Эээ… Мне всегда казалось, что программист должен уметь не только уметь гуглить и стэковерфловить. И не только прочесть модную книгу по паттерна, чтобы не писать макаронный код, но и вообще-то знать алгоритмы, архитектуру программно-аппаратную, математическую логику и быть способным решать и находить способы решения задач своим умом. Ну, Кнута, например прочесть. Ну, это в моём мире, где программисты — это software engineer, где главное второе слово.
Геометрические задачи тяжело решаются на компе. Написать robust алгоритм для общего случая чаще всего очень сложно. Автор вскользь написал, что существуют сложные многоугольники (они же самопересекающиеся), но задачу начал решать для простых. А вот я бы как раз посмотрел, как бы он эту задачу с помощью бумаги и карандаша решал применительно к сложным многоугольникам. Интересующиеся могут пойти в гугл с запросом «repair complex polygon» и убедиться, что это тема для многих научных работ и диссертаций, большинство решений которых ненадежны в общем случае. И задача эта очень важная и часто встречающаяся, потому что существует и в картографическом мире, и в полигональных моделях.
Поэтому, лично мое мнение, что начинать задачу нужно в первую очередь с понимания предметной области, а уже потом брать карандаш и писать свои велосипеды.
Интуитивная разработка алгоритмов