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

@adamo86 · Регистрация: 10.04.2011

Студворк — интернет-сервис помощи студентам

Помогите подобрать алгоритм к задачи: есть точка a с координатой x и y - p(x,y) и задана некоторая плоскость из четырех точек a(x,y), b(x,y), c(x,y), d(x,y). Необходимо узнать лежит ли точка p в в заданной плоскости?

silent_1991 · 25.08.2011, 23:15

adamo86, считаем площадь четырёхугольника и сумму площадей четырёх треугольников, каждый из которых составлен из пары соседних точек четырёхугольника и точки p. Если эти величины (площадь и сумма площадей) совпадают - точка лежит внутри четырёхугольника. Иначе - не лежит.

@NIch · 25.08.2011, 23:25

Гениально)))

@And192 · 26.08.2011, 00:25

Сообщение от silent_1991

Если эти величины (площадь и сумма площадей) совпадают - точка лежит внутри четырёхугольника. Иначе - не лежит.

Для выпуклых фигур это будет работать.

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

Точка лежит внутри многогранника, если луч, проведенный из этой точки в любом направлении пересекает грани многогранника нечетное число раз.

silent_1991 · 26.08.2011, 00:28

Не по теме:

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

@And192 · 26.08.2011, 00:33

Можно, например, поступить следующим образом:
1. Через точку p провести прямую, параллельную оси х.
2. Найти все точки в которых прямая пересекает стороны четырехугольника.
3. Отбросить точки, лежащие слева от p
4. Подсчитать количество точек. Если нечетное (1 или 3 в случае четырехугольника) - значит точка лежит внутри. Если четное (0,2,4) - снаружи.

murderer · 26.08.2011, 10:05

Помогите подобрать алгоритм к задачи: есть точка a с координатой x и y - p(x,y) и задана некоторая плоскость из четырех точек a(x,y), b(x,y), c(x,y), d(x,y). Необходимо узнать лежит ли точка p в в заданной плоскости?

1) Плоскость - элемент трёхмерного пространства. Почему координаты двумерные?
2) Для задания плоскости достаточно 3 точек.

@Dzhej-Dzhej · 26.08.2011, 10:13

Сообщение от murderer

2) Для задания плоскости достаточно 3 точек.

точно
берем уравнение плоскости ax + by + cz + k = 0, подставляем координаты точки(x, y, z), если равенство справедливо, значит принадлежит
вроде так

Уравнение плоскости по трем точкам

Евгений М. · 26.08.2011, 11:00

Сообщение от adamo86

некоторая плоскость

будем это называть фигурой или частью плоскости. murderer правильно отметил.

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

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

Добавлено через 15 минут

Сообщение от Евгений М.

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

Вроде так можно. Берем 2 точки из {a,b,c,d}. К примеру, a,b. Проводим прямую через эти точки. Эта прямая будет делить плоскость Oxy на 2 полуплоскости. Если c и d лежат на разных полуплоскостях, то отрезок [a,b] - это тот отрезок, который делит фигуру на треугольники, иначе - не тот.
За корректность не отвечаю.

@Thinker · 26.08.2011, 15:00

Сообщение от Евгений М.

Вроде так можно...

Чтобы определить, лежат ли две точки C и D по обе стороны относительно прямой, проходящей через точки A и B, можно посмотреть знаки векторных произведений
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{AB}\times \vec{AC}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{AB}\times \vec{AD}$ .
Если знаки разные, то лежат по обе стороны. А уж векторное произведение просто подсчитать, здесь это определитель матрицы 2 на 2.

Евгений М. · 26.08.2011, 17:27

Сообщение от Thinker

знаки векторных произведений

О_о знаки? Вы может быть скалярное произведение имели ввиду?

murderer · 26.08.2011, 17:48

Евгений М.
Принадлежность точки многоугольнику устанавливается проще. Как написал And192

Точка лежит внутри многогранника, если луч, проведенный из этой точки в любом направлении пересекает грани многогранника нечетное число раз.

@Somebody · 26.08.2011, 17:54

Сообщение от Евгений М.

знаки?

Наверное, знак координаты z векторного произведения, которое будет или вверх или вниз от плоскости. x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?

murderer · 26.08.2011, 18:38

x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?

x1*y2-y2*x1=0

@Somebody · 26.08.2011, 21:33

Вот блин

Ну тогда x1*y2-x2*y1

@Thinker · 26.08.2011, 22:07

Сообщение от Евгений М.

О_о знаки? Вы может быть скалярное произведение имели ввиду?

Именно векторное произведение. Вернее длина полученного вектора со знаком. Скалярное тут совсем не нужно. Такой метод применяется при построении выпуклых оболочек, проверке, является ли многоугольник выпуклым и т.д.

@Mr.X · 27.08.2011, 09:40

Сообщение от Somebody

Наверное, знак координаты z векторного произведения, которое будет или вверх или вниз от плоскости. x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?

Косое произведение

@Thinker · 27.08.2011, 09:50

Сообщение от Somebody

Наверное, знак координаты z векторного произведения, которое будет или вверх или вниз от плоскости. x1*y2-y2*x1 - как это применительно к двумерному пространству правильно называется?

В данном случае так и есть, знак компоненты z, спасибо за пояснение. z = x1*y2-x2*y1

@Puporev · 27.08.2011, 09:52

Не по теме:

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

Сообщение от adamo86

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

@videolord · 03.09.2011, 01:17

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");
    }
 
}

Новые блоги и статьи Все статьи Все блоги /
Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@adamo86 2 / 2 / 0 Регистрация: 10.04.2011 Сообщений: 185

	Геометрия. Принадлежит или не принадлежит? 25.08.2011, 22:50. Показов 6777. Ответов 21 Метки нет (Все метки) Помогите подобрать алгоритм к задачи: есть точка a с координатой x и y - p(x,y) и задана некоторая плоскость из четырех точек a(x,y), b(x,y), c(x,y), d(x,y). Необходимо узнать лежит ли точка p в в заданной плоскости? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	25.08.2011, 23:15
	adamo86, считаем площадь четырёхугольника и сумму площадей четырёх треугольников, каждый из которых составлен из пары соседних точек четырёхугольника и точки p. Если эти величины (площадь и сумма площадей) совпадают - точка лежит внутри четырёхугольника. Иначе - не лежит. 2

@NIch 401 / 312 / 74 Регистрация: 17.03.2010 Сообщений: 1,119
	25.08.2011, 23:25
	Гениально))) 0

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

@And192 7 / 7 / 0 Регистрация: 10.08.2011 Сообщений: 9
	26.08.2011, 00:33
	Можно, например, поступить следующим образом: 1. Через точку p провести прямую, параллельную оси х. 2. Найти все точки в которых прямая пересекает стороны четырехугольника. 3. Отбросить точки, лежащие слева от p 4. Подсчитать количество точек. Если нечетное (1 или 3 в случае четырехугольника) - значит точка лежит внутри. Если четное (0,2,4) - снаружи. 2

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	26.08.2011, 21:33
	Вот блин Ну тогда x1y2-x2y1 0