Выталкивание точки из бокса.

← →
@!!ex_ (2007-06-22 18:11) [0]

Есть точка. Известно, что она внутри бокса.
Вопрос, как найти направление и расстояние на которое нужно переместить точку, чтобы точка оказалась вне бокса и при этом, чтобы это расстояние было минимальным.

← →
Desdechado © (2007-06-22 18:13) [1]

Бокс какую форму имеет? Пространственных измерений сколько?

← →
antonn © (2007-06-22 18:14) [2]

скорее всего паралеллепипед

← →
TUser © (2007-06-22 18:14) [3]

Бокс - многоугольник? Тогда перебрать все расстояния до сторон. Пофиксить по поводу вершин. Внутри или снаружи, - это уже не важно, между ними нет разницы.

Или многогранник? Тогда до граней.

← →
Desdechado © (2007-06-22 18:15) [4]

TUser © (22.06.07 18:14) [3]
Про выпуклость и самопересечение ничего не написано.

← →
TUser © (2007-06-22 18:26) [5]

> Про выпуклость и самопересечение ничего не написано.

Ну, при самопересечениях не совсем понятно, что значит внутри. А выпуклость вроде несущественна.

← →
@!!ex_ (2007-06-22 18:29) [6]

Паралеллепипед

Что имеется ввиду под:
Пофиксить по поводу вершин.

← →
TUser © (2007-06-22 18:52) [7]

Расстояние до каждой грани есть минимум из след. велиичн
1. Длины перпендикуляра.
2. Длин перепендикуляров до сторон.
3. Расстояний до вершин.

Надо найти минимум всех этих штук. Если я правильно понял.

← →
@!!ex_ (2007-06-22 19:11) [8]

> 1. Длины перпендикуляра.

Не понял... какого перпендикуляра??

> 3. Расстояний до вершин.

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

← →
Юрий Зотов © (2007-06-22 19:14) [9]

Для прямоугольника - наименьший из перепендикуляров до сторон.

← →
TUser © (2007-06-22 19:25) [10]

> Не понял... какого перпендикуляра??

До грани.

> Но ведь расстояние до ближайшей плоскости всегда меньше
> чем расстояние до ближайшей вершины, если точка внутри...

Меньше или равно. Но расстонием до плоскости может быть длина перпендикуляра к плоскости, который пересекается с плоскостью вовсе не в той точке, где эта плоскость составляет грань.

← →
@!!ex_ (2007-06-22 20:45) [11]

> Меньше или равно. Но расстонием до плоскости может быть
> длина перпендикуляра к плоскости, который пересекается с
> плоскостью вовсе не в той точке, где эта плоскость составляет
> грань.

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

← →
@!!ex_ (2007-06-22 20:47) [12]

Ну вобщем сутья понял. Спасибо! Как до самого не дошло, не понятно...

← →
TUser © (2007-06-22 20:49) [13]

> Но ведь в параллелепипеде если точка находится внутри, то к каокй плоскости нормаль не опускай, все равно попадешь внутрь параллелепипеда?

Пе обязательно. Проще поэкспериментировать с треугольками, у которых есть тупой угол. Параллелипипед - это будет обобщение.

← →
Однокамушкин (2007-06-22 22:16) [14]

> TUser © (22.06.07 20:49) [13]
> Пе обязательно. Проще поэкспериментировать с треугольками,
> у которых есть тупой угол. Параллелипипед - это будет обобщение.

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

> Выталкивание точки из бокса.

Блин, а по рууски умеем изъясняться?
Только дурак станет выпихивать точку из коробки.

← →
@!!ex_ (2007-06-23 10:10) [16]

> [15] homm © (22.06.07 22:32)

Расслабься. Задача именно такая. Collision Detection реализую вот и все.
А как по твоему надо было сформулировать? :))

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

Например, 4-угольник (0,0)-(0,10)-(2,2)-(10,0) и точка (1,1). Перпендикуляр из этой точки на сторону (2,2)-(10,0) не пересекает никакой другой стороны, поэтому минимальное расстояние до этого ребра равно расстоянию до вершины, а не длине перпендикуляра. С многогранниками аналогично.

> @!!ex_ (23.06.07 10:10) [16]
> А как по твоему надо было сформулировать? :))

Слово "бокс" в этом контексте - слишком неоднозначное, осбенно учитывая, что написано по-русски.
Не надо думать только со своей колокольни :)

> homm © (22.06.07 22:32) [15]
> Только дурак станет выпихивать точку из коробки.

Ну, смотря что выкурить: может оказаться вполне занятным :)

← →
Dmitry S. (2007-06-23 17:36) [19]

> Расслабься. Задача именно такая. Collision Detection реализую
> вот и все.

Маловероятно, с такими вопросами

← →
@!!ex_ (2007-06-23 17:48) [20]

> [19] Dmitry S. (23.06.07 17:36)

Что маловероятнО? :)
Что реализую?
Так уже реализовано, пол года как. Для точки и треугольника. С учетом граней.
Тут задача проще, поскольку определение что точка внутри бокса - тупо проверка расстояния с каждой плоскостью бокса. Если для всех меньше 0, значит внутри. Проблема в том, что не увидел очевидности нахождения кратчайшего расстояния вот и все.

Выталкивание точки из бокса. Найти похожие ветки