CityObjects in sorted order

[clausnagel]

Sometimes it is useful to sort city objects by their thematic (or spatial) attributes such as height, address or name. The OGC WFS 2.0 interface, for instance, allows clients to request features in a sorted order using the <fes:SortBy> element of query expressions. Formats like GML or GeoJSON have FeatureCollections that are defined as arrays and thus preserve the order of the contained features.

The "CityObjects" property in CityJSON is a JSON object and thus an unordered set. As a consequence, JSON libraries are free to rearrange the order of the elements.

I am struggling with this in the context of the 3DCityDB WFS, which is capable of serving CityJSON data. If a client requests city objects in a sorted way, the order gets lost in the CityJSON output. My current hack is to add a "sequenceId" attribute to each CityObject so that a client could potentially rebuild the original order. It would be easier for the client to just read the objects from the file and be sure they are properly ordered.

Of course, the current "CityObjects" property makes it easy to programmatically access city objects by their ID. Well, just wanted to point to this issue and start a discussion.

[hugoledoux]

The solution I do not have, and I do like that City Objects can be indexed by their IDs.

The only way to do this with the current CityJSON structure is indeed like you mention having a "sequenceID" property for each CO.

But notice also that depending which language you use, a dictionary is implemented differently:

• Python before v3.5 (I believe) implemented built-in dictionary with a hash (thus O(1) access; but order of keys is not guaranteed), but they switched to a red-black tree since then and now the order of insertion can be preserved (but with O(log n) access).
  • in C++, you have std::map (order kept) and the std::unordered_map (hash), and your JSON library should allow you to decide which you want

Of course that solves the issue only for your WFS and not for everyone, but that's a start I guess

[clausnagel]

Well, maybe another solution would be to store the order of the city objects as part of the "metadata" object in the CityJSON file. For instance, a new property like "order" could be added to "metadata", whose value could be an array of city object IDs.

An implementation could then choose to simply iterate over this array and access the corresponding city objects via their ID in "CityObjects". Simple enough. Other implementations could choose to completely ignore this metadata property.

Of course, the current CityJSON Extension mechanism already allows for injecting additional attributes such as "order" to the root of the document. But then this would not be part of the specification.

[kenohori]

The second solution seems a lot better IMHO. It is much easier to iterate over an "order" array than to force users to build it from the "sequenceId"of every CityObject (and then iterate over it). It's also more compact 😉.

@hugoledoux, if I'm not mistaken, I think there's a small confusion here. std::map keeps the items ordered based on the order of the keys (as opposed to the insertion order). There's nlohmann's fifo_map though.

[hugoledoux]

duh, of course, my mistake.

But Python from 3.6+ has changed the behaviour to keep the insertion order (not with a red-black tree, but with two different data structures; details there) but it's not guaranteed to be always like this. There are 2 containers: dict (no guarantees it seems), and OrderedDict where the order is guarantee. (this was more a note to myself for the future than anything else)

But the question is: should we add an "order" to the metadata? I am a bit against it since it's not really data about the data, but data about the file. Adding a new property to the file is a better idea, but should it be documented and in the schema? Nothing prevents you from adding an "order" property at the root (just a warning is thrown by cjio), and then the issue is solved. But I am not against adding it to the schema, but v1.0.1.

One question arises: should only top-level city objects be listed? All of them? What is the list doesn't contain all of the city objects?

[clausnagel]

Yep, good questions. At least for WFS, sorting is applied only to those feature types that are requested by the user. For instance, if the user requests buildings, then the top-level COs of type "Building" would be sorted but not their children such as installations.

Seems like an "order" property would require metadata itself, like for example which sort keys were applied, which COs are affected, ...

I use citygson (Java) for reading/writing CityJSON, and it preserves insertion order for "CityObjects" and thus offers predictable iteration order. So in the CityJSON response of the WFS the COs are in fact presented in their sort order. I am more worried about the clients consuming the response, which are not under my control.

Well, for the time being, I will go on with this and the "sequenceId". No need for bringing something into v1.0.1 which might need more thoughts.

[liberostelios]

I think this raises a bigger question on how CityJSON can be used for data exchange purposes. From my perspective, until now CityJSON focused more on how to act as a "static" data storage and less as a "dynamic" data exchange format.

Maybe for the future there should be a goal set to incorporate data exchange characteristics in the specification, which can have their own dedicated property (e.g. "exchange_metadata"). This could start by having the "order" array described here, but in the future it can be enriched with things like tiling information (see #18) and other exchange-related information meant for web services.