Should geom::Polygon.points be closed or not?

[michaelkirk]

I wanted to test out some new georust/geo features in the context of abstreet, and consequently I've been spelunking in abstreet::geom.

I ran into some inconsistencies while trying to roundtrip some abstreet::geom::Polygyon to/from geo::Polygon - it resulted in some corrupt rendering like this:

My unverified hunch is that this some problem with one or more of:

• a mismatch in the points array and the precomputed triangulation indices
• an issue with the vertex uploading assuming closed vs open
• an issue with earcutr assuming closed vs open

While digging into that, I noticed that some (but not all) of the abstreet:geom::Polygon.points are closed. Do you have any strong feelings on whether abstreet::geom::Polygon.points should be closed?

Full disclosure is that more broadly I'm interested in making abstreet/geom more semantically consistent with georust/geo, in hopes of make future inter-op easier, but I'm also aware that these are the kinds of changes with no immediate benefit that could have a long tail of bugs in a system which is more or less currently working.

[dabreegster]

Do you have any strong feelings on whether abstreet::geom::Polygon.points should be closed?

The intention is for them to be. But a flat list of points for a polygon with holes is meaningless -- to be more clear, Polygon.rings are all closed. The storage tries to be clever and avoid repetition right now -- per https://github.com/a-b-street/abstreet/blob/193672f19f4c288b4f8df0d3045c02f6ed8c0265/geom/src/polygon.rs#L66, if the polygon only has an exterior ring, then rings will be None and the points should be closed. If there are holes, then the points field is meaningless (it'll be all the points in the exterior ring, then each hole's points appended). The points() method should only return the exterior points, and they generally should be closed.

But all of the guarantees depend on how the Polygon is constructed. The "good" cases are with_holes, from_geojson, etc. There are a handful of callers of buggy_new where all we try to do is render. What's probably happening here is precomputed, where that guarantee breaks down. This code path uses usvg and then lyon to tesellate polygons. Last I checked, the order of points it hands back aren't usually closed -- probably SVGs we render often have holes, so we'd have to figure out how to get that out of lyon anyway.

Full disclosure is that more broadly I'm interested in making abstreet/geom more semantically consistent with georust/geo

Awesome! That's what I'd love to see too. A next (big) step would be to try to make geom::Polygon just store geo::Polygon and wrap APIs over it. Only rendering needs the triangulation, so the one caller of raw_for_rendering could do something different. There are probably smaller intermediate steps.

In an ideal world, we can make sure every single construction of a polygon happens from closed rings. But in case all we can get out of lyon is a triangulated mesh, I wonder what we should do otherwise.

Also related: the other big geom structure to rethink is PolyLine. It's effectively a geo::LineString that tries to enforce extra invariants, but that validation has been causing more and more problems lately. I've been working with GPS trajectory data lately where the points double back on themselves in all sorts of ways, but still being able to do some PolyLine operations would be nice.

[dabreegster]

My unverified hunch is that this some problem with one or more of:

To test the theory that the problem is usvg + lyon feeding into Polygon::precomputed and not giving points in order or where first=last, try running A/B Street and looking at lanes/roads. That uses PolyLine::make_polygons, which also calls Polygon::precomputed, but there the points definitely are in order and closed

[michaelkirk]

Ah! So the points returned from lyon are likely not even in any particular ordering WRT the winding of the polygon - it's basically just a bag of points that can be triangulated with indices.

It seems pretty unlikely that we'd be able to safely roundtrip that representation with geo.

[dabreegster]

Maybe GeomBatch should have a way to store pretriangulated polygons, and not allow anything to access the Polygon. These cases from lyon should directly use that, and not use geom::Polygon at all. They likely break many of the methods in there now, and there shouldn't be many (any?) callers of those anyway. get_bounds is one of the few valid things to do, and scale/translate transformations.

[michaelkirk]

That sounds plausible! I may (may!) have a go at this tomorrow.

[michaelkirk]

Maybe GeomBatch should have a way to store pretriangulated polygons, and not allow anything to access the Polygon.

I think I'm having a go at something along these lines.

My basic idea was to have two types:

• Polygon for a topologically conventional geometry (something that could feasibly be replaced by geo::Polygon)
• Tessellation for a pre-triangulated entity suitable for rendering

It's going OK, but I think seeing it through could be a very large change. Here's my hack-and-slash WIP if you're curious:
https://github.com/michaelkirk/abstreet/tree/mkirk/tessellation

I think at the end of it, Polygon wouldn't have an indices field at all. And only at the point that you wanted to render the polygon (which you might not always want to), would you use earcutr to turn the Polygon into a Tessellation.

GeomBatch then, is a collection of Tessellations, not Polygons. I haven't gotten far enough to know if there will be any show stoppers with this approach, but it does seem like it's going to have far reaching implications that I might not have time to see through.

Does this approach seem reasonable?

[dabreegster]

Approach sounds perfectly reasonable to me! The difficulties I would anticipate...

• Callers of GeomBatch::consume... actually, scratch that. At a glance, all of them don't need a Polygon
• rotate_around_batch_center currently calls Polygon::rotate_around, which is some pretty simple math that lives outside of geo. Tesselation will need to keep this
• The handful of Polygon::buggy_new callers remain awkward, because some of them aren't just rendering. For example, convert_osm/src/osm_geom.rs tries to get Polygons to store for areas and buildings. (Mostly those are just rendered later, so you could maybe argue map_model could just store that instead?) But also, it might be fine to just start failing here if the multipolygons we're scraping from OSM aren't valid rings. I don't entirely remember what motivated adding this in; it's likely some more fundamental bug handling multipolygons.

So actually this hopefully shouldn't be too bad...

[dabreegster]

If it's OK, I'm going to pick up your branch and try to push through. I think the migration steps could be:

1. Introduce Tessellation, convert Polygon to it, use it for rendering
2. Replace current uses of Polygon::buggy_new and Polygon::precomputed with it
3. Make geom::Polygon just wrap geo

In your branch you were very carefully changing the API for places that directly construct a tessellation, but I won't attempt that until maybe a step 4. It's a huge refactor.

[dabreegster]

I got too ambitious as usual! https://github.com/a-b-street/abstreet/tree/geo_polygon_too_quickly is a start, but I realized some more complications:

• Circles and polylines becoming polygons should maybe still have a way to feed the pre-triangulated result forward, for performance. It's unnecessary to go through earcutr. Need to think through this, and also measure to see if it's actually going to be a problem.
• All of the places unioning and intersecting polygons also need to be done carefully, because the result might not be a valid geo::Polygon. geo::Polygon kind of pretends multipolygons are single polygons sometimes, which is weird.

I do see a few smaller steps to peel off first, to make the migration easier. I'll see if I can get rid of a few places that construct geo::Polygons in strange ways.

[michaelkirk]

geo::Polygon kind of pretends multipolygons are single polygons sometimes, which is weird.

Can you expound on this? I'm not sure what you mean.

[dabreegster]

I've got a few steps to remove callers that construct "bad" polygons. Then we can switch to tessellations for rendering, and consider step 3.

Can you expound on this? I'm not sure what you mean.

I'm mistaken. We always transform a geo::MultiPolygon into Vec<geom::Polygon>. I was thinking of geom::Polygon::union, which is just doing something bizarre. I'll whittle away the callers of this one too.

[dabreegster]

Remaining work before the polygon cleanup can be considered done:

• Make polyline outlines be a proper Polygon with an outer and inner ring, then clean up tessellation -> geojson
• Profile the Polygon -> Tessellation code and try out some ideas with earctur
• Revert polygon.center change probably