Астрономия и Геометрия

[MaximusFT]

Задача:
Есть контуры (границы) созвездия
http://www.astromyth.tau-site.ru/Constellations/And.htm
Синие линии. Можете обратит внимание что они собой представляют неправильный многоугольник.
Есть база звезд. Нужно найти вхождения звезд в границу созвездия.

По сути задача сводится к поиску вхождения в неправильный многоугольник.
Может кто-то подсказать алгоритм (желательно с формулами) решения задачи.

[ИСН]

Ладно бы неправильный, но ещё и невыпуклый...
Слушайте, а кто придумал так проводить границы созвездий? Это общепринято? Ведь нелепость же. Надо было через разбиение Вороного.

[Munin]

Вообще-то этот многоугольник проведён по параллелям и меридианам небесной сферы, так что проверка есть просто проверка удовлетворения координат звезды системе элементарных неравенств.

ИСН в сообщении #381173 писал(а):

Надо было через разбиение Вороного.

Есть созвездия, не содержащие ни одной яркой звезды. По Вороному они бы обнулились :-)

[ИСН]

Munin в сообщении #381200 писал(а):

Вообще-то этот многоугольник проведён по параллелям и меридианам небесной сферы

Типа карты западных штатов (Колорадо, Вайоминг особенно). Ну-ну.

Munin в сообщении #381200 писал(а):

Есть созвездия, не содержащие ни одной яркой звезды. По Вороному они бы обнулились

Кто сказал "яркой"? Зафиксируем некий произвольный список звёзд, каких получится, да по нему и разобьём...

[MaximusFT]

Munin
Подскажите где можно почитать чтобы формулы составить... мне на php надо написать.
Заранее премного благодарен.

[Munin]

ИСН в сообщении #381212 писал(а):

Типа карты западных штатов (Колорадо, Вайоминг особенно). Ну-ну.

А чо, рек по небу не течёт, гор не растёт, чего зря мучаться.

ИСН в сообщении #381212 писал(а):

Кто сказал "яркой"? Зафиксируем некий произвольный список звёзд, каких получится, да по нему и разобьём...

Вот такие списки и были в ходу до деления неба на области, и именно из таких списков в эти созвездия ни одной звезды и не попадает.

MaximusFT в сообщении #381213 писал(а):

Подскажите где можно почитать чтобы формулы составить... мне на php надо написать.

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

Если вы ещё учитесь в школе - приношу извинения, могу разобрать подробнее.

[MaximusFT]

Нет в школе не учусь уже 15 лет :) наверное поэтому и обращаюсь к Вам, так как многое забыл... но вариант нашел такой:
брать звезду и находить
1) 2 последовательные точки слева от звезды (причем одна точка должна находиться выше другая ниже)
2) с права
3) сверху (причем одна точка должна находиться левее другая правее)
4) снизу

Если все условия верны - то звезда в контуре созвездия.

Правильный ли алгоритм?

[ИСН]

Ну, если Ваша структура данных такова, что допускает понятие "находить точки", то всё может быть.

[Munin]

Основная идея состоит в том, что вам надо от границ созвездия перейти к набору условий, которым должны удовлетворять точки. Например, вот такой набор условий позволяет проверять принадлежность углу на плоскости:


Аналогично четыре условия, взятые по AND, могут проверить принадлежность прямоугольнику. В данном случае фигура имеет сложную форму границы, и вы должны представить её в виде наложения более простых фигур или неограниченных углов и полуплоскостей:


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