| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Входит ли точка в фигуру? |
| Автор: Ravend 28.6.2006, 14:18 |
| Привет, All! требуется определить входит ли точка в фигуру фигура наиболее похожа на вертикально стоящее куринное яйцо (эллипс со смещенным к низу центром) подскажите как это можно решить? спасибо |
| Автор: skyboy 28.6.2006, 14:47 |
| Ravend, уравнение поверхности есть? Тогда сделать так, чтоб уравнение описывало поверхность с осью эквивалетной оси Z. Берем z-координату точки, которую проверяем. От поверхности отсекаем эллипс на этом уровне и опеределяем, принадлежит ли точка эллипсу. |
| Автор: Ravend 28.6.2006, 15:31 | ||
фигура 2х мерная
вот собственно это и хотелось узнать, в виде формул |
| Автор: maxim1000 28.6.2006, 15:54 |
| как задана граница? (формула, просто на рисунке точками или ещё как-то) |
| Автор: Ravend 28.6.2006, 16:29 |
| собственно первоначальная задача такова, нужно найти точки входящие в окружность с R радиусом (см. рисунок), но при переводе данной окружности к декартовой системе координат, окружность приобретает сходство с 2d-проекцией яйца, возможно я пошел и не тем путем, но мне кажется что нужно искать именно вхождение точек в описанной мной эллипс P.S. очень важно найти входящие точки одной итерацией (вывести формулу) т.к. в дальнейшем эта формула должна подставляться в sql-запрос |
| Автор: skyboy 28.6.2006, 17:21 |
| Ravend, не ясно, почему окружность в декартовой системе координат перестаёт быть окружностью... |
| Автор: maxim1000 28.6.2006, 17:33 | ||||
формула внутренности эллипса простая: sqr(x/a)+sqr(x/b)<=1 (для случая, когда оси эллипса параллельны осям координат) a - длина горизонтальной полуоси b - вертикальной
вот чего-чего, а эллипса там не увидел... вариант (по рисунку) такой: выводим зависимость координат (x,y) от номера делаем 6 линейных неравенств... |
| Автор: chich 29.6.2006, 07:58 |
| по-моему для того чтобы получить ответ на свой вопрос надо его ставить конкретно - что дано, что надо получить. но если я правильно понял до задана окружность с координатами в точке x y и с радиусом R. так зачем же городить огород надо просто проверять если расстояние до центра меньше радиуса, значит точка принадлежит окружности |
| Автор: Ravend 29.6.2006, 10:17 | ||
Вы уважаемый картинку смотрели? приведите изображенную фигуру к декартовой системе координат и посмотрите какая у Вас окружность получится, если Вы мне напишете формулу буду весьма признателен а флудить просьба в другом месте |
| Автор: chich 29.6.2006, 11:12 |
| есть такие же формулы эллипса (см выше), хотя она тоже не нужна если принять за единичный отрезок по оси x 1 а по оси y 2. Тогда ваше так сказать "яйцо" превратится в окружность - все дело в единицах измерения. и по-моему есть еще куча решений вашей задачи,но это самое простое (по-моему даже очень). Можно разделить контур окружности на две части верхнюю и нижнюю и смотреть по графикам - если ниже одного и выше другого то попадает в окружность. и еще есть куча вариантов |
| Автор: Romikgy 29.6.2006, 11:54 | ||||
А вы ? 
 |
| Автор: Ravend 29.6.2006, 12:12 |
| сдается мне, что вы просто не делали преобразования, вот что у меня получается, и убедите меня что это окружность |
| Автор: Romikgy 29.6.2006, 12:21 |
| Из первого рисунка у тебя шестиугольник! Из второго , при такой дискретности, вообще не понятно что. так что сначало имхо надо немного конкретизировать задачу, а уж потом спрашивать, ты спросил про окружность тебе про нее и ответили, на картинках совсем другое  |
| Автор: Ravend 29.6.2006, 12:41 | ||
см. пост №1
упоминание мной окружности относиться к не декартовой системе координат, заметте что там единицей является не квадрат, а гексагон следовательно формула окружности известная нам не подходит поймите, что точка A1(0;1) в этой системе стоит не просто справо от точки A0(0;0), а с право-вверх |
| Автор: skyboy 29.6.2006, 12:53 |
| Ravend, у тебя координаты могут принимать только целые значения? если да и будешь работать с базой, то занеси в таблицу все целочисленные координаты относящиеся к фигуре и проверяй на принадлежность просто выборкой-select. |
| Автор: Ravend 29.6.2006, 14:28 |
| да целочисленные, но к сожалению Вам способ не подходит, т.к. он предусматривает заранее заданный размер фигуры, и соответственно динамически менять диаметр не получиться но спасибо за совет |
| Автор: skyboy 29.6.2006, 15:08 |
| Ravend, сорри за глупый вопрос, но где на этой фигуре диаметр? Добавлено @ 15:11 вообще, не могли бы на пальцах пояснить, как эту фигуру "приводить в декартовы координаты"? |
| Автор: Ravend 29.6.2006, 16:29 |
| ссори если было не понятно, думаю такой рисунок снимет вопрос P.S. фигура представляет собой окружность (возможно изобразил не совсем достоверно) с радиусом R (в данном случае =5), но данные в БД хранятся в виде X:Y, требуется вывести формулу подставив которую в запрос можно было выбирать точки входящие в данную фигуру |
| Автор: Aloha 29.6.2006, 18:12 |
| Ravend Идея такая. Помещаем центр нашего шестиугольного "круга" в начало координат. Перенумеровываем шестиугольники как показано на рис. слева (это можно сделать любым другим способом, главное, чтобы каждый шестиугольник имел уникальный номер). Затем перенумеровываем шестиугольники как показано на рис. справа. Таблицу соответствия храним в БД. Далее, задаемся вопросом, принадлежит ли "кругу", например, шестиугольник №101 и если да, то какой именно "окружности" (слою). По таблице соответствия находим номер нашего шестиугольника на рис. справа – это №75. Далее пользуемся формулой (привожу ее Excel’евский вариант): =ОКРВНИЗ((-1+КОРЕНЬ(1+8*ОКРВНИЗ((A1-1)/6;1)))/2;1)+1 Подставляем в нее 75 (данные для вычисления помещаем в ячейку A1) Получаем в результате число 5 – это искомый номер "окружности" (нумерация начинается с 0). Точно также, например, для шестиугольника №161 получаем по таблице соответствия номер 192, подставляем его в формулу и получаем номер окружности – 8. P.S. Должен отметить, что приведенная формула некорректно обрабатывает №0. Если нужны подробности по формуле – пишите в личку. |
| Автор: Ravend 30.6.2006, 09:46 | ||
| Aloha, спасибо но тоже то выше приводилась формула:
только в ней участвуют центр эллипса и его радиусы, а как здесь учесть точки проверяемые на принадлежность фигуре |
| Автор: maxim1000 30.6.2006, 11:13 |
| предполагается, что центр в нуле если нет - поотнимать его координаты от координат проверяемой точки т.е. получается: sqr( (x-xc)/a ) + sqr( (y-yc)/b ) <= 1 |
| Автор: Ravend 30.6.2006, 11:16 |
| всем спасибо, вроде решение найдено |
| Автор: SoWa 1.7.2006, 14:21 | ||
|
