Wataru

Для вашей задачи подойдет и квадродерево: ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%...
Поиск ближайшей точки к заданной выполняется рекурсивным перебором с отсечениями (не стоит рассматривать квадрат, если он целиком дальше, чем имеющийся промежуточный ответ).
Поиск всех точек, которые надо вывести делается так же рекурсивно.

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

Простое, но медленное решение - проверять на пересечение все пары отрезков. Это работает за квадратичную сложность от количества отрезков в контуре.
Проверка пересечения двух отрезков делается довольно просто. Можно пересечь 2 прямые, заданные параметрически (2 линейных уравнения, решение на бумажке), а потом проверить, что точка пересечения на каждой прямой внутри отрезка (можно задать параметрическое уравнение прямой так, что отрезок соответствует параметрам от 0 до 1). Другой, более быстрый способ с помощью векторного произведения. Надо проверить, что точки каждого отрезка лежат по разные стороны от прямой, на которой лежит другой отрезок.

Есть сложное, но более быстрое решение задачи - с помощью заметающей прямой. Подробно описанно вот тут: e-maxx.ru/algo/intersecting_segments
Работает за O(n log n), где n - количество отрезков. Его, правда, придется чуть-чуть подкорректировать, чтобы не учитывать пересечения соседних отрезков.

Утверждение: Рассмотрим какую-то вершину v. Допустим самый ранний момент, в который можно попасть в нее - t. Если эта вершина есть в кратчайшем пути из вершины a в вершину b, то обязательно есть путь, не длинее, в котором вершина v посещается как раз в момент t.
Такой путь можно получить конструктивно - начало взять из кратчайшего пути в v, а конец из кратчайшего пути из a в b, может придется подождать какое-то время в вершине, прежде чем продолжить путь.

С учетом этого утверждения становится понятно, что можно решать вашу задачу стандартным алгоритмом дейкстры для поиска самого быстрого пути во все вершины. Там при релаксации (пересчете минимального растояния) надо просто учитывать, в какое ближайшее к текущему веремни ребро станет доступно для прохождения.

Еще интересная игра — SpaceChem. Тут не совсем привычное программирование. Надо на плоском поле расставлять в клетках команды. Некоторый манипулятор двигается по полю, повинуясь командам и берет/отпускает атомы. Надо собирать из атомов определенные молекулы. Развивает не только алгоритмический образ мышления, но и воображение и память.