Здравствуйте, RolandD, Вы писали:

RD>Как проверить, что полигон не имеет самопересечений?

Самое простое --- цикл по всем отрезкам и искать их пересечения.
Сложность, соответственно, квадратичная.

Можно усовершенствовать, если использовать sweep-line --- лучше
всего искать описание именно по этим словам (ну или же line segment intersection).
На русском, кажется, есть описание у Препараты-Шаймоса, талмуд называется
"Вычислительная геометрия" и (возможно!) Кормен-Лейзерсон. Сложность
при таком алгоритме --- что-то около O(n log n), ну примерно так.

Если отрезки малы, можно обойтись еще меньшей кровью: достаточно проверять
только те отрезки, расстояние от которых до заданного меньше 2*d, d -- длина.
Тогда сложность будет определяться, в основном, сортировкой. Те имеем
примерно O(n log n).

Короче, давно я такими вещами занимался