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;
Попадание точки в треугольник
Отцы, помогите начинающему программёру.
Суть проблемы такова: даны координаты вершин треугольника, и точки, надо проверить, лежит ли эта точка в данном треугольнике?А, и потом еще найти расстояние от точки до ближайшей стороны треугольника.
Плз, направьте меня на верную мысль. Зарание спасибо.
Суть проблемы такова: даны координаты вершин треугольника, и точки, надо проверить, лежит ли эта точка в данном треугольнике?А, и потом еще найти расстояние от точки до ближайшей стороны треугольника.
Плз, направьте меня на верную мысль. Зарание спасибо.
Вроде если сумма расстояний от каждой вершины до точки меньше периметра, то внутри, иначе - вовне.
А вообще, посмотри по геометрии расстояние от прямой до точки (это класс 8-9 школы, если не раньше)
А вообще, посмотри по геометрии расстояние от прямой до точки (это класс 8-9 школы, если не раньше)
С точкой внутри треугольника можно так:
I.
1. Считаем площадь треугольника (формула герона или стороны-синус)
2. Бьем треугольник на 3 (с помощью ентой точки).
3. Считаем сумму площадей.
4. Совпадает-внутри, нет-снаружи.
II.
С фигурками посложнее можно так:
1. Пускаем из данной точки луч так, чтоб он не пересекал вершину фигуры.
2. Смотрим скока сторон пересек наш луч.
3. Нечетное-внутри, четное-снаружи.
III.
Вычисление расстояния организуй через вектора.
:)
I.
1. Считаем площадь треугольника (формула герона или стороны-синус)
2. Бьем треугольник на 3 (с помощью ентой точки).
3. Считаем сумму площадей.
4. Совпадает-внутри, нет-снаружи.
II.
С фигурками посложнее можно так:
1. Пускаем из данной точки луч так, чтоб он не пересекал вершину фигуры.
2. Смотрим скока сторон пересек наш луч.
3. Нечетное-внутри, четное-снаружи.
III.
Вычисление расстояния организуй через вектора.
:)
Sorry за жестокий оффтоп.
Sanyia, извини за нескромный вопрос.
А из пушки по воробьям не пробовал? Или компьютером гвозди забивать?
И вообще данную задачу можно решить переведя все в полярную сисетму координат....
Sanyia, извини за нескромный вопрос.
А из пушки по воробьям не пробовал? Или компьютером гвозди забивать?
И вообще данную задачу можно решить переведя все в полярную сисетму координат....
Берем учебник аналитической геометрии и линейной алгебры и роем на предмет принадлежности точки плоскости. Тама в маскимум в 2 формулы
Большое спасибо, всё оказалось гораздо проще, чем казалось:)
В своё время сталкивался с этим. Реализовал вот так
Код:
даа протупил я...
а это похоже наилучший способ
а это похоже наилучший способ
Цитата:
Вроде если сумма расстояний от каждой вершины до точки меньше периметра, то внутри, иначе - вовне.
[quote=s$s]решение влоб:
-----------------
Хт Є [minX;maxX]
and
Ут Є [minY;maxY]
-----------------
Хт,Ут - координаты точки
minX,maxX - минимальная и максимальная координата вершины по Х
minУ,maxУ - минимальная и максимальная координата вершины по У[/quote]
Ну и получиться проверка на попадание в прямоугольник.
-----------------
Хт Є [minX;maxX]
and
Ут Є [minY;maxY]
-----------------
Хт,Ут - координаты точки
minX,maxX - минимальная и максимальная координата вершины по Х
minУ,maxУ - минимальная и максимальная координата вершины по У[/quote]
Ну и получиться проверка на попадание в прямоугольник.
Цитата:
даа протупил я...
а это похоже наилучший способ
Цитата:
Вроде если сумма расстояний от каждой вершины до точки меньше периметра, то внутри, иначе - вовне.
а это похоже наилучший способ
Цитата:
Вроде если сумма расстояний от каждой вершины до точки меньше периметра, то внутри, иначе - вовне.
Треугольник (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
Есть разница???
Когда я учился в школе, у нас была такая задачка на какой-то олимпиаде по информатике.
Я решал так - брал прямую, содержащую сторону треугольника, находил с какй стороны от неё лежат данная точка и третья вершина. Если с одинаковой - всё ок. И так для всех трёх сторон. Если везде сошлось - точка внутри.
Очень прикололо меня решение одного парня. Он на невидимом экране (дело происходило на Ямахах MSX-2) рисовал треугольник, закрашивал, а потом смотрел - какого цвета точка искомая получилась. Обломился он на следующем - в тестовых заданиях были координаты вершин порядка 0-1. В итоге треугольник у него получился размером 1х1 пиксель. И с искомой точкой не повезло - в пиксель попала, а в треугольник - нет. :)
Я решал так - брал прямую, содержащую сторону треугольника, находил с какй стороны от неё лежат данная точка и третья вершина. Если с одинаковой - всё ок. И так для всех трёх сторон. Если везде сошлось - точка внутри.
Очень прикололо меня решение одного парня. Он на невидимом экране (дело происходило на Ямахах MSX-2) рисовал треугольник, закрашивал, а потом смотрел - какого цвета точка искомая получилась. Обломился он на следующем - в тестовых заданиях были координаты вершин порядка 0-1. В итоге треугольник у него получился размером 1х1 пиксель. И с искомой точкой не повезло - в пиксель попала, а в треугольник - нет. :)
А в трёхмерной системе координат x, y, z?
нужно к предыдущей сводить
уравнение плоскости составим и проверим принадлежит ли ей точка
а дальше либо нет либо задача на плоскости
уравнение плоскости составим и проверим принадлежит ли ей точка
а дальше либо нет либо задача на плоскости