Voronoi diagram or similar in Altair

[ChristopherDavisUCI]

This is probably more of a question for Vega-Lite, but I thought I would try here first.

Is there any natural way (even with most of the work happening outside of Altair) to make a chart like a solid version of this one: Open the Chart in the Vega Editor?

I'm trying to illustrate the decision boundary for a logistic regression classifier. Here what I did was just artificially make a grid of points and color them using the classifier.

Even a simpler picture like where there is a diagonal line in the xy-plane and I want the half-plane on one side of the line to be colored one way and the half-plane on the other side to be colored a different way, I don't think I would know how to produce in Altair. (If it were a vertical line or a horizontal line, I think I could accomplish this using mark_rect.)

Here is an example of the type of end result I would like using Matplotlib.

If you think I should instead ask at Vega-Lite, is there any information you think I should add to make my question more clear?

Thanks!

[joelostblom]

There are these two examples, not sure how generally applicable they are:

• https://observablehq.com/@manzt/u-s-airports-voronoi-in-vega-lite
• https://observablehq.com/@manzt/world-airports-voronoi-in-vega-lite

You can see the code by clicking to edit the cell the map is in. There is also a voronoi transformation in Vega https://vega.github.io/vega/docs/transforms/voronoi/ (but not VegaLite I think), which I believe is used for interactions in VegaLite that are using nearest=True. There is also this example that might be useful vega/vega#799

[ChristopherDavisUCI]

Thanks a lot @joelostblom! I had seen the Observable notebooks but not the Vega discussion. This functionality is perfect if there is a way to fill in the cells with a color (other than in the context of a geographic shape). Do you think asking if there is a way to do that would be appropriate on the Vega GitHub page?

[joelostblom]

You might be able to use the area mark for that, but i am not sure how it would look on the top of my head. Might be something to ask on StackOVerflow tagging with vega-lite and vega?

[ChristopherDavisUCI]

Thanks again @joelostblom ! I don't have any experience with this mark_area but that's a good idea. I've had some bad experiences with Stack Overflow so will probably resist that for as long as possible!

[mattijn]

I recently re-discovered the encoding channel shape in combination with :G for the geojson data type. Maybe it is useful here.
If you precompute your voronoi using scipy.spatial (I used this answer) than you can render it as follow:

import numpy as np
from scipy.spatial import Voronoi
import pandas as pd
from shapely.ops import orient
from shapely import geometry
import shapely
import altair as alt

# make up data points add 4 distant dummy points and compute Voronoi tesselation
df_pts = pd.DataFrame(
    {"u": [0.1, 0.9, 0.1, 0.9, 0.5], "v": [0.1, 0.1, 0.9, 0.9, 0.5], "z": list("abcde")}
)
df_pts_extended = pd.concat(
    (
        df_pts,
        pd.DataFrame(
            [[999, 999], [-999, 999], [999, -999], [-999, -999]], columns=["u", "v"]
        ),
    ),
    ignore_index=True,
)
points = df_pts_extended[["u", "v"]].values
vor = Voronoi(points)

# polygonize voronoi regions as geojson features, add 'tessel' index key for color
vals = []
for ix, region in enumerate(vor.regions):
    if not -1 in region:
        polygon = [vor.vertices[i] for i in region]
        geompol = geometry.Polygon(polygon)
        if not geompol.is_empty:
            if geompol.exterior.is_ccw:
                geompol = orient(geompol, -1)
            feature = {
                "type": "Feature",
                "properties": {},
                "geometry": shapely.geometry.mapping(geompol),
            }
            ixs=vor.point_region[ix-1]  # trial
            vals.append({
                "geo": feature,
                "tessel": df_pts_extended.iloc[ixs].z  # trial
            })

# set the fit/extent range of axes, must be an array with a geom
xmin, xmax = 0, 1
ymin, ymax = 0, 1
extent = geometry.Polygon(
    [(xmax, ymax), (xmax, ymin), (xmin, ymin), (xmin, ymax), (xmax, ymax)]
)
fit = [shapely.geometry.mapping(extent)]

voronoi = alt.Data(name="vals", values=vals)
c_vor = (
    alt.Chart(voronoi)
    .mark_geoshape(clip=True, tooltip=True, opacity=0.3, stroke="black")
    .encode(shape="geo:G", color="tessel:N")
)

c_pts = (
    alt.Chart(df_pts)
    .mark_circle(clip=True, color="orange", tooltip=True, size=100, opacity=1)
    .encode(latitude="u:Q", longitude="v:Q", color="z:N")
)

(c_vor + c_pts).project(
    type="identity", reflectY=True, fit=fit
)

I tried to connect the computed regions to the value in the z column, but for that did not succeed (see # trial codelines). Maybe that is not possible? Maybe differently?
Result in VL: Open the Chart in the Vega Editor

[ChristopherDavisUCI]

This looks wild @mattijn, thanks so much for sharing it! It hadn't occurred to me that the geojson data might be usable for something not involving actual maps. (I've never used that ":G" encoding type before myself.) I will try to understand what's going on and let you know if I get confused. Thanks again!

[mattijn]

Yes, it's a bit hidden in the documentation. I never have seen any direct usage of this :G method either. Can do lots of things with this approach.

[josephburkhart]

Pinging this discussion again, would there be any interest among maintainers in adding a mark or transformation that produces a vornoi tessellation, without the need for scipy calculations and geo-wizardry? My research group would benefit from such functionality, and I'd be interested in figuring out how to contribute it myself, especially since the algorithm's already in Vega.

[ChristopherDavisUCI]

Hi! I admit I haven't thought about this issue in about one year, but I would be very happy to have an easy way to create Voronoi diagrams in Altair. Would this functionality need to be added to Vega-Lite first?

[josephburkhart]

This would make sense to me. I'll check out the contributor guidelines there. Do you think I should message maintainers there to gauge interest? I personally am still somewhat new to collaborative development and I haven't contributed to a Vega project before.

[ChristopherDavisUCI]

Yes I think that would be reasonable! I remember when I first got involved, I reached out through the Vega Slack (linked from the bottom of this page: https://vega.github.io/vega/ ) I think that or a discussion or an issue at Vega-Lite would be a good place to start: https://github.com/vega/vega-lite

Thanks again for your interest!

[josephburkhart]

And thanks to you for responding so quickly! I've made an enhancement issue on the vega-lite repo. If I don't hear from anyone there then I'll reach out over Slack.