Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.71/31: Рейтинг темы: голосов - 31, средняя оценка - 4.71
adamo86
2 / 2 / 0
Регистрация: 10.04.2011
Сообщений: 185
1

Геометрия. Принадлежит или не принадлежит?

25.08.2011, 22:50. Просмотров 5886. Ответов 21
Метки нет (Все метки)

Помогите подобрать алгоритм к задачи: есть точка a с координатой x и y - p(x,y) и задана некоторая плоскость из четырех точек a(x,y), b(x,y), c(x,y), d(x,y). Необходимо узнать лежит ли точка p в в заданной плоскости?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2011, 22:50
Ответы с готовыми решениями:

P принадлежит NP
Почему класс задач P принадлежит классу задач NP? Добавлено через 1 минуту Почему правильность...

Принадлежит ли отрезок фигуре
Даны координат вершин многоугольника (не обязательно выпуклой) и координаты концов отрезка. Концы...

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

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

Помогите составить алгоритм: принадлежит ли точка многоугольнику?
Помогите составить алгоритм: Дано множество координат точек (x и y), являющимися вершинами...

21
silent_1991
Эксперт С++
5025 / 3085 / 271
Регистрация: 11.11.2009
Сообщений: 7,047
Завершенные тесты: 1
25.08.2011, 23:15 2
adamo86, считаем площадь четырёхугольника и сумму площадей четырёх треугольников, каждый из которых составлен из пары соседних точек четырёхугольника и точки p. Если эти величины (площадь и сумма площадей) совпадают - точка лежит внутри четырёхугольника. Иначе - не лежит.
2
NIch
400 / 311 / 74
Регистрация: 17.03.2010
Сообщений: 1,120
25.08.2011, 23:25 3
Гениально)))
0
And192
7 / 7 / 0
Регистрация: 10.08.2011
Сообщений: 9
26.08.2011, 00:25 4
Цитата Сообщение от silent_1991 Посмотреть сообщение
Если эти величины (площадь и сумма площадей) совпадают - точка лежит внутри четырёхугольника. Иначе - не лежит.
Для выпуклых фигур это будет работать.

Если четырехугольник невыпуклый, точка может лежать внутри четырехугольника, но площадь самого четырехугольника не обязательно будет равна сумме площадей треугольников. Для невыпуклой фигуры правило работает когда ни один из отрезков, соединяющих точку p c вершиной фигуры не пересекает ее границ.

Точка лежит внутри многогранника, если луч, проведенный из этой точки в любом направлении пересекает грани многогранника нечетное число раз.
3
26.08.2011, 00:25
silent_1991
26.08.2011, 00:28
  #5

Не по теме:

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

0
And192
7 / 7 / 0
Регистрация: 10.08.2011
Сообщений: 9
26.08.2011, 00:33 6
Можно, например, поступить следующим образом:
1. Через точку p провести прямую, параллельную оси х.
2. Найти все точки в которых прямая пересекает стороны четырехугольника.
3. Отбросить точки, лежащие слева от p
4. Подсчитать количество точек. Если нечетное (1 или 3 в случае четырехугольника) - значит точка лежит внутри. Если четное (0,2,4) - снаружи.
2
murderer
4918 / 1590 / 164
Регистрация: 06.10.2010
Сообщений: 3,509
26.08.2011, 10:05 7
Помогите подобрать алгоритм к задачи: есть точка a с координатой x и y - p(x,y) и задана некоторая плоскость из четырех точек a(x,y), b(x,y), c(x,y), d(x,y). Необходимо узнать лежит ли точка p в в заданной плоскости?
1) Плоскость - элемент трёхмерного пространства. Почему координаты двумерные?
2) Для задания плоскости достаточно 3 точек.
0
Dzhej-Dzhej
Заблокирован
26.08.2011, 10:13 8
Цитата Сообщение от murderer Посмотреть сообщение
2) Для задания плоскости достаточно 3 точек.
точно
берем уравнение плоскости ax + by + cz + k = 0, подставляем координаты точки(x, y, z), если равенство справедливо, значит принадлежит
вроде так

Уравнение плоскости по трем точкам
0
Евгений М.
1059 / 995 / 102
Регистрация: 28.02.2010
Сообщений: 2,883
Завершенные тесты: 2
26.08.2011, 11:00 9
Цитата Сообщение от adamo86 Посмотреть сообщение
некоторая плоскость
будем это называть фигурой или частью плоскости. murderer правильно отметил.

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

Осталось подумать как разбить фигуру.

Добавлено через 15 минут
Цитата Сообщение от Евгений М. Посмотреть сообщение
Осталось подумать как разбить фигуру.
Вроде так можно. Берем 2 точки из {a,b,c,d}. К примеру, a,b. Проводим прямую через эти точки. Эта прямая будет делить плоскость Oxy на 2 полуплоскости. Если c и d лежат на разных полуплоскостях, то отрезок [a,b] - это тот отрезок, который делит фигуру на треугольники, иначе - не тот.
За корректность не отвечаю.
1
Thinker
Эксперт С++
4241 / 2215 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 15:00 10
Цитата Сообщение от Евгений М. Посмотреть сообщение
Вроде так можно...
Чтобы определить, лежат ли две точки C и D по обе стороны относительно прямой, проходящей через точки A и B, можно посмотреть знаки векторных произведений
http://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{AB}\times \vec{AC} и http://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{AB}\times \vec{AD}.
Если знаки разные, то лежат по обе стороны. А уж векторное произведение просто подсчитать, здесь это определитель матрицы 2 на 2.
0
Евгений М.
1059 / 995 / 102
Регистрация: 28.02.2010
Сообщений: 2,883
Завершенные тесты: 2
26.08.2011, 17:27 11
Цитата Сообщение от Thinker Посмотреть сообщение
знаки векторных произведений
О_о знаки? Вы может быть скалярное произведение имели ввиду?
0
murderer
4918 / 1590 / 164
Регистрация: 06.10.2010
Сообщений: 3,509
26.08.2011, 17:48 12
Евгений М.
Принадлежность точки многоугольнику устанавливается проще. Как написал And192
Точка лежит внутри многогранника, если луч, проведенный из этой точки в любом направлении пересекает грани многогранника нечетное число раз.
0
Somebody
3104 / 1625 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
26.08.2011, 17:54 13
Цитата Сообщение от Евгений М. Посмотреть сообщение
знаки?
Наверное, знак координаты z векторного произведения, которое будет или вверх или вниз от плоскости. x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?
1
murderer
4918 / 1590 / 164
Регистрация: 06.10.2010
Сообщений: 3,509
26.08.2011, 18:38 14
x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?
x1*y2-y2*x1=0
1
Somebody
3104 / 1625 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
26.08.2011, 21:33 15
Вот блин
Ну тогда x1*y2-x2*y1
0
Thinker
Эксперт С++
4241 / 2215 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.08.2011, 22:07 16
Цитата Сообщение от Евгений М. Посмотреть сообщение
О_о знаки? Вы может быть скалярное произведение имели ввиду?
Именно векторное произведение. Вернее длина полученного вектора со знаком. Скалярное тут совсем не нужно. Такой метод применяется при построении выпуклых оболочек, проверке, является ли многоугольник выпуклым и т.д.
0
Mr.X
Эксперт С++
3193 / 1720 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
27.08.2011, 09:40 17
Цитата Сообщение от Somebody Посмотреть сообщение
Наверное, знак координаты z векторного произведения, которое будет или вверх или вниз от плоскости. x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?
Косое произведение
1
Thinker
Эксперт С++
4241 / 2215 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.08.2011, 09:50 18
Цитата Сообщение от Somebody Посмотреть сообщение
Наверное, знак координаты z векторного произведения, которое будет или вверх или вниз от плоскости. x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?
В данном случае так и есть, знак компоненты z, спасибо за пояснение. z = x1*y2-x2*y1
0
Puporev
27.08.2011, 09:52
  #19

Не по теме:

Для того чтобы тема стала максимально информативной нужно просто задать тупой вопрос типа

Цитата Сообщение от adamo86 Посмотреть сообщение
задана некоторая плоскость из четырех точек a(x,y), b(x,y), c(x,y), d(x,y).

1
videolord
49 / 15 / 2
Регистрация: 20.02.2011
Сообщений: 152
03.09.2011, 01:17 20
adamo86, считаем площадь четырёхугольника и сумму площадей четырёх треугольников, каждый из которых составлен из пары соседних точек четырёхугольника и точки p. Если эти величины (площадь и сумма площадей) совпадают - точка лежит внутри четырёхугольника. Иначе - не лежит.
верно! площадь каждого треуголнка и площадь четырехугольника надо считать с помошю косого произведения векторов, так без потери точности посчитаете площадь

В декартовой системе координат на плоскости заданы координаты вершин треугольника и ещё одной точки. Определить, принадлежит ли эта точка треугольнику. задача
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Scanner;
public class triangleDot {
static long area(long x1,long y1,long x2,long y2,long x3,long y3){
long s=Math.abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
return s; 
}
    public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    long x1=sc.nextInt();
    long y1=sc.nextInt();
    long x2=sc.nextInt();
    long y2=sc.nextInt();
    long x3=sc.nextInt();
    long y3=sc.nextInt();
    long x0=sc.nextInt();
    long y0=sc.nextInt();
    long s=area(x1,y1,x2,y2,x0,y0)+area(x2,y2,x3,y3,x0,y0)+area(x1,y1,x0,y0,x3,y3);
    if(area(x1,y1,x2,y2,x3,y3)==s)  
       System.out.println("In");
    else
        System.out.println("Out");
    }
 
}
0
03.09.2011, 01:17
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2011, 01:17

Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вер
Здравствуйте! Задача состоит в следующем: Найти такую вершину заданного графа, которая...

Вычислить координаты ближайшей точки, которая принадлежит отрезку и точки на плоскости
Есть плоскость с осями x и y, на ней расположен отрезок, координаты конца A и начала B этого...

Геометрия (проверить, принадлежит ли третья точка кругу!)
Отрезок прямой задан двумя точками и есть радиусом круга с центром в первой точке, приверить...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.