Определите, лежит ли набор линий по одну сторону от точки, а другой набор линий - по другую сторону

#computational-geometry

#вычислительная геометрия

Вопрос:

Даны два набора линий A и B, всего n линий и точка p. Как определить, лежат ли линии A по одну сторону от p, а линии B — по другую сторону?

1. Здесь недостаточно информации. Это двухпространство? 3-пробел? Отсортированы ли линии в каком-либо смысле? Кроме того, я действительно не уверен, есть ли какой-либо реальный смысл в идее «на определенной стороне точки»

2. Я бы подумал, что это можно обобщить до N измерений. Учитывая точку, вы всегда можете разделить N-пространство на две части с (N-1)-мерным объектом. (Точка делит линию; линия делит плоскость; плоскость делит трехмерное пространство; и т.д.)

3. Как вы можете находиться «по одну сторону от точки»? Это не имеет смысла. Может быть, плоскость?

Ответ №1:

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

Ответ №2:

Предполагая следующее:
1. Это не домашнее задание.
2. «Пересечение P» означает, что для данного диапазона x, y они не пересекаются. Если мы говорим обо всей оси, то линии в A и B должны быть параллельны относительно их набора, и этот вопрос становится тривиальным.

Тогда простой (хотя и наивный) подход (O (n)) заключается в простом сравнении каждого значения x линий со значением x точки (для вашего заданного y-значения p). Если для заданного y все x-координаты множества A (или B) находятся слева от заданной точки и для заданного x все значения y НЕ выше этой точки, то это множество находится с одной стороны. Запустите тот же тест для другого набора и убедитесь, что все линии находятся по другую сторону. Et viola. 🙂

Надеюсь, это поможет.

1. Могу ли я попытаться немного изменить проблему? Если я предполагаю, что линии являются точками, а точка — линией. Тогда как мне определить, указывает ли A на одной стороне линии p, а B — на другой стороне?

2. Затем вам придется выполнить тот же алгоритм, за исключением сравнения значения x точек со значением x линий для данного y .