День добрый!

Это самопересикающийся полигон.

************************
*                                            *
*                         *****         *  
*                         *      *         *
*                         *      **** **  
*    *******       *      *         *
*    *          *       *      *         *
*    *          *       *      *         *
*    *          *************** 
*    *          *       *      *         * 
*    *          *       *      *         * 
*    *******       *      *         *
*                         *****         *
*                                            *
************************

Как найти красную точку с минимум затрат?
Есть вариант, когда все ребра (от вершины 1 до вершмны 2  и т.д.) сравнивать друг с другом и тем самым находить эту точку, но получается 
0(n*n).  А это плохо! Нужно быстрее. Какие будут мысли?
 

Используй метод сканирующей линии. Он дает (кажется) O(n*log n). Быстрее, по-моему, не получится.
Метод сканирующей линии вкратце: все ребра сортируем, скажем по x, слева направо. Начальные и конечные х-координаты ребер составляют список точек-событий. Вертикальная сканирующая линия переходит от одного события к другому, слева направо. В каждый момент времени рассматриваются только те ребра, которые пересекают сканирующую линию. Причем эти ребра (называемые активными) сортируются по y-координате пересечения сканирующей линии. Так что нужно проверять пересечения только соседних в списке ребер. Хорошее и подробное описание этого алгоритма можно найти в книге Ласло "Вычислительная геометрия и компьютерная графика на С++". 
Но следует иметь в виду, что реализация алгоритма значительно сложнее, чем квадратичная проверка пересечений всех ребер, а за счет сортировок и подготовительной работы выгрыш будет только при большом числе ребер. Я думаю, от сотни. Если ребер 2 десятка, проще попарно сравнить.

Добавлено @ 09:54 
Если полигон именно такой, как на рисунке, т.е. состоит только из вертикальных и горизонтальных линий, думаю процесс можно существенно упростить и ускорить. 

Спасибо!
Просто нужно определить эту точку, которая принадлежит обоим  отрезкам (сторонам). На первый взгляд это легко, но когда копнешь глубже...
           
            A'
             *
             *
             *
             *
 A************B
             *
             * 
             *
             *
           B'

Получется куча условий и они работают по отдельности.



Это 1 / 4 от всех условий. 
Первое, это когда рассматривается отрезок (сторона) A'B' и (AB или BA)
А второе -  B'A' и (AB или BA). 
И так с каджой стороны (учитываются и то, что под любым углом пересекаются прямые).

Видимо надо от этого отказаться, или нацти альтернативу.