Определить, лежит ли точка внутри четырехугольника
|
|
tracer07 | Дата: Понедельник, 22 Октября 2012, 20:35 | Сообщение # 1 |
постоянный участник
Сейчас нет на сайте
| Здравствуйте, подскажите пожалуйста, как определить, лежит ли точка внутри четырехугольника, если известны координаты всех точек фигуры и самой точки для которой нужно определить факт нахождения внутри четырехугольника?
|
|
| |
Spyro23 | Дата: Понедельник, 22 Октября 2012, 20:50 | Сообщение # 2 |
Black Snowflake Games
Сейчас нет на сайте
| Проверять координаты точки и сравнивать их с координатами точек четырёхугольника.
Black Snowflake Games
|
|
| |
tracer07 | Дата: Понедельник, 22 Октября 2012, 21:06 | Сообщение # 3 |
постоянный участник
Сейчас нет на сайте
| А если четырех угольник находится под каким либо углом?
|
|
| |
Kamskii | Дата: Понедельник, 22 Октября 2012, 21:08 | Сообщение # 4 |
Game ≠ Toy
Сейчас нет на сайте
| Дай угадаю - у тебя не четырехугольник, а плоскость?
|
|
| |
tracer07 | Дата: Понедельник, 22 Октября 2012, 21:13 | Сообщение # 5 |
постоянный участник
Сейчас нет на сайте
| Я не знаю как это можно назвать. Есть четыре точки которые образуют фигуру. Допустим тот же квадрат. Мне нужно проверить, попадает ли заданная точка внутрь этого квадрата. Этот квадрат может быть повернут например на 45 градусов, при этом уже получается ромб...
|
|
| |
-Mikle- | Дата: Вторник, 23 Октября 2012, 09:18 | Сообщение # 6 |
Изобретатель велосипедов
Сейчас нет на сайте
| Вот я как-то написал функцию, возвращающую True, если точка лежит внутри полигона, на Visual Basic 6: Code Function PointInPolygon(ByVal X As Single, ByVal Y As Single) As Boolean Dim n1 As Long, n2 As Long, f As Boolean
For n1 = 0 To vCnt - 1 n2 = (n1 + 1) Mod vCnt If (Y > V(n1).Y) Xor (Y > V(n2).Y) Then If X > V(n1).X + (V(n2).X - V(n1).X) * (Y - V(n1).Y) / (V(n2).Y - V(n1).Y) Then f = Not f End If End If Next n1 PointInPolygon = f End Function В полигоне может быть сколько угодно углов, допустима даже невыпуклая фигура. V() - массив вертексов с координатами вершин полигона, vCnt - количество вершин. Mod - вычисление остатка от целочисленного деления. Неинициализированные локальные переменные автоматически инициализируются нулями (False). Long можно смело заменить на Int. Остальное, вроде бы, стандартно для любого ЯП.
Сообщение отредактировал -Mikle- - Вторник, 23 Октября 2012, 10:13 |
|
| |
tracer07 | Дата: Вторник, 23 Октября 2012, 12:23 | Сообщение # 7 |
постоянный участник
Сейчас нет на сайте
| -Mikle-, Спасибо, то что нужно!
|
|
| |
falcoware | Дата: Вторник, 23 Октября 2012, 14:44 | Сообщение # 8 |
старожил
Сейчас нет на сайте
| tracer07, трасер, четырехугольник состоит из 2х треугольников.
А функция нахождения точки в треугольнике такая:
Code BOOL point_in_triangle(point3d& a, point3d& b, point3d& c, point3d& cross){ point3d vab, vac, vcrossa, vcrossb, vcrossc; sub_vectors(&vab.x, &b.x, &a.x); sub_vectors(&vac.x, &c.x, &a.x);
// S triangle * 2; point3d temp; cross_prod(&temp.x, &vab.x, &vac.x); double summa = vect_length(&temp.x);
sub_vectors(&vcrossa.x, &a.x, &cross.x); sub_vectors(&vcrossb.x, &b.x, &cross.x); sub_vectors(&vcrossc.x, &c.x, &cross.x); double res_summa = 0.f;
// S a_b_cross * 2 cross_prod(&temp.x, &vcrossa.x, &vcrossb.x); res_summa = vect_length(&temp.x); if(res_summa > summa){ return FALSE; }
// S c_b_cross * 2 cross_prod(&temp.x, &vcrossb.x, &vcrossc.x); res_summa += vect_length(&temp.x); if(res_summa > summa){ return FALSE; }
// S a_c_cross * 2 cross_prod(&temp.x, &vcrossa.x, &vcrossc.x); res_summa += vect_length(&temp.x);
if(res_summa > (summa + summa * 0.0002)){ return FALSE; }
return TRUE; }
|
|
| |
tracer07 | Дата: Вторник, 23 Октября 2012, 18:43 | Сообщение # 9 |
постоянный участник
Сейчас нет на сайте
| falcoware, Спасибо. Это для трехмерного пространства?
|
|
| |