Пересечение отрезка и многоугольника

[bzubzni]

Здравствуйте! Помогите пожалуйста с алгоритмом, надо на CLIPSе написать. Но я даже не знаю, как именно находить это положение между фигурами.

В трёхмерных координатах заданы прямая (двумя точками) и некоторый замкну-тый пространственный контур (множеством точек, соединённых отрезками, перечислен-ных в определённом порядке обхода). Написать функцию, определяющую положение прямой относительно контура (проходит внутри контура, пересекает контур или лежит вне контура).

[onewho]

мне в голову приходит только проверять все точки прямой - принадлежат ли они многоугольнику ??
соотв-но 3 варианта - все, ни одной, часть.

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

[bzubzni]

вот как можно найти положение прямой и плоскости? и как многоугольник представить в виде плоскости?(

[Rin]

Попробуйте спросить на этом форуме. Публикуйте в "Помогите решить/разобраться"

[onewho]

прямая задается по 2-м точкам, плоскость по 3-м

[s-andriano]

Не совсем понятно, что такое контур.
Если все его точки лежат в одной плоскости, то нужно найти точку пересечения прямой и плоскости, проверить, что она лежит внутри отрезка и только в этом случае, выяснять, находится ли точка внутри многоугольника.

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

Это в качестве предположения - нужно проверять.

[bzubzni]

а я и не подумала, что это может быть просто контур, а не плоскость....
но алгоритм мне не совсем понятен(
что тогда будет значить пересечение отрезка и контура? отрезок пересекает одно из ребер?

[s-andriano]

Насколько я себе представляю, пересечение многоугольника и прямой - это примерно следующее: пусть многоугольник - веревка или цепь, завязанные в кольцо. Если мы потянем за эту веревку и она соскользнет с "прямой" - пересечения нет, а если "зацепится" - есть.
А вот в случае отрезка...
Если перпендикуляры, опущенные из каждой точки многоугольника на прямую, все лежат в пределах отрезка - результат сравнения такой же, как и для прямой. Если все вне - пересечения нет. Если часть в пределах отрезка, а часть - вне, случай сложнее.
Кстати, перпендикуляры, думаю, не обязательны. Достаточно, чтобы существовало две параллельные плоскости такие, чтобы все точки многоугольника лежали между ними, а сами плоскости пересекали прямую обе либо в пределах отрезка, либо за его пределами по одну сторону от отрезка.

[bzubzni]

а что если обнулить одну из трех координат и получить проекцию на плоскости? я не наверно работать легче

[s-andriano]

ну хорошо, если проекция прямой пройдет в стороне от проекции многоугольника, а если в проекции прямая будет пересекать многоугольник - что тогда?

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