Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
na4ik
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 14
1

Принадлежит ли точка четырехугольнику?

05.11.2014, 11:20. Просмотров 1297. Ответов 9
Метки нет (Все метки)

Подскажите пожалуйста, как можно по проще проверить лежит ли заданная точка (x, y) внутри четырехугольника, если задано его 4 вершины.

Код нужен на php, ну думаю з C++ буде не сложно перевести.
Этот элемент в принципе работает, только проблема буде если задать точки <0;

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?php
$x1=0;
$y1=0;
 
$x2=12;
$y2=0;
 
$x3=0;
$y3=10;
 
$x4=12;
$y4=10;
 
$x=15;
$y=5;
 
if(($x>=$x1)&&($x<=$x4)&&($y>=$y1)&&($y<=$y4)) print "Точка належить чотирикутнику";
else print "Точка НЕ належить чотирикутнику"
?>
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2014, 11:20
Ответы с готовыми решениями:

Принадлежит ли точка четырехугольнику.
Надеюсь на помощь форумчан: Задача следующяя: задана коодинатами точек...

Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае.
Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с...

Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
Даны отрезки и и точка A с координатой х. Определить, принадлежит ли данная...

Определить принадлежит точка точка координатам
Такая задача даны действительные числа x y определить принадлежит точка ...

Принадлежит ли точка окружности
Нужно было написать программу определяющию принадлежит ли точка окружности {...

9
-THE_MASTER666-
Заблокирован
05.11.2014, 11:24 2
Цитата Сообщение от na4ik Посмотреть сообщение
как можно по проще проверить лежит ли заданная точка (x, y) внутри четырехугольника
Никак. Для определения 4-х угольника достаточно двух точек его диагонали, например LEFT_TOP и RIGHT_BOTTOM, собственно ты эти точки в условии и проверяешь. Проще сделать нельзя.
1
na4ik
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 14
05.11.2014, 11:27  [ТС] 3
-THE_MASTER666-, Проблема просто в том, что для примера задать точку (0;0) и взять одну вершину для примера (-3,3) то не выполнится условия ($y>=$y1)...не могу придумать как решить эту проблему.
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4833 / 2478 / 695
Регистрация: 18.10.2014
Сообщений: 4,285
05.11.2014, 11:27 4
Цитата Сообщение от na4ik Посмотреть сообщение
лежит ли заданная точка (x, y) внутри четырехугольника
Так а что известно про четырехугольник? Может быть это прямоугольник? Может это даже осеориентированный прямоугольник???

В примере у вас задан осеориентированный прямоугольник, что наводит на смутные сомнения. Если вам нужен именно осеориентированный прямоугольник, то ставить задачу через термин "четырехугольник"... за это надо направлять на сельхозработы.
0
na4ik
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 14
05.11.2014, 11:31  [ТС] 5
TheCalligrapher, Вот полная постановка задачи: "Создать (html-форму для передачи в РНР-скрипта координат четырех вершин четырехугольника и координат произвольной точки. Вычислить на серверном стороне, находится эта точка внутри четырехугольника (включая его границы) или за его пределами и передать соответствующий ответ в html-документа."
Ну мне в принципе нужно что бы только правильно определяло, остальное сам)
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4833 / 2478 / 695
Регистрация: 18.10.2014
Сообщений: 4,285
05.11.2014, 11:33 6
Цитата Сообщение от na4ik Посмотреть сообщение
координат четырех вершин четырехугольника
Ну в такой постановке мы имеем дело с произвольным четырехугольником, возможно даже невыпуклым. Такая задача не решается в две строчки.
0
na4ik
0 / 0 / 0
Регистрация: 02.11.2013
Сообщений: 14
05.11.2014, 11:48  [ТС] 7
TheCalligrapher, Может быть можно просто как то сместить все точки в положительную часть системы координат...и тогда буде подходить под изначальное условия?
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4833 / 2478 / 695
Регистрация: 18.10.2014
Сообщений: 4,285
05.11.2014, 11:55 8
Вот вариант для произвольного четырехугольника, основанный на классическом подходе с подсчетом количества пересечений ребер многоугольника с горизонтальным лучом и проверкой четности этого количества. Это вариант на самом деле работает для произвольного многоугольника с любым количеством вершин. Что наводит на мысль о том, что именно для четырехугольника можно придумать что-то поостроумнее.

Если бы про ваш четырехугольник было что-то дополнительно известно (например, что он всегда выпуклый), то это могло бы упростить задачу. Хотя и алгоритм ниже тоже весьма прост.

Разумеется, всегда остаются тонкости обработки точек "на ребрах" - они внутри или нет? И тонкости дребезга и/или переполнения целочисленой арифметики. Но это уже детали.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
unsigned intersects_right(int px, int py, int x1, int y1, int x2, int y2)
{
  if (y1 > y2) {
    std::swap(x1, x2);
    std::swap(y1, y2);
  }
 
  if (py < y1 || py >= y2)
    return 0;
 
  if (x1 == x2)
    return px <= x1;
 
  int x = x1 + (py - y1) * (x2 - x1) / (y2 - y1);
  return px <= x;
}
 
int main()
{
  // Четырехугольник
  const unsigned N = 4;
  const int X[N] = { 10, 20, 10, 0 };
  const int Y[N] = { 0,  20, 40, 20 };
 
  // Точка
  const int PX = 5;
  const int PY = 5;
 
  // Проверка
  int xp = X[N - 1];
  int yp = Y[N - 1];
  unsigned nintersects = 0;
 
  for (unsigned i = 0; i < N; ++i)
  {
    nintersects += intersects_right(PX, PY, xp, yp, X[i], Y[i]);
    xp = X[i];
    yp = Y[i];
  }
 
  std::cout << (nintersects % 2 != 0 ? "Внутри" : "Снаружи") << std::endl;
}
0
-THE_MASTER666-
Заблокирован
05.11.2014, 11:58 9
Лучший ответ Сообщение было отмечено na4ik как решение

Решение

Цитата Сообщение от na4ik Посмотреть сообщение
роблема просто в том, что для примера задать точку (0;0) и взять одну вершину для примера (-3,3) то не выполнится условия ($y>=$y1)...не могу придумать как решить эту проблему.
Смотри, для того, чтоб у тебя всегда выполнялось условие, тебе надо этот 4-х угольник привести к нормальному виду, то есть к виду, с которым работает твоё условие. В таком случае тебе понадобятся все 4 координаты (точнее их составные части)

Вникай о чём я. У твоего прямоугольника есть координаты по X: LEFT, RIGHT и координаты по Y: TOP, BOTTOM.
То есть ты можешь свой 4-х угольник задать двумя точками: LEFT_TOP / RIGHT_BOTTOM.
Так вот, если у тебя RIGHT не больше LEFT, допустим у тебя LEFT = 0.0, а RIGHT = -3.0, ну допустим так, так как в программе после каких - то автоматических вычислений может так получиться, тебе надо привести своё 4-х угольник к нормальному проверяемому виду, то есть чтоб RIGHT опять стал больше LEFT, для этого тебе надо поменять LEFT И RIGHT местами. Понял? Вот смотри, живой пример:

4-х угольник:
LEFT = 0;
RIGHT = -5;
TOP = 2;
BOTTOM = 10;


сразу видно, что право не справа , а слева и верх не верх, а низ ))))))
Делаешь при помощи 3-х / 4-х if-ов нормальный 4-х угольник, чтоб на выходе получился:
LEFT = -5;
RIGHT = 0;
TOP = 10;
BOTTOM = 2;

Всё, теперь у тебя лево слева и низ снизу - можешь смело проверять свою точку
1
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4833 / 2478 / 695
Регистрация: 18.10.2014
Сообщений: 4,285
05.11.2014, 12:03 10
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Вот вариант для произвольного четырехугольника
Код надо подправить

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
unsigned intersects_right(int px, int py, int x1, int y1, int x2, int y2)
{
  if (y1 == y2)
    return 0;
 
  if (y1 > y2) {
    std::swap(x1, x2);
    std::swap(y1, y2);
  }
 
  if (py < y1 || py >= y2)
    return 0;
 
  if (x1 == x2)
    return px <= x1;
 
  int x = x1 + (py - y1) * (x2 - x1) / (y2 - y1);
  return px <= x;
}
Есть еще тонкости с точками на границе, о которых следует немного подумать...
0
05.11.2014, 12:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2014, 12:03

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

Принадлежит ли точка прямоугольнику?
Составить программку для определения принадлежности точки в прямоугольной...

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


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

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

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