Je passe des coordonnées à Mongo pour faire une recherche géographique. Cela fonctionne bien si les coordonnées ne se croisent pas (par exemple un huit). Mais lorsque deux lignes se croisent, cela donne le loop is not valid . Existe-t-il un moyen de trouver l'intersection et de diviser toutes ces boucles ?
Notez qu'il peut y en avoir plusieurs.
EDIT : J'ai ajouté l'exemple de requête et d'erreur. Notez que je comprends pourquoi cela se produit, je me demande simplement s'il existe un moyen connu de diviser ces boucles en polygones séparés (un algorithme ou dans Mongo).
Une requête :
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]
]]
}
}
}
});Erreur :
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
J'ai ajouté une image d'une approche par force brute.
- En fait, il s'agit d'une anticipation sur les intersections.
- S'il en trouve un, il échange les points de façon à rester dans une boucle.
- Il ajouterait le seuil comme "point de départ" dans une certaine file d'attente.
- Lorsqu'une anticipation fait le tour et trouve son propre point de départ, nous avons une boucle.
- Puis continuez à parcourir la file d'attente du "point de départ" jusqu'à ce qu'elle soit vide.
- Le nouvel ensemble de polygones devrait contenir toutes les boucles séparées (en théorie).
Cette méthode présente toutefois quelques inconvénients, car elle peut s'avérer assez coûteuse en raison de toutes ces boucles. Disons qu'un maximum de 50 points correspondrait à environ 1275 opérations.
De même, la gestion de l'enveloppement sur les coordonnées 0/180 degrés pourrait être un défi.
Quoi qu'il en soit, je ne voulais pas passer une journée entière sur ce sujet, je pourrais même m'occuper d'une solution qui ne traite PAS de la condition enveloppante.
J'espère qu'il existe déjà quelque part un bon algorithme pour cela, que je peux simplement utiliser (il y a probablement un terme technique sophistiqué).
Ce serait également formidable s'il existait une approche plus efficace que le look-ahead par force brute.
