Имеется многоугольник с "дырками" и 2 точки внутри него.
Как построить ломаную наименьшей длины, соединяющую эти точки?
Желательно бы в исходнике или в мат. форме.

Методом извлечения оптимального пути в графе. А на чем тебе сырец надо, на Паскале или на Си?

Лучше тогда на Паскале... Только причем здесь граф?

$tatic А что значит с "дырками" ???

Так, тогда расскажи как ты решаешь задачи с путями в фигурах?

Сначала пробуем дотянуться напрямую. Если не вышло, тянемся к ближайшей "Дырке". От неё к точке пробуем, итд...

Ищется путь в графе дейкстрой. Вершины - эти две точки плюс вершины многоугольника (включая вершины дыр). Дуги - все отрезки, соединяющие пары вершин, которые (отрезки) при этои остаются внутри многоугольника. Длина дуги - её эвклидова длина (или какая там мера используется).

Метод определение того, что отрезок остаётся внутри многоугольника.

Термины:
1) Отрезок - отрезок, который мы проверяем (дуга графа)
2) Сегмент - отрезок, соединяющий две подряд идущие вершины многоугольника/дырки.
3) Внутренность отрезка/сегмента - все точки кроме концов. Т.е. (a;b) в интервальной нотаци ([a;b] - весь отрезок целиком в этой нотации).
4) ДА - отрезок лежит целиком внутри прямоугольника.
5) НЕТ - отрезок не лежит целиком вутри прямоугольника.

Критерий:
1) Если отрезок пересекает своей внутренностью внутренность какого-то сегмента, то НЕТ.

2) Если внутренность отрезка содержит концевую вершину какого-то сегмента, то надо идти от этой вершины вдоль многоугольника/дырки в обе стороны, пока каждый из обходов не наткется на вершину, не принадлежащую внутренности отрезка (вершина всё ещё может оставаться на прямой отрезка, но при этом не принадлежать его внутренности). Если эти вершины лежат строго по разные стороны прямой отрезка (т.е. произведение ориентированных расстояний строго отрицательно), то НЕТ.

Если по всем сегментам ни разу не сработало НЕТ, то ДА.

(В п.2. обход может зациклиться, если отрезок параллелен плоской дырке/многоугольнику (это допустимо?). В этом случае ответа НЕТ по данному сегменту _не_выдается_).

Это сообщение отредактировал(а) Harkonnen - 12.7.2005, 14:48

Спасибо, Harkonnen. Это как раз то что нужно.