Учитывая геометрическую полосу движения, как я могу определить путь, по которому идет автомобиль?

Question

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

Диаграмма (это довольно простая, но я думаю, что она передает сообщение):

Я думал о следующем, но я не вижу, чтобы они работали или, по крайней мере, неэффективно:

1. Разбиение его на четырехугольники, или четырехугольники и треугольники,
2. Начните с линии длиной десять, затем вращайте ее, пока ее конечная точка не окажется на равном расстоянии от обеих граничных сторон, и повторите и
3. Для каждого выходного сегмента усредните наклоны обеих граничных сторон.

Я подумал еще о нескольких, но упоминать не стоит.

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

Answer 1

Следующая идея вдохновлена ​​ Динамическая деформация времени (DTW). Это продолжение идеи Shreyas Pimpalgaonkar в комментариях:

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

Вот некоторые детали: Распределение очков не так сложно. Вы можете либо поставить очки каждые х единиц. Или вы можете распределить постоянное количество точек по сегментам. В конце концов, не имеет большого значения, как распределены баллы. Тем не менее, равномерное распределение даст вам лучшие результаты.

Центральная точка - вариант DTW. Основные данные для этого алгоритма - это матрица соответствия, которая говорит вам, насколько дорого сопоставлять одну точку с другой. Для этого вы можете использовать евклидово расстояние двух точек. Если у вас есть эта матрица (она не должна быть полной матрицей; обычно достаточно записей около диагонали; см. Ограничение локальности в статье в Википедии), вы просто решаете проблему деформации с помощью динамической программы.

И, наконец, вы подключаетесь к средним точкам. Вот и все.

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

Вот несколько примеров. Если вам нужны более гладкие пути, вы можете изменить точку, которую вы выбрали на соединительных линиях (вместо средней точки). Вы могли бы, например, оптимизировать параметр интерполяции по отношению к лапласиану сгенерированной линии. Это даст вам линейную систему уравнений, которая позволит вам контролировать гладкость пути. Однако не так-то просто гарантировать, что путь останется внутри полосы движения.

Answer 2

Прежде всего, если вы разработали какую-то часть кода, а затем задайте свой вопрос. Либо только анализ может дать вам много вариантов, это можно сделать с помощью обоих java / python.

Я просто показываю вам простой пример, в котором достаточно подробно описан следящий по пути / полосе, используемый в картах.

private void CarMove(final Marker marker, final LatLng beginLatLng, final LatLng endLatLng, final long duration) {
        final Handler handler = new Handler();
        final long startTime = SystemClock.uptimeMillis();

        final Interpolator interpolator = new LinearInterpolator();

        // set car bearing for current part of path
        float angleDeg = (float)(180 * getAngle(beginLatLng, endLatLng) / Math.PI);
        Matrix matrix = new Matrix();
        matrix.postRotate(angleDeg);
        marker.setIcon(BitmapDescriptorFactory.fromBitmap(Bitmap.createBitmap(mMarkerIcon, 0, 0, mMarkerIcon.getWidth(), mMarkerIcon.getHeight(), matrix, true)));

        handler.post(new Runnable() {
            @Override
            public void run() {
                // calculate phase of animation
                long elapsed = SystemClock.uptimeMillis() - startTime;
                float t = interpolator.getInterpolation((float) elapsed / duration);
                // calculate new position for marker
                double lat = (endLatLng.latitude - beginLatLng.latitude) * t + beginLatLng.latitude;
                double lngDelta = endLatLng.longitude - beginLatLng.longitude;

                if (Math.abs(lngDelta) > 180) {
                    lngDelta -= Math.signum(lngDelta) * 360;
                }
                double lng = lngDelta * t + beginLatLng.longitude;

                marker.setPosition(new LatLng(lat, lng));

                // if not end of line segment of path 
                if (t < 1.0) {
                    // call next marker position
                    handler.postDelayed(this, 16);
                } else {
                    // call turn animation
                    nextTurnAnimation();
                }
            }
        });
    }