| Вопрос: условие принадлежности точки к плоскости | Добавлено: 19.03.06 20:11 |
Автор вопроса:  КУДЕСНИК
|
|
я занемаюсь vb смовсем недавно только 2 недели
мне нужно решить задачу кто может подскажите как я еще много незнаю так что самые легкие варианты 2. Даны действительные числа Х0,Х1, Х2, Х3, Y0,Y1, Y2, Y3. Определить принадлежит ли точка с координатами (Х0, Y0) треугольнику с вершинами в точках (Х1, Y1), (Х2, Y2), (Х3Y3). |
| Ответы | Всего ответов: 22 |
|
Номер ответа: 1 Автор ответа:  SL ICQ: 277007669 Вопросов: 10 Ответов: 86 |
Профиль | | #1 | Добавлено: 19.03.06 21:01 |
| это уж не бейсик а математика, точнее геометрия | ||
|
Номер ответа: 2 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #2 | Добавлено: 19.03.06 21:19 |
|
Не силен я в геометрии:
Задача сводится к проверке пересечения 2х отрезков: 1) взять 2 точки треугольника 2) проверить, пересекается ли отрезок, образованный этими 2мя точками и отрезок из оставшейся и и проверяемой точки 3) проверить еще 2 раза для 2-х оставшихся комбинаций 4) если нет ни одного пересекания, значит точка внутри. |
||
|
Номер ответа: 3 Автор ответа: SLICQ: 277007669 Вопросов: 10 Ответов: 86 |
Профиль | | #3 | Добавлено: 19.03.06 21:27 |
| проверяй, в какой полуплоскости от каждой прямой расположена точка | ||
|
Номер ответа: 4 Автор ответа: SLICQ: 277007669 Вопросов: 10 Ответов: 86 |
Профиль | | #4 | Добавлено: 19.03.06 21:28 |
| да, определи, в какой полуплоскости лежит противоположная вершина треугольника, и если точка в ней, то проверяй дальше, иначе не принадлежит треугольнику | ||
|
Номер ответа: 5 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #5 | Добавлено: 19.03.06 21:31 |
|
Проверка пересечения отрезков (x1 х2 х3 х4 у1 у2 у3 у4):
1) найти точку пересечения (задача для 7классника) (получим X0,Y0) 2) если X0 находится между (или равен) X1 и X2 и Y0 тоже между (или равен) у1 у2, значит отрезки пересекаются. |
||
|
Номер ответа: 6 Автор ответа: SLICQ: 277007669 Вопросов: 10 Ответов: 86 |
Профиль | | #6 | Добавлено: 19.03.06 21:31 |
|
2ChemistN1:
добавляю(поправляю): 4)если нет ни одного пересекания, значит точка снаружи. |
||
|
Номер ответа: 7 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #7 | Добавлено: 19.03.06 21:34 |
|
1) хотел сказать, найти точку пересечения прямых содержащих отрезки.
Объедини с тем что я сказал в начале - будет готовый алгоритм |
||
|
Номер ответа: 8 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #8 | Добавлено: 19.03.06 21:36 |
| 4) Да нет, вроде я не ошибся. Внутри точка будет, если пересечений нет. | ||
|
Номер ответа: 9 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #9 | Добавлено: 19.03.06 21:40 |
|
Чтобы не было путаницы:
1) взять 2 точки треугольника 2) проверить, пересекается ли отрезок, образованный этими 2мя точками и отрезок из оставшейся и и проверяемой точки 3) проверить еще 2 раза для 2-х оставшихся комбинаций 4) если нет ни одного пересекания, значит точка внутри. Проверка пересечения отрезков (x1 х2 х3 х4 у1 у2 у3 у4): 1) найти точку пересечения прямых, содержащих отрезки 2) если X0 находится между (или равен) X1 и X2 и Y0 тоже между (или равен) у1 у2, значит отрезки пересекаются. |
||
|
Номер ответа: 10 Автор ответа: Morpheus Вопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #10 | Добавлено: 19.03.06 22:20 |
| там помню чё то какая то теорема была, блин забыл короче что точка если лежит внутри треугольника, то длина отрезков от неё до вершин поддаётся какой то пропорции, короче если кто помнит может нипишите сюды | ||
|
Номер ответа: 11 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #11 | Добавлено: 19.03.06 22:33 |
|
Да, чето такое было. Короче, алгоритм, который я предложил, работает не всегда, проверил.
Вот 99,99% алгоритм: 1) провести от точки до вершин треугольника отрезки 2) попарно проверить пересечения сторон треугольника и отрезков (всего 9 проверок) 3) если есть хоть 1 пересечение, точка снаружи |
||
|
Номер ответа: 12 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #12 | Добавлено: 19.03.06 22:44 |
|
Или так:
Если площадь 3х треугольников, составленных из точки и сторон исходного треугольника = плошади исходного треугольника, то точка внутри. Если больше - снаружи. 100% работает, но считать долго. |
||
|
Номер ответа: 13 Автор ответа: ChemistN1Вопросов: 7 Ответов: 43 |
Web-сайт: Профиль | | #13 | Добавлено: 20.03.06 06:09 |
|
Площади можно найти по формуле Герона. Так как числа получатся вещественные, то чтоб точка не была всегда вне треугольника, проверять с точностю дельта.
Вот, откопал еще 2 способа, мож чего и поймете (извиняйте, если непонятно, писал не я): Определение, лежит ли точка внутри треугольник или нет. У нас есть точка пересечения плоскости с лучом. Теперь надо определить, лежит ли эта точка внутри трекгольника (полигона) или нет. "Barycentric intersection" алгоритм. Это довольно быстрый алгоритм для определения, лежит ли точка внутри треугольника или снаружи. К сожалению, его нельзя применять для многоугольников. Но я думаю, что это и не надо, т.к. полигон всегда можно разбить на треугольники. Я не буду приводить весь вывод, т.к. это сплошная высшая алгебра, и большинство (такие как я) просто запутаются и ничего не поймут 
Параметрическое уравнение плоскости имеет вид: P = (1-u-v)*A + u*B + v*C (3) A, B и C - три точки, задающие плоскость. (Не путать с координатами вектора нормали!). Если мы будем изменять u и v от –Ґ до +Ґ, то будем всегда получать точки P, лежащие в плоскости ABC. Если все коэффициенты і 0, то точка лежит внутри треугольника ABC, т.е. 1-u-v і 0, u і 0 и v і 0. Таким образом, надо выразить из (3) u и v, подставить вместо P точку пересечения прямой с треугольником и проверить следующие условия: 0 Ј u Ј 1 и 0 Ј v Ј (1–u). Если это выполняется, то точка пересечения лежит внутри треугольника ABC. Алгоритм N2. Этот алгоритм тоже довольно хороший и его можно применять для полигонов. Я думаю, он даже более быстрый, чем barycentric алгоритм (при соответствующей оптимизации), особенно если его применять для многоугольников. Пусть у нас есть на плоскости (!) треугольник ABC. Как определить, лежит ли точка M(x,y) внутри треугольника или вне его? Будем считать, что треугольник задан векторами AB, BC и CA. Если точка M лежит правее вектора AB, правее BC и CA, то она находится внутри треугольника. Для определения, где лежит точка M относительно вектора AB, воспользуемся следующей формулой: j = (y - y0) (x1 - x0) - (x - x0) (y1 - y0) (x0,y0), (x1,y1) - координаты точек А и B соответственно. Если j больше 0, то точка М лежит слева от вектора AB, если меньше 0, то справа от AB, а если j равно 0, то на AB. Таким образом если для всех сторон треугольника (полигона) выполняется неравенство j Ј 0, то точка M лежит внутри треугольника (полигона). Этот метод работает довольно быстро, т.к. часто условие не выполняется уже при проверки первой стороны, и дальнейшие вычисления можно не выполнять. |
||
|
Номер ответа: 14 Автор ответа: Fever Вопросов: 60 Ответов: 808 |
Профиль | | #14 | Добавлено: 20.03.06 10:36 |
| Все ясно. Проекции здесь никто не знает, посему рассказывать и не буду. А легче всего-взять DirectX, который это умеет. | ||
|
Номер ответа: 15 Автор ответа: SLICQ: 277007669 Вопросов: 10 Ответов: 86 |
Профиль | | #15 | Добавлено: 20.03.06 14:34 |
с проекциями тоже мучаться нада....
|
||