Определение с какой стороны от ломаной находится точка

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

В общем, дано: кривая на плоскости (можно использовать трёхмерное пространство), заданая набором точек.
Существует точка (вообще, регулярная сетка из точек).

Требуется - определить с какой стороны от кривой находится точка.
Сторона определяется порядком следования точек. Первый и последний сегменты ломаной образуют прямые, уходящие в бесконечность.

Собственно, нет проблем определить ближайший к точке отрезок и найти с какой стороны от отрезка находится точка.
У меня возникают артефакты, когда между двумя ближайшими (у них общая точка ближе всего к заданной) отрезками находится острый угол. Тогда точка может быть по одну сторону от первого отрезка, но по другую сторону от второго отрезка. Как обработать эти случаи, чтобы они корректно отсчитывались?
В конечном итоге я хочу получить два набора точек из сетки, которые разделены произвольной кривой (без самопересечений, лучи из концов кривой не пересекаются)

Добавлено через 29 минут
Простите за безграмотность, поторопился, не успел отредактировать вопрос.

0

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

0

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

Миниатюры

 

0

Честно говоря, понятнее не стало. . Как я понял у тебя так получается: точка О лежит справа от AC, но слева от AB если идти по пути CAB.
я не силён в топологии, но тут задача о контуре и о нахождении точки внутри контура или снаружи. Нужно рассматривать не один отрезок, а часть контура.

Миниатюры

 

0

Да, проблема именно в этом.
Предположим, у меня всегда известны два отрезка СА и АВ.

Добавлено через 3 часа 47 минут
К сожалению, я её так и не решил. Я пишу, вдруг кто из комьюнити зайдёт в ветку..

0

Aycon, может быть я ошибаюсь, но у тебя перперндикуляры из этой точки на отрезки должны быть одного знака, если точка лежит по одну сторону

0

Решил. Если кому нужно будет - напишу. Спасибо за помощь.

0

Aycon, пиши, кому-нибудь точно пригодится

0

Псевдокод:

Если точка P ближе всего к прямой, на которой лежит один из сегментов (проекция точки Р лежит на сегменте и это наикратчайшее расстояние до кривой), то точка лежит слева от кривой если она лежит слева от этого сегмента.
Иначе:

АВ и ВС это ближайшие отрезки (из искомой линии) к точке P. Точка В общая и является ближайшей из кривой к Р.

Если катчайший угол между векторами ВА и АС больше 90 градусов, то точка Р слева от кривой, если она слева от АВ и слева от ВС.
Иначе:

Если z координата векторного произведения ВА на ВС больше нуля (острый угол смотрит влево от кривой), то точка Р лежит слева от кривой, если она слева от АВ и слева от ВС.
Иначе:

Если z координата векторного произведения ВА на ВС меньше нуля (острый угол смотрит вправо от кривой), то точка Р лежит слева от кривой, если она слева от АВ или слева от ВС.

Во всех остальных случаях точка лежит справа от кривой.

0