Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

polygon drawing optimizations at low numerical zoom levels #1409

Closed
spyhunter99 opened this issue Sep 29, 2019 · 5 comments
Closed

polygon drawing optimizations at low numerical zoom levels #1409

spyhunter99 opened this issue Sep 29, 2019 · 5 comments
Assignees

Comments

@spyhunter99
Copy link
Collaborator

@spyhunter99 spyhunter99 commented Sep 29, 2019

Issue Type

[ ] Performance

description

see pr #937 and #906 for reference.

When there is a sufficient quantity of small polygons on screen and the user zooms out, draw speed can drop to a crawl. #937 mitigates this somewhat by enabling and using the feature requested by @MKergall which uses an overlay bounds as a faster mechanism to skip draw cycles on overlays that are not in view. This makes rendering quick if nothing is in view.

i think using the point reducer at lower numerical zoom levels may reduce complex polygons from potentially 1000s of points down to 4 or less, which should help draw speed significantly.

the reduced point set can be cached for panning operations to reducing the recalculation necessary and the cache invalidated on zoom events.

to reproduce...

see pr #937 for esri shape file download link, then import the shape file, specifically the "shapes" within the shape file. after its imported, the performance issue is obvious

@monsieurtanuki

This comment has been minimized.

Copy link
Collaborator

@monsieurtanuki monsieurtanuki commented Dec 2, 2019

I managed to reproduce the poor performances using https://catalog.data.gov/dataset/military-installations-ranges-and-training-areas
A solution could also be to use a PointReducer for pixels too, not only for GeoPoints.
In order to avoid confusion and painful code merge, I'll work on that issue after #1440 is finished.

@monsieurtanuki

This comment has been minimized.

Copy link
Collaborator

@monsieurtanuki monsieurtanuki commented Dec 19, 2019

... and now, #1440 is merged. I can start!

@monsieurtanuki

This comment has been minimized.

Copy link
Collaborator

@monsieurtanuki monsieurtanuki commented Dec 19, 2019

For what it's worth, I've just run some tests on my smartphone. We're talking about 2035 ESRI Polygons, to be displayed in the world map.

Test 1 was the target test, without editing anything.
The very first draw took 3890ms, and the next draw 830ms.
The difference comes from the fact that the first draw initializes data (for instance the projections of GeoPoint into a virtual screen).

Test 2: I removed the actual "canvas.drawPath" call, in order to understand if we are slow computing things or Android is slow drawing Paths.
The very first draw took 3980ms, and the next draw 730ms.
Very similar to test 1, because the population of the Path is already optimized (we remove consecutive duplicates points).

Test 3: I removed the "display this Polygon" calls.
The very first draw took 20ms, and the next draw 30ms.
Same duration. We don't compute data for each draw, and don't even initialize any.

Test 4, 5 and 6 are the same as 1, 2 and 3, but pretending that we use Polylines instead of Polygons.

Test 4.
The very first draw took 4740ms, the next draw 1270ms.
Seems to be slower than with Polygons. A reason may be that Polylines are not optimized for consecutive duplicate points: we add and add single point segments. Polylines get drawn faster than Polygons in general because canvas.drawLines is faster than canvas.drawPath, but in this case there's nothing to draw!

Test 5.
The very first draw took 4390ms, the next draw 980ms.
Slower than test 2, because the consecutive duplicate points case is not optimized: we spend time precomputing and adding useless segments - and in this test we don't display them.

Test 6.
The very first draw took 70ms, the next draw 20ms.
Similar to test 3.

Let's say that drawing involves 3 steps: the init phase (around 3s in those examples), the draw precomputation phase (around 1s) and the actual draw.
What we definitely need to optimize are the precomputation and the actual draw phases.

Suggestions:

  • optimize Polylines when dealing with consecutive duplicate points
  • optimize the init phase (see how)
  • short-circuit the precomputation phase when relevant. For instance, if in the init phase we computed the bounding box, we are able to say very quickly if the polygon is less than n square-pixel big, and then dismiss it as irrelevant for that projection. Perhaps take also into account the density. I'm a big fan of that option!
  • see if it's relevant to use Polygons instead of Polylines for ESRI Polygons (@spyhunter99 what do you think?)
  • pre-reduce the number of GeoPoints for low zoom levels
@monsieurtanuki

This comment has been minimized.

Copy link
Collaborator

@monsieurtanuki monsieurtanuki commented Dec 19, 2019

The first tests are very encouraging ("if the boundingbox is too small, don't even try to display it").
I'll PR soon. It's a quick win. Is it going to be fast enough for you guys, I don't know, but even on my old smartphone the performances are decent.

monsieurtanuki added a commit that referenced this issue Dec 22, 2019
…ed poly is too small

The downgrade management works with 2 methods:
* `PolyOverlayWithIW.setDowngradeMaximumPixelSize(int)` - if the poly projected at the screen is too small (width or height lower than this value), either we don't display the poly or we display a rectangle instead
* `PolyOverlayWithIW.setDowngradeDisplay(boolean)` - should we display the rectangle when the poly is too small?

It can be tested in `SampleShapeFile`.

Deleted class:
* `PathOverlay`, which was deprecated 4 years ago

Impacted classes:
* `BoundBoxTest`: unrelated refactoring
* `Counters`: added a more flexible access to counter features with methods `reset(String)`, `increment(String)` and `get(String)`
* `CustomPaintingSurface`: used the new method `PolyOverlayWithIW.getBounds`; unrelated performance refactoring
* `DefaultOverlayManager`: unrelated display optimization for MapSnapshots
* `LinearRing`: now computing the bounding box ASAP, in method `computeProjected`, which simplifies method `getCenter`; created another version of `getBestOffset`; created method `getCloserValue`; created methods `getBoundingBox` and `clear`
* `LineDrawer`: optimized the display
* `MilestoneLineDisplayer`: fixed a minor unrelated bug, where the last point was added as (X0,Y0), but without a correspnding (X1,Y1)
* `OsmMapShapeConverter`: used method `PolyOverlayWithIW.getActualPoints` instead of deprecated `Polygon.getPoints()`
* `Polygon`: deprecated method `getPoints()`, to be replaced by `PolyOverlayWithIW.getActualPoints`; moved methods `setPoints` and `addPoint` to `PolyOverlayWithIW`
* `Polyline`: deprecated method `getPoints()`, to be replaced by `PolyOverlayWithIW.getActualPoints`; moved methods `setPoints` and `addPoint` to `PolyOverlayWithIW`
* `PolyOverlayWithIW`: added in the `draw` the downgrade management; created methods `setDowngradeMaximumPixelSize`, `setDowngradeDisplay`, `isWorthDisplaying` and `displayDowngrade` for the downgrade management; moved `Polygon` and `Polyline` methods here - `getBounds`, `setPoints`, `addPoint` and `getActualPoints`
* `Projection`: computed `mProjectedMapSize` regardless of the tile size; created method `getWorldMapSize()`
* `SampleOsmPath`: removed the "deprecated 4 years ago" `PathOverlay` sample; refactored
* `SampleShapeFile`: set up the display (downgrade and style)
* `ShapeConverter`: used the new method `PolyOverlayWithIW.getBounds`
* `TileSystem`: deprecated now useless member `projectionZoomLevel`
monsieurtanuki added a commit that referenced this issue Jan 9, 2020
monsieurtanuki added a commit that referenced this issue Jan 9, 2020
feature/#1409 - downgrade mode for PolyOverlayWithIW when the projected poly is too small
@monsieurtanuki

This comment has been minimized.

Copy link
Collaborator

@monsieurtanuki monsieurtanuki commented Jan 9, 2020

Solved by #1459.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.