PHP / Mongo geoJSON Loop is not valid

Question

I'm passing in some coordinates to mongo to do a geo search. It works fine if the coordinates don't intersect (for instance a figure eight). But when two lines intersect it gives the loop is not valid. Is there any way to find the intersection and split all these loops up?

Note there could be many.

EDIT: I added the sample query and error. Note that I understand why it's happening, I'm just wondering if there is some known way to split those loops up into separate polygon's (some algorithm or within 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: 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

I've added an image of a brute force approach.

Polygon Slicing

• Basically it's doing a look ahead on intersects.
• If it finds one, it swaps out the points so that it stays within a loop.
• It would add the cut off as a "starting point" in some queue.
• When a look ahead goes around and finds it's own starting point we have a loop.
• Then keep going through the "starting point" queue until it's empty.
• The new set of polygons should contain all separate loops (in theory).

There are some issues with this though, it can get quite expensive going through all these loops. Say a max of 50 points would be about 1275 operations.

Also dealing with wrap around on 0/180 degreee coordinates could be a challenge.

Anyway, I didn't want to spend a whole day on this, I could even deal with a solution that does NOT deal with the wrap around condition.

Hoping there is a nice algorithm for this somewhere already I can just pop in (probably has some fancy technical term).

Also would be great if there was a more efficient approach then the brute force look-ahead.

Answer 1

It is because your coordinates are identical that creates an anomaly in the polygon shape: [-97.1788790, 49.9193990] and [-97.2035980, 49.9193990]. In your code remove or change any of the duplicate coordinate,

"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]
]]

Answer 2

As I mentioned in comments the better tool to query spatial data would be to use PostGIS.

For example PostGIS have the ST_validReason() to find the problem with polygon and a st_makevalid to fix but if this is not an option then I would create a service available to your PHP script with shapely python library https://github.com/Toblerity/Shapely

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

The first premise of Shapely is that Python programmers should be able to perform PostGIS type geometry operations outside of an RDBMS

Certainly shapely is a popular tool, and you should get future help with in on StackOverflow or gis.stackexchange.com from more experienced users

I think the problem you are trying to solve is not as trivial as it sounds.

So I would perform following steps:

1 Find how to do it with shapely

similar questions: Splitting self-intersecting polygon only returned one polygon in shapely in Python

2 create a simple php service which will pass query details to python script

3 Shapely will not prevent the creation of invalid polygon, but exceptions will be raised when they are operated on. So basically on such exception, I would call the script from step 1.

If this is just for one of query, I would just use QGIS software ( import points as CSV, create a new shapefile layer ( of type polygon ), and use Numerical vertex edit plugin )

update

I think the polygon should be fixed by the tool that created it so in this case, it should be a user. Maybe you fix that problem by looking from a different angle and if the shape is coming from the user and is drawn in GoogleMap in your app maybe enforce no intersection during drawing.

Found also this Drawing a Polygon ( sorting points and creating polygon with no intersection )