Расстояние от точки до полигона

[Sneaks]

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

[Mikle]

И имеем полигон с 3мя известными точками.

То есть даже не полигон, а именно треугольник?
Всё просто, сначала ищем три величины, расстояния от точки до стороны треугольника при условии, что проекция точки на прямую, содержащую сторону, попадает на саму сторону.
Меньшее из расстояний и будет ответом, расстояние ищем в направлении "наружу", получив отрицательный ответ - игнорируем, если он отрицательный для всех трёх сторон - точка лежит внутри треугольника.
Если ни одна сторона не прошла проверку на то, что "проекция точки на прямую, содержащую сторону, попадает на саму сторону", то ищем расстояния от точки до вершин треугольника, ответом будет меньшее.
Это для 2D случая, для 3D - вначале проверяем, что проекция точки на плоскость, содержащую треугольник, лежит внутри треугольника, если да, то ответ - это расстояние до этой плоскости, нет - переходим к тому же алгоритму, что и в 2D случае.
Какой из этих этапов вызывает сложность?

[goldexer]

Теорема Пифагора — одна из основополагающих теорем евклидовой геометрии, устанавливающая соотношение между сторонами прямоугольного треугольника: сумма квадратов длин катетов равна квадрату длины гипотенузы. Иными словами, две любые точки с известными координатами, образуют прямоугольный треугольник с третьей «нулевой» точкой. Я думаю выводы сделать проще простого. Если всё же нужна формула, то вы, парень, чемпион ленивец.

Да, Mikle, я чуть-чуть не успел.

[Sneaks]

с чего Вы взяли что образуется именно прямоугольный треугольник?

[Mikle]

с чего Вы взяли что образуется именно прямоугольный треугольник?

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

[goldexer]

с чего Вы взяли что образуется именно прямоугольный треугольник?

Докажи мне обратное...

Гипотенуза треугольника и будет искомой величиной.

[Sneaks]

Ребят спасибо за активность, но похоже я реально тупой.
вот картинка, как мне доказать что красная линия находится ближе к черной точки?
Если по майклу то перпендикуляр не падает не на одну их них - т.е. мерим по ближайшей точки. По ней они равны.
Годэксер, да был не прав, я не понял какую нужно было "нулевую" точку брать, но и по твоей системе не все линии он будет считаь правильно. Сейчас забабахаю еще одну картинку и скину

[Mikle]

перпендикуляр не падает не на одну их них - т.е. мерим по ближайшей точки. По ней они равны.

А разве не так?

[Sneaks]

немного перерисовал картинку. Но они жа визуально явно не на равной удаленности от точки. Красная ближе а вот как это доказать?
Если делать прорисовку "от дальней к ближнему" относительно точки, то зеленая должна быть первой а красная вторая. Как это доказать цифрой ума не приложу. Пока греется мысль - пустить равный вектор, от ближайшей точки в сторону второй, у обоих линиях, с равной длинной, не важно какой, скажем 10 попугаев, и от этой точки измерять расстояние до заданной точки. Но это систему будет работать только в данной задачи, если они будут парралельны, и стоять одна за одной, то нужно мерить по длине перпендикуляра. Сейчас попробую набросать посмотрю что получится.
Но один фиг мне это решение не нравится, все как то через жопу. Я просто думал что задача то в принципе простая, и решение, я думал, уже давно имеется

[Mikle]

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

[Sneaks]

да вот главная беда состоит в том что даже до центра получается что красная дальше

[Mikle]

Если делать прорисовку "от дальней к ближнему" относительно точки, то зеленая должна быть первой а красная вторая. Как это доказать цифрой ума не приложу.

Кажется понял. Ближе та, которая заслоняет. Верно?
Но это нерешаемо - представь, что линии пересекаются.
Даже если пересечение запретить, есть такой вариант:

[goldexer]

Да не вопрос. Смотри:
Первым делом, тебе необходимо задавать систему отсчета. То-есть хотя бы критерии, по которым для тебя «дальше» значит «дальше»

Конкретно в этом случае ,зная координаты обоих линий и построив треугольники, просто сравни углы относительно интересующей тебя оси. Больший угол будет принадлежать дальней линии, если, только точка с которой начинается линия дальше первой и наоборот. Например:


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

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

[Sneaks]

Спасибо.
Дело в том что у меня это не - именно эта задача. Отрезки могут лежать в хаотичном порядке, и не обязательно иметь общую точку. Но с ними все просто и понятно, у них разное расстояние как ты не считай, но возможен вариант что они имеют общую точку, и тогда и начинается свестопляска. Проверять каждую линию с всеми реально, но это убийство ресурсов, вот и думал что это все давным давно решили за меня, а я просто не могу найти это для себя решил - если нет перпендикуляра, то буду кидать линию от ближайшей точки по направлению с равной длиной. И мерить уже от дальней точки моей теоретической линии до точки.

[Mikle]

Дело в том что у меня это не - именно эта задача.

Так, всё-таки, какова ТА задача? Соответственно каков критерий "дальше-ближе"?
А то сначала было так:

второй день мучаюсь с простым вопросом - как узнать расстояние от точки до полигона?
Может не коректно написал. Необходима именно формула как считать. Мы имеем точку. И имеем полигон с 3мя известными точками.

А теперь про полигон забыли вообще.
Что нужно и для чего?

[Sneaks]

если решу как делать с отрезками то на полигон это будет легко перенести.
Если в 3д, то моя система будет работать так: узнаем ближайшую точка в полигоне до точки, назовем ее камера, потом находим центр полигона, от ближайшей точки в полигоне кидаем отрезок в сторону центра полигона, длинной в 1 единицу. и потом измеряем расстояние от дальней точки этого отрезка до камеры.

[Mikle]

если решу как делать с отрезками то на полигон это будет легко перенести.

Что "это"? Какой критерий? Какой смысл ты вкладываешь в понятие "ближе"? Я уже привёл три разных критерия.

[Sneaks]

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

[Mikle]

узнать кто кого заслоняет.

Тогда повторяю - это нерешаемая в общем случае задача, я привёл конкретный пример, где все заслоняют всех по кругу, это даже без пересечений:


Именно потому, что это нерешаемо, в 3D изобрели порталы, Z-буфер и прочие обходные пути.

[Sneaks]

да, збуфер решает мои проблемы, но он мне пока не по карману

[goldexer]

Тут по форуму был проект с полноценной 3D графикой абсолютно со всеми плюшками. Причем на моем старом 1,4ГГц одноядерном процессоре выдавал в максимальной загруженности 16 FPS.Всё софтверно, только перевод пикселей на экран за счет DirectDraw был. Может стоило бы тебе его поковырять? Повторяю, полноценная графика со светом, тенями, сглаживанием, загрузкой моделей QuakeII.
Mikle, может подскажешь где он сейчас лежит? Там ещё QDLL на C была в комплекте.

Ещё был проект с чайником и цветочком на боку. Тоже вроде с освещением и плюшками.

О, кстати:
http://algolist.manual.ru/graphics/3dfaq/index.php Вот отличный ресурс. Не форум, чисто теория с образцами алгоритмов.

Mikle на графике «собаку съел», поэтому может уже перестанешь стесняться и расскажешь о своем проекте более глобально. Например: делаю софтверную игрушку для мобильных устройств с 3D графикой, есть такие-то задачи...
Писать за тебя, конечно, никто не будет, но здесь есть люди с большим опытом за плечами, форум начинался ещё во времена, когда спрайтовая псевдо-3D графика Diablo2 заставляла людей выпучивать глаза, ведь делали её на P2 266Mhz 32MB RAM 16MBVideo. И уже тогда не тормозила. А переплюнули только сейчас. А ты говоришь z-buffer тебе не по карману. Видали и похуже.

Вот на 8-битном микроконтроллере Atmega2560 с 8КБ RAM, 16Mhz частотой, блочной видео-памятью пополам с RAM нужно запихивать цветные пиксели в 320x240 экран, считать графику, общаться по CAN и диагностироваться по UART, выдавать шесть, включая комплементарные, каналов ШИМ, мониторить блютуф и вай-фай шилды, не считая туеву хучу показаний датчиков+нажатия клавиш, вот это очень сложно. Тут берешь в руки 32-битный STM32 с 72 MHz и 20КБ RAM как студент стипендию - жируем.
Рассказывай, где там у тебя z-buffer «не по-карману»

Исправлено: нашел чайник Sr3D http://bbs.vbstreets.ru/viewtopic.php?f=6&t=44375#p6767389

[Sneaks]

Если честно - то я изобретаю велосипед. Нужно было сделать визуализацию простенького 3д. С чем я справился. Там были менюшки и этого не требовалось. Но эта тема стала интересной, ни какой конечной задачи не поставлено, просто появилась возможность и интерес узнать как работает этот самый 3д изнутри. Для себя решил сделать боле менее законченную версию и уйти с этого неправильного пути и начать разбираться с ДХ.
За материал спасибо, вот сижу изучаю

[Sneaks]

Еще раз спасибо за материал. Жаль что я его не видел лет 10 назад))
По используемой мной технологии, как там ее назвали, художника. Написано все просто: берем среднюю удаленность. Что собственно я и делал, но она плохо работает.
А материал просто отменный, как раз все то что я сам изобретаю методом тыка и догадок, там все аккуратно и по полочкам изложено. Я просто в восторге))