Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Попадание точки в треугольник

4.6K
31 октября 2006 года
SerG1nho
72 / / 30.10.2006
Отцы, помогите начинающему программёру.
Суть проблемы такова: даны координаты вершин треугольника, и точки, надо проверить, лежит ли эта точка в данном треугольнике?А, и потом еще найти расстояние от точки до ближайшей стороны треугольника.
Плз, направьте меня на верную мысль. Зарание спасибо.
547
01 ноября 2006 года
Hydra
488 / / 20.06.2006
Вроде если сумма расстояний от каждой вершины до точки меньше периметра, то внутри, иначе - вовне.
А вообще, посмотри по геометрии расстояние от прямой до точки (это класс 8-9 школы, если не раньше)
3.2K
01 ноября 2006 года
Sania
186 / / 28.10.2006
С точкой внутри треугольника можно так:
I.
1. Считаем площадь треугольника (формула герона или стороны-синус)
2. Бьем треугольник на 3 (с помощью ентой точки).
3. Считаем сумму площадей.
4. Совпадает-внутри, нет-снаружи.
II.
С фигурками посложнее можно так:
1. Пускаем из данной точки луч так, чтоб он не пересекал вершину фигуры.
2. Смотрим скока сторон пересек наш луч.
3. Нечетное-внутри, четное-снаружи.
III.
Вычисление расстояния организуй через вектора.
:)
547
02 ноября 2006 года
Hydra
488 / / 20.06.2006
Sorry за жестокий оффтоп.
Sanyia, извини за нескромный вопрос.
А из пушки по воробьям не пробовал? Или компьютером гвозди забивать?
И вообще данную задачу можно решить переведя все в полярную сисетму координат....
269
03 ноября 2006 года
Greenering
892 / / 04.02.2003
Берем учебник аналитической геометрии и линейной алгебры и роем на предмет принадлежности точки плоскости. Тама в маскимум в 2 формулы
4.6K
06 ноября 2006 года
SerG1nho
72 / / 30.10.2006
Большое спасибо, всё оказалось гораздо проще, чем казалось:)
17K
12 ноября 2006 года
jack marked
20 / / 12.11.2006
В своё время сталкивался с этим. Реализовал вот так
Код:
type
  TExPoint = packed record // Координаты радиус-вектора
    X, Y: Extended;
  end;
 
function PointInTriangle(const Point, P1, P2, P3: TExPoint): Boolean;
begin
  Result := ParallelogramSquare(Point, P1, P2) +
  ParallelogramSquare(Point, P1, P3) +
  ParallelogramSquare(Point, P2, P3) <= ParallelogramSquare(P1, P2, P3)
end;
 
function ParallelogramSquare(const P1, P2, P3: TExPoint): Extended;
begin
  Result := Abs((P2.X - P1.X) * (P3.Y - P1.Y) - (P2.Y - P1.Y) * (P3.X - P1.X));
end;
17K
12 ноября 2006 года
s$s
25 / / 05.09.2006
даа протупил я...
а это похоже наилучший способ
Цитата:
Вроде если сумма расстояний от каждой вершины до точки меньше периметра, то внутри, иначе - вовне.

292
13 ноября 2006 года
Matush
726 / / 14.01.2004
[quote=s$s]решение влоб:
-----------------
Хт Є [minX;maxX]
and
Ут Є [minY;maxY]
-----------------
Хт,Ут - координаты точки
minX,maxX - минимальная и максимальная координата вершины по Х
minУ,maxУ - минимальная и максимальная координата вершины по У[/quote]

Ну и получиться проверка на попадание в прямоугольник.
3.2K
17 ноября 2006 года
Sania
186 / / 28.10.2006
Цитата:
даа протупил я...
а это похоже наилучший способ
Цитата:
Вроде если сумма расстояний от каждой вершины до точки меньше периметра, то внутри, иначе - вовне.


Треугольник (0,0)(0,100 000 000)(1,0)
Периметр ~ 200 000 000
Точка (-0.01,-0.01) сумма расстояний до вершин ~ 100 000 001
Точка (0,100 000 001) сумма ~ 200 000 000
Есть разница???

267
17 ноября 2006 года
Cutty Sark
1.2K / / 17.10.2002
Когда я учился в школе, у нас была такая задачка на какой-то олимпиаде по информатике.

Я решал так - брал прямую, содержащую сторону треугольника, находил с какй стороны от неё лежат данная точка и третья вершина. Если с одинаковой - всё ок. И так для всех трёх сторон. Если везде сошлось - точка внутри.

Очень прикололо меня решение одного парня. Он на невидимом экране (дело происходило на Ямахах MSX-2) рисовал треугольник, закрашивал, а потом смотрел - какого цвета точка искомая получилась. Обломился он на следующем - в тестовых заданиях были координаты вершин порядка 0-1. В итоге треугольник у него получился размером 1х1 пиксель. И с искомой точкой не повезло - в пиксель попала, а в треугольник - нет. :)
31K
05 сентября 2007 года
Sodin
1 / / 02.07.2007
А в трёхмерной системе координат x, y, z?
622
05 сентября 2007 года
nilbog
507 / / 19.12.2006
нужно к предыдущей сводить
уравнение плоскости составим и проверим принадлежит ли ей точка
а дальше либо нет либо задача на плоскости

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог