Ошибка PHP/Mongo geoJSON Loop - программирование

Я прохожу в некоторых координатах к монго, чтобы выполнить гео-поиск. Он отлично работает, если координаты не пересекаются (например, восьмерка). Но когда две прямые пересекаются, он дает loop is not valid. Есть ли способ найти пересечение и разбить все эти циклы?

Заметьте, что может быть много.

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

Query:

db.items.find({
    "address.location": {
        "$geoWithin": {
            "$geometry": {
                "type": "Polygon",
                "coordinates": [[
                    [-97.209091, 49.905691],
                    [-97.206345, 49.918072],
                    [-97.178879, 49.919399],
                    [-97.165146, 49.907903],
                    [-97.164459, 49.892865],
                    [-97.180939, 49.889326],
                    [-97.197418, 49.895077],
                    [-97.200165, 49.902596],
                    [-97.203598, 49.919399],
                    [-97.216644, 49.928682],
                    [-97.244797, 49.927356],
                    [-97.255096, 49.913209],
                    [-97.209091, 49.905691]
                ]]
            }
        }
    }
});

Ошибка:

Error: error: {
    "waitedMS" : NumberLong(0),
    "ok" : 0,
    "errmsg" : "Loop is not valid: [
            [ -97.209091, 49.905691 ]
            [ -97.206345, 49.918072 ],
            [ -97.17887899999999, 49.919399 ],
            [ -97.16514599999999, 49.907903 ],
            [ -97.16445899999999, 49.892865 ],
            [ -97.180939, 49.889326 ],
            [ -97.197418, 49.895077 ],
            [ -97.200165, 49.902596 ],
            [ -97.203598, 49.919399 ],
            [ -97.216644, 49.928682 ],
            [ -97.24479700000001, 49.927356 ],
            [ -97.25509599999999, 49.913209 ],
            [ -97.209091, 49.905691 ]
        ]
        Edges 1 and 7 cross.
        Edge locations in degrees: [-97.2063450, 49.9180720]-[-97.1788790, 49.9193990]
        and [-97.2001650, 49.9025960]-[-97.2035980, 49.9193990]
    ",
    "code" : 2
}

UPDATE

Я добавил изображение подхода грубой силы.

Нарезка многоугольников

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

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

Также рассмотрение проблемы вокруг координат 0/180 градусов может быть проблемой.

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

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

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

"coordinates": [[ [-97.209091, 49.905691], [-97.206345, 49.918072], [-97.178879, 49.919399], // this line [-97.165146, 49.907903], [-97.164459, 49.892865], [-97.180939, 49.889326], [-97.197418, 49.895077], [-97.200165, 49.902596], [-97.203598, 49.919399], // and this one [-97.216644, 49.928682], [-97.244797, 49.927356], [-97.255096, 49.913209], [-97.209091, 49.905691] ]]

Ответ 2

Как я уже упоминал в комментариях, лучшим инструментом для запроса пространственных данных будет использование PostGIS.

Например, PostGIS имеет ST_validReason(), чтобы найти проблему с полигоном и st_makevalid для исправления, но если это не вариант, я бы создал сервис, доступный вашему PHP script с shapely библиотекой python https://github.com/Toblerity/Shapely

http://toblerity.org/shapely/manual.html

Первая предпосылка Shapely заключается в том, что программисты на Python должны быть способны для выполнения операций геометрии типа PostGIS за пределами РСУБД

Разумеется, shapely - популярный инструмент, и вы должны получить помощь в будущем на StackOverflow или gis.stackexchange.com у более опытных пользователей

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

Итак, я бы выполнил следующие шаги:

1 Найдите, как это сделать с эффектным

2 создайте простую службу php, которая передаст детали запроса на python script

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

Если это только для одного из запросов, я просто использую программное обеспечение QGIS (точки импорта как CSV, создаю новый слой шейп файла (типа polygon) и использую плагин редактирования числовых вершин)

Обновление

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

Нашел также этот Рисование многоугольника (точки сортировки и создание многоугольника без пересечения)

Ответ 1

Ответ 2