Вопрос по algorithm, math – Элегантный «левый» тест для Polyline

13

Given:

(X,Y) coordinate, which is the position of a vehicle. Array of (X,Y)'s, which are vertices in a polyline. Note that the polyline consists of straight segments only, no arcs.

What I want:

To calculate whether the vehicle is to the left or to the right of the polyline (or on top, ofcourse).

My approach:

Iterate over all line-segments, and compute the distance to each segment. Then for the closest segment you do a simple left-of test (as explained here for instance).

Possible issues:

When three points form an angle smaller than 90 degrees (such as shown in the image blow), a more complicated scenario arises. When the vehicle is in the red segment as shown below, the closest segment can be either one of the two. However, the left-of test will yield right if the first segment is chosen as the closest segment, and left otherwise. We can easily see (at least, I hope), that the correct result should be that the vehicle is left of the polyline.

Error scenario

My question:

How can I elegantly, but mostly efficiently take care of this specific situation?

My fix so far:

Compute for both segments a point on that segment, starting from the vertex point. Compute the distance from the vehicle to both of the points, using Euclidian distance Keep the segment for which the computed point is the closest.

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

Существующая кодовая база находится на C ++, поэтому, если вы хотите писать на определенном языке, C ++ имеет мои предпочтения. Спасибо!

[edit] Я изменилсяmy fixот перпендикулярной точки к параллельной точке, так как я думаю, что легче следовать за отрезком, чем вычислять внешнюю нормаль.

@dasblinkenlight Нет, это явно проверено заранее. Полилиния отклоняется, если это так. Yuri
Я думаю, что мне нужно лучшее определение для "слева" от & quot; бывают случаи, когда я не могу сказать, является ли случай «левым»; или "справа от" Ivaylo Strandjev
Я предполагаю, что ломаная линия не является самопересекающейся, не так ли? dasblinkenlight
Если ломаная есть (0,0) - & gt; (10,0) и многоугольник (20, -20), (-20, -20), (-20, 20), (20,20) - многоугольник слева или справа? Именно это я и имел в виду, когда говорил, что вам нужно лучше формализоваться - бывают случаи, когда вы не можете решить, какой из них правильный, если не определите лучше, что слева. Ivaylo Strandjev
@izomorphius Я не совсем уверен, как это формализовать. Если вы хотите, чтобы какая-то аналогия сделала ее более интуитивной, подумайте о ней как об заборе, где начальная и конечная точки простираются до бесконечности. (Конечно, это прямой забор, поэтому он ориентирован определенным образом, как будто вы идете вдоль этого забора в каком-то направлении). Теперь это транспортное средство слева или справа от забора. Это помогает? Yuri

Ваш Ответ

4   ответа
0

ите проверить, находится ли точка (x0, y0) слева от заданной поверхности (вашей полилинии), вам необходимо определить, по какому сегменту тестировать, по ее высоте. Один простой способ сделать это состоит в том, чтобы построить дерево нижней точки каждого сегмента и найти в нем предшественник контрольной точки. Получив этот сегмент, вы можете выполнить тест слева от него: если он слева от обеих конечных точек или между ними на соответствующей стороне, вы возвращаете значение true.

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

Расширение в ответ на комментарий OP:

Обратите внимание, что пример угла в вопросе противоречит первому предположению - ломаная не достигает высоты точки поиска.

Один из способов осмысления моего метода состоит в том, чтобы отсортировать сегменты по вертикали, а затем выполнить итерацию по ним, сравнивая y-координату вашей точки с сегментами, пока ваша точка не окажется выше нижней конечной точки и ниже более высокой конечной точки. Затем используйте конечные точки s, например, чтобы выяснить x-перехват в данном y. Если точка имеет более низкую координату X, она находится слева, а если она имеет большую координату X, то она справа.

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

Use a balanced search tree to find the right segment instead of iterating through a sorted list, to bring the time from O(n) to O(log n) Reconceptualize the search as finding the intersection of the polyline and the horizontal line y = y0 through the search point. Then just compare the x value of the intersection against the search point.
Оба ваших предположения в порядке. Они довольно ограничительны, но вклад действительно соответствует этим критериям. К сожалению, я не очень понимаю из вашего поста, как правильно выбрать сегмент. Не могли бы вы предоставить более пошаговый пример для изображения, которое я разместил, может быть? Yuri
1

что я считаю ее мертвой. У меня есть решение, хотя.

However, the left-of test will yield right if the first segment is chosen as the closest segment, and left otherwise.

Вы использовали слегка двусмысленный язык. Я собираюсь использоватьsegments говорить о отрезках в полилинии иquadrants говорить об областях, разграниченных ими. Таким образом, в вашем случае у вас будет красныйquadrant который, кажется, справа от одногоsegment и слева от другого.

Если тест слева дает разные ответы для разных сегментов, вам следует повторить тест на самих сегментах. В вашем случае у вас есть:

The quadrant is on the RIGHT of the first segment The quadrant is on the LEFT of the second segment

Оба сегмента расходятся во мнениях о том, где находится квадрант, поэтому вы проводите еще два теста устранения неоднозначности:

The second segment is on the RIGHT of the first segment The first segment is on the RIGHT of the second segment

Это позволяет нам сделать вывод, что второй сегментin between первый сегмент и квадрант, поскольку каждый из этих двух элементов находится на другой стороне второго сегмента. Следовательно, второй сегмент «ближе» к квадранту, чем первый, и его ответ на левый-правый тест следует использовать как правильный.

(Я почти уверен, что вы можете выполнить только один из двух тестов на устранение неоднозначности, я поставил оба для ясности)

Ради полноты: я считаю, что это решение также учитывает ваши требования эффективности и элегантности, поскольку оно использует тот же метод, который вы использовали с самого начала (слева от теста), поэтому оно удовлетворяет всем указанным условиям: это изящно, это эффективно, и это заботится о проблеме.

1

где M достаточно велико. Вы можете считать, что все находится в квадрате [-M, M] x [-M, M], разделите квадрат своей ломаной линией, и теперь у вас есть два многоугольника. Затем проверить, находится ли автомобиль в заданном многоугольнике, можно очень просто с помощью углов.

Я считаю, что ваша первая точка и ваша последняя точка имеют M там координат. Вам может понадобиться добавить некоторые из этих точек, чтобы иметь многоугольник: (-M, -M), (M, -M), (M, M) и (-M, M).

Если у вас есть многоугольник слева от ломаной, сложите углы O & # x108; P, где O - фиксированная точка, C - автомобиль, а P - точка многоугольника. Если сумма равна 0, то автомобиль находится за пределами многоугольника, иначе он находится внутри.

Я думаю, что вы меня не понимаете (возможно, из-за того, что мой английский не идеален). Если ваша ломаная линия конечна (и именно так я понимаю вашу проблему), как вы можете сказать, что машина находится слева или справа? ?
Извините, но я не согласен. Тот факт, что я не сказал вам, что я определяюon the line какleft, или жеrightили, может быть, даже значениеunknown не делает это двусмысленным, неполным, может быть. Я только что опубликовал очень специфический сценарий, для которого я ищу элегантный метод. Как видите, у меня уже есть исправление, которое работает. Проблема в том, что мне не нравится сам метод, так как он кажется обходным путем для хорошего геометрического доказательства. Yuri
Это звучит как верная альтернатива моему решению. Тем не менее, вы чувствуете, что это легче реализовать? Если так: Не могли бы вы дать еще несколько объяснений. Я не могу использовать внешние библиотеки из-за политики. Yuri
Хорошо, тогда пусть бесконечность = M, где M достаточно велико. Вы можете считать, что все находится в квадрате [-M, M] x [-M, M], разделите квадрат своей ломаной линией, и теперь у вас есть два многоугольника.
Я отношусь к первому и последнему сегменту полилинии так, как будто они расширены до бесконечности. Yuri
0

можно ли соединить последнюю и первую вершины вашей полилинии, чтобы она стала многоугольником? Затем вы можете выполнить простую внутреннюю / внешнюю проверку, чтобы определить, находится ли транспортное средство слева / справа от линии (этот курс зависит от направления многоугольника).

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

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

Похожие вопросы