Skip to content

Commit

Permalink
Add n-gon glyph (bokeh#14027)
Browse files Browse the repository at this point in the history 
* Add n-gon glyph

* improve _hit_poly

* missing return type

* move helper funcs to hittest module

* remove spurious comment

* improve hittest tests
  • Loading branch information
@bryevdv
bryevdv authored Aug 21, 2024
1 parent 2bfef99 commit 0296a2d
Show file tree
Hide file tree
Showing 14 changed files with 709 additions and 175 deletions.
37 changes: 37 additions & 0 deletions bokehjs/src/lib/core/hittest.ts
View file
Original file line number Diff line number Diff line change
Expand Up @@ -94,3 +94,40 @@ export function check_2_segments_intersect(
return {hit: (a > 0 && a < 1) && (b > 0 && b < 1), x, y}
}
}

// Given two polygons, is any vertex of one inside the other
export function vertex_overlap(x0: Arrayable<number>, y0: Arrayable<number>, x1: Arrayable<number>, y1: Arrayable<number>): boolean {
// need to check "both directions" to handle total inclusion cases
for (let i = 0; i < x0.length; i++) {
if (point_in_poly(x0[i], y0[i], x1, y1)) {
return true
}
}
for (let i = 0; i < x1.length; i++) {
if (point_in_poly(x1[i], y1[i], x0, y0)) {
return true
}
}
return false
}

// Given two polygons, do any pair of edges intersect
export function edge_intersection(x0: Arrayable<number>, y0: Arrayable<number>, x1: Arrayable<number>, y1: Arrayable<number>): boolean {
for (let i = 0; i < x0.length-1; i++) {
for (let j = 0; j < x1.length-1; j++) {
if (check_2_segments_intersect(x0[i], y0[i], x0[i+1], y0[i+1], x1[j], y1[j], x1[j+1], y1[j+1]).hit) {
return true
}
}
// consider x1, y1 "closing" segment
if (check_2_segments_intersect(x0[i], y0[i], x0[i+1], y0[i+1], x1[x1.length-1], y1[x1.length-1], x1[0], y1[0]).hit) {
return true
}
}
// consider x0, y0, "closing" segment
if (check_2_segments_intersect(x0[x0.length-1], y0[x0.length-1], x0[0], y0[0], x1[x1.length-1], y1[x1.length-1], x1[0], y1[0]).hit) {
return true
}

return false
}
110 changes: 7 additions & 103 deletions bokehjs/src/lib/models/glyphs/circle.ts
View file
Original file line number Diff line number Diff line change
@@ -1,24 +1,15 @@
import {XYGlyph, XYGlyphView} from "./xy_glyph"
import {inherit} from "./glyph"
import {RadialGlyph, RadialGlyphView} from "./radial_glyph"
import type {PointGeometry, SpanGeometry, RectGeometry, PolyGeometry} from "core/geometry"
import {LineVector, FillVector, HatchVector} from "core/property_mixins"
import type * as visuals from "core/visuals"
import type {Rect, Indices} from "core/types"
import {to_screen} from "core/types"
import {RadiusDimension} from "core/enums"
import * as hittest from "core/hittest"
import * as p from "core/properties"
import type {SpatialIndex} from "core/util/spatial"
import {elementwise} from "core/util/array"
import type * as p from "core/properties"
import {minmax2} from "core/util/arrayable"
import type {Context2d} from "core/util/canvas"
import {Selection} from "../selections/selection"
import type {Range1d} from "../ranges/range1d"
import type {CircleGL} from "./webgl/circle"

export interface CircleView extends Circle.Data {}

export class CircleView extends XYGlyphView {
export class CircleView extends RadialGlyphView {
declare model: Circle
declare visuals: Circle.Visuals

Expand All @@ -30,67 +21,6 @@ export class CircleView extends XYGlyphView {
return CircleGL
}

protected override _index_data(index: SpatialIndex): void {
const {x, y, radius, data_size} = this
for (let i = 0; i < data_size; i++) {
const x_i = x[i]
const y_i = y[i]
const r_i = radius.get(i)
index.add_rect(x_i - r_i, y_i - r_i, x_i + r_i, y_i + r_i)
}
}

protected override _map_data(): void {
this._define_or_inherit_attr<Circle.Data>("sradius", () => {
if (this.model.properties.radius.units == "data") {
const sradius_x = () => this.sdist(this.renderer.xscale, this.x, this.radius)
const sradius_y = () => this.sdist(this.renderer.yscale, this.y, this.radius)

const {radius_dimension} = this.model
switch (radius_dimension) {
case "x": {
return this.inherited_x && this.inherited_radius ? inherit : sradius_x()
}
case "y": {
return this.inherited_y && this.inherited_radius ? inherit : sradius_y()
}
case "min":
case "max": {
if (this.inherited_x && this.inherited_y && this.inherited_radius) {
return inherit
} else {
return elementwise(sradius_x(), sradius_y(), Math[radius_dimension])
}
}
}
} else {
return this.inherited_sradius ? inherit : to_screen(this.radius)
}
})
}

protected override _mask_data(): Indices {
const {frame} = this.renderer.plot_view

const shr = frame.x_target
const svr = frame.y_target

let hr: Range1d
let vr: Range1d
if (this.model.properties.radius.units == "data") {
hr = shr.map((x) => this.renderer.xscale.invert(x)).widen(this.max_radius)
vr = svr.map((y) => this.renderer.yscale.invert(y)).widen(this.max_radius)
} else {
hr = shr.widen(this.max_radius).map((x) => this.renderer.xscale.invert(x))
vr = svr.widen(this.max_radius).map((y) => this.renderer.yscale.invert(y))
}

return this.index.indices({
x0: hr.start, x1: hr.end,
y0: vr.start, y1: vr.end,
})
}

protected _paint(ctx: Context2d, indices: number[], data?: Partial<Circle.Data>): void {
const {sx, sy, sradius} = {...this, ...data}

Expand Down Expand Up @@ -232,45 +162,23 @@ export class CircleView extends XYGlyphView {

return new Selection({indices})
}

// circle does not inherit from marker (since it also accepts radius) so we
// must supply a draw_legend for it here
override draw_legend_for_index(ctx: Context2d, {x0, y0, x1, y1}: Rect, index: number): void {
// using objects like this seems a little wonky, since the keys are coerced to
// stings, but it works
const len = index + 1

const sx: number[] = new Array(len)
sx[index] = (x0 + x1)/2
const sy: number[] = new Array(len)
sy[index] = (y0 + y1)/2

const sradius: number[] = new Array(len)
sradius[index] = Math.min(Math.abs(x1 - x0), Math.abs(y1 - y0))*0.2

this._paint(ctx, [index], {sx, sy, sradius})
}
}

export namespace Circle {
export type Attrs = p.AttrsOf<Props>

export type Props = XYGlyph.Props & {
radius: p.DistanceSpec
radius_dimension: p.Property<RadiusDimension>
export type Props = RadialGlyph.Props & {
hit_dilation: p.Property<number>
} & Mixins

export type Mixins = LineVector & FillVector & HatchVector
}

export type Visuals = XYGlyph.Visuals & {line: visuals.LineVector, fill: visuals.FillVector, hatch: visuals.HatchVector}
export type Visuals = RadialGlyph.Visuals

export type Data = p.GlyphDataOf<Props>
}

export interface Circle extends Circle.Attrs {}

export class Circle extends XYGlyph {
export class Circle extends RadialGlyph {
declare properties: Circle.Props
declare __view_type__: CircleView

Expand All @@ -281,11 +189,7 @@ export class Circle extends XYGlyph {
static {
this.prototype.default_view = CircleView

this.mixins<Circle.Mixins>([LineVector, FillVector, HatchVector])

this.define<Circle.Props>(({Float}) => ({
radius: [ p.DistanceSpec, {field: "radius"} ],
radius_dimension: [ RadiusDimension, "x" ],
hit_dilation: [ Float, 1.0 ],
}))
}
Expand Down
1 change: 1 addition & 0 deletions bokehjs/src/lib/models/glyphs/index.ts
View file
Original file line number Diff line number Diff line change
Expand Up @@ -20,6 +20,7 @@ export {Line} from "./line"
export {MathMLGlyph} from "./mathml_glyph"
export {MultiLine} from "./multi_line"
export {MultiPolygons} from "./multi_polygons"
export {Ngon} from "./ngon"
export {Patch} from "./patch"
export {Patches} from "./patches"
export {Quad} from "./quad"
Expand Down
178 changes: 178 additions & 0 deletions bokehjs/src/lib/models/glyphs/ngon.ts
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,178 @@
import {RadialGlyph, RadialGlyphView} from "./radial_glyph"
import type {PointGeometry, PolyGeometry, RectGeometry, SpanGeometry} from "core/geometry"
import {minmax2} from "core/util/arrayable"
import {edge_intersection, point_in_poly, vertex_overlap} from "core/hittest"
import * as p from "core/properties"
import type {Arrayable} from "core/types"
import type {Context2d} from "core/util/canvas"
import {Selection} from "../selections/selection"

export interface NgonView extends Ngon.Data {}

function ngon(x: number, y: number, r: number, n: number, angle: number): [Arrayable<number>, Arrayable<number>] {
const xs = new Float32Array(n)
const ys = new Float32Array(n)
const alpha_i = 2*Math.PI / n
for (let i = 0; i < n; i++) {
const alpha = i * alpha_i + angle
xs[i] = x + r * Math.sin(alpha)
ys[i] = y + r * -Math.cos(alpha)
}
return [xs, ys]
}

export class NgonView extends RadialGlyphView {
declare model: Ngon
declare visuals: Ngon.Visuals

protected _paint(ctx: Context2d, indices: number[], data?: Partial<Ngon.Data>): void {
const {sx, sy, sradius, angle, n} = {...this, ...data}

for (const i of indices) {
const sx_i = sx[i]
const sy_i = sy[i]
const sradius_i = sradius[i]
const angle_i = angle.get(i)
const n_i = n.get(i)

if (n_i < 3 || !isFinite(sx_i + sy_i + sradius_i + angle_i + n_i)) {
continue
}

const [sxs, sys] = ngon(sx_i, sy_i, sradius_i, n_i, angle_i)

ctx.beginPath()
ctx.moveTo(sxs[0], sys[0])
for (let i = 1; i <= n_i; i++) {
ctx.lineTo(sxs[i], sys[i])
}
ctx.closePath()

this.visuals.fill.apply(ctx, i)
this.visuals.hatch.apply(ctx, i)
this.visuals.line.apply(ctx, i)
}
}

protected _ngon(index: number) {
const {sx, sy, sradius, angle, n} = {...this}
const sx_i = sx[index]
const sy_i = sy[index]
const sradius_i = sradius[index]
const angle_i = angle.get(index)
const n_i = n.get(index)
return ngon(sx_i, sy_i, sradius_i, n_i, angle_i)
}

protected override _hit_point(geometry: PointGeometry): Selection {
const x = this.renderer.xscale.invert(geometry.sx)
const y = this.renderer.yscale.invert(geometry.sy)
const candidates = this.index.indices({x0: x, y0: y, x1: x, y1: y})

const indices = []
for (const index of candidates) {
const [sxs, sys] = this._ngon(index)
if (point_in_poly(geometry.sx, geometry.sy, sxs, sys)) {
indices.push(index)
}
}
return new Selection({indices})
}

protected override _hit_span(geometry: SpanGeometry): Selection {
const {sx, sy} = geometry
const {x0, x1, y0, y1} = this.bounds()

const [val, dim, candidates] = (() => {
switch (geometry.direction) {
case "v": {
const y = this.renderer.yscale.invert(sy)
const candidates = this.index.indices({x0, y0: y, x1, y1: y})
return [sy, 1, candidates]
}
case "h": {
const x = this.renderer.xscale.invert(sx)
const candidates = this.index.indices({x0: x, y0, x1: x, y1})
return [sx, 0, candidates]
}
}
})()

const indices = []
for (const index of candidates) {
const coords = this._ngon(index)[dim]
for (let i = 0; i < coords.length-1; i++) {
if ((coords[i] <= val && val <= coords[i+1]) || (coords[i+1] <= val && val <= coords[i])) {
indices.push(index)
break
}
}
}
return new Selection({indices})
}
protected override _hit_poly(geometry: PolyGeometry): Selection {
const {sx: gsx, sy: gsy} = geometry

const candidates = (() => {
const xs = this.renderer.xscale.v_invert(gsx)
const ys = this.renderer.yscale.v_invert(gsy)
const [x0, x1, y0, y1] = minmax2(xs, ys)
return this.index.indices({x0, x1, y0, y1})
})()

const indices = []
for (const index of candidates) {
const [sxs, sys] = this._ngon(index)
if (vertex_overlap(sxs, sys, gsx, gsy)) {
indices.push(index)
continue
}
if (edge_intersection(sxs, sys, gsx, gsy)) {
indices.push(index)
continue
}
}

return new Selection({indices})
}

protected override _hit_rect(geometry: RectGeometry): Selection {
const {sx0, sx1, sy0, sy1} = geometry
const sxs = [sx0, sx1, sx1, sx0]
const sys = [sy0, sy0, sy1, sy1]
return this._hit_poly({type: "poly", sx: sxs, sy: sys})
}
}

export namespace Ngon {
export type Attrs = p.AttrsOf<Props>

export type Props = RadialGlyph.Props & {
angle: p.AngleSpec
n: p.NumberSpec
}

export type Visuals = RadialGlyph.Visuals

export type Data = p.GlyphDataOf<Props>
}

export interface Ngon extends Ngon.Attrs {}

export class Ngon extends RadialGlyph {
declare properties: Ngon.Props
declare __view_type__: NgonView

constructor(attrs?: Partial<Ngon.Attrs>) {
super(attrs)
}

static {
this.prototype.default_view = NgonView

this.define<Ngon.Props>(() => ({
angle: [ p.AngleSpec, 0 ],
n: [ p.NumberSpec, {field: "n"} ],
}))
}
}
Loading

0 comments on commit 0296a2d

Please sign in to comment.