Ахтунк... Задачка. Геометрия. 3 класс.
I
Ifgen
Только разбить на выпуклые сложная задача на самом деле :-)
r
rasso
Только разбить на выпуклые сложная задача на самом деле
В чём сложность?
V
Vаnо
какая муть с лучами(хотябы по тому что лучь может пойти по одной из сторон многоугольника, и тогда точек пересечения будет бесконечное моножество мощьностью континум.. хы так вроде оно назвалось).. проще проинтегрировать и узнать площадь n угольника, далее интегрируем и суммируем площади
треугольников (X_i,Y_i)(X_i+1,Y_i+1) (Х0,Y0) где i пробегает от 1...n-1 из первого выичитаем второе если 0 то внутри, если не 0 то снаружи, и все это делается аналитически....
I
Ifgen
В чём сложность?
Предложи простой способ, может я туплю конечно...
Я что-то не могу
I
Ifgen
какая муть с лучами(хотябы по тому что лучь может пойти по одной из сторон многоугольника, и тогда точек пересечения будет бесконечное моножество мощьностью континум.. хы так вроде оно назвалось).. проще проинтегрировать и узнать площадь n
угольника, далее интегрируем и суммируем площади треугольников (X_i,Y_i)(X_i+1,Y_i+1) (Х0,Y0) где i пробегает от 1...n-1 из первого выичитаем второе если 0 то внутри, если не 0 то снаружи, и все это делается аналитически....
С лучом нужно аккуратно учесть граничные случаи, об этом писал уже кто-то выше. Но это не муть, а одно из самых разумных решений задачи, если это программировать . А твой вариант тоже имеет граничные случаи. Например точка лежит прямо на стороне n-угольника или в вершине. Там сложно о треугольниках тогда говорить становится :-) А во вторых это для невыпуклых не будет работать, можно такой невыпуклый нарисовать и так точку поставить, что сумма площадей треугольников будет больше, чем площадь n-угольника, а точка при этом внутри. Например на первом рисунке в данной теме поместить точку внутрь поближе к точке (x1,y1)
[Сообщение изменено пользователем 25.07.2007 19:33]
V
Vаnо
С лучом нужно аккуратно учесть граничные случаи, об этом писал уже кто-то выше. Но это не муть, а одно из самых разумных решений задачи, если это программировать . А твой вариант тоже имеет граничные случаи. Например точка лежит прямо на стороне
n-угольника или в вершине. Там сложно о треугольниках тогда говорить становится А во вторых это для невыпуклых не будет работать, можно такой невыпуклый нарисовать и так точку поставить, что сумма площадей треугольников будет больше, чем площадь n-угольника, а точка при этом внутри
уел.. подумал..
1)граничные условия роли не играют при интегрировании есои точка попадает на одну из граней, то интеграл от этого треугольника будет 0
2) невыпуклый.. дай подумать... мысль пришла..
смотрим углы между вектором A (X_i,Y_i)(X_i+1,Y_i+1)
И B(X_i,Y_i)(X_i-1,Y_i-1) больше 180 градусов(это можно сделать програмным образом) оставляем меньше обрезаем массив поскольку многоугольник вогнутый. таким образом получаем несколько многоугольников которые будут уже выпуклыми а далее применяем способ выше...
Ш
ШУМный
блин )) пойду тоже в программисты )) думал минуты полторы лучи, лучи - вы потом заколебетесь учитывать всякие исключения.
проще надо быть - есть 2 точки. сможете обределить "справа" или "слева" находится искомая красная точка ? (сможете - синусы-косинусы рулят). ну и так со всеми прямыми - в конце получите гарантированно верный ответ, где лежит нужная вам точка ))
проще надо быть - есть 2 точки. сможете обределить "справа" или "слева" находится искомая красная точка ? (сможете - синусы-косинусы рулят). ну и так со всеми прямыми - в конце получите гарантированно верный ответ, где лежит нужная вам точка ))
V
Vаnо
проще надо быть - есть 2 точки. сможете обределить "справа" или "слева" находится искомая красная точка ?
а если с низу
J
John Dow
блин )) пойду тоже в программисты )) думал минуты полторы лучи, лучи - вы потом заколебетесь учитывать всякие исключения.
проще надо быть - есть 2 точки. сможете обределить "справа" или "слева" находится искомая красная точка ? (сможете - синусы-косинусы рулят). ну и так со всеми прямыми - в конце получите гарантированно верный ответ, где лежит нужная вам точка ))
проще надо быть - есть 2 точки. сможете обределить "справа" или "слева" находится искомая красная точка ? (сможете - синусы-косинусы рулят). ну и так со всеми прямыми - в конце получите гарантированно верный ответ, где лежит нужная вам точка ))
ПАшо зачед
маленько больше гемороя при впуклом многораннике но точно также описывается
Хотя еще такой вариант... рисуешь это многогранник, и заливаешь его однотонно, потом проверяешь цвет в координатах этой точки если он равен залитому то она внутри если нет то снаружи
Ш
ШУМный
ПАшо зачед
сцуко )) я специально всю тему прочитал - искал, чо ты там предложил )) в итоге сам написал
Хотя еще такой вариант... рисуешь это многогранник, и заливаешь его
однотонно, потом проверяешь цвет в координатах этой точки если он равен залитому то она внутри если нет то снаружи
ну мы ж с математической точки зрения подошли )) ушлость на потом оставим
Ш
ШУМный
а если с низу
кавычки видим, да ?
превед, третьеклассник
J
John Dow
сцуко )) я специально всю тему прочитал - искал, чо ты там предложил )) в итоге сам написал
а я пля работал..вот только дома в тему залез
Ш
ШУМный
а я пля работал..вот только дома в тему залез
не верю был я у тя недавно - как-то не сильно ты трудился
J
John Dow
а если с низу smoke
то наклоняем оси:-)
I
Ifgen
в конце получите гарантированно верный ответ, где лежит нужная вам точка ))
Непонятно (с) Изложи как получим-то в конце концов :-) Ну и что такое справа или слева тоже непонятно :-) Ну и если ты борешься за отсуствие граничных случаев, то как быт когда лежит на одном уровне с
а)вертикальной линией - стороной многогранника
б)горизонтальной
Так что до зачета пока далеко :-)
I
Ifgen
рисуешь это многогранник, и заливаешь его однотонно, потом проверяешь цвет в координатах этой точки если он равен залитому то она внутри если нет то снаружи
Ты вычислительную сложность заливки всего многогранника по сравнению с лучом вообще представляешь? :-)
Заливать это копец. Очень долго, не всегда возможно (у тебя устройство без экрана скажем) и главное, просили решить математически :-)
Ш
ШУМный
Непонятно (с) Изложи как получим-то в конце концов
а код на Си те не предоставить ? отлаженный ? не ?
Так что до зачета пока далеко
а программисты 1С все поняли
J
John Dow
Непонятно (с) Изложи как получим-то в конце концов Ну и что такое справа или слева тоже непонятно Ну и если ты борешься за отсуствие граничных случаев, то как быт когда лежит на одном уровне с
а)вертикальной линией - стороной многогранника
б)горизонтальной
а)вертикальной линией - стороной многогранника
б)горизонтальной
проверка на принадлежность точки линии у которой известны координаты концов делает на раз
I
Ifgen
проверка на принадлежность точки линии у которой известны координаты концов делает на раз
Отлично, почему тогда применение ее в случае с лучом напрягает, а в данном случае - нет? :-)
J
John Dow
Ты вычислительную сложность заливки всего многогранника по сравнению с лучом вообще представляешь?
эээне помню две или одна комнада на дельфях
I
Ifgen
а код на Си те не предоставить ? отлаженный ? не ?
Нет. Ты объясни как ты воспользуешься информацией. Что она "левее" двух сторон и "правее" третьей скажем. Что отсюда следует-то? Ну и определи что такое все таки "право"
Ш
ШУМный
Ты вычислительную сложность заливки всего многогранника по сравнению с лучом вообще представляешь?
дяденька кодит сразу в машинных кодах ?
J
John Dow
Отлично, почему тогда применение ее в случае с лучом напрягает, а в данном случае - нет?
меня не напрягает.. только Вам извесно что луч это вообщето бесконечная прямая с точкой начал и направлением :-)
I
Ifgen
эээне помню две или одна комнада на дельфях
Команда-то одна, ты время померяй :-) Даже на быстром компе видно иногда на глаз как идет заливка, настолько это тормозная вещь :-)
J
John Dow
если будем выпендриватся сейчас спрошу а в сколькимерной системе и в каком пространстве считаем :-)
Обсуждение этой темы закрыто модератором форума.