Giter Club home page Giter Club logo

radialcells's Introduction

RadialCells

Fast radius nearest neighbors search on 2d plane

It is based on my method of exact rasterization of a circle

Usage example (also in ./example folder):

package main

import (
	"fmt"
	"math/rand"
	"time"

	"github.com/ogau/radialcells"
)

type Point = radialcells.Point

func randpoints(width, height float32, N int) []Point {
	points := make([]Point, N)
	seed := time.Now().Unix()
	fmt.Printf("[seed]: %v\n", seed)
	rnd := rand.New(rand.NewSource(seed))
	for i := 0; i < N; i++ {
		points[i].Row = rnd.Float32() * height
		points[i].Col = rnd.Float32() * width
	}
	return points
}

func main() {
	const width, height = 2.0, 1.0
	const gridstep = 0.05
	const npts = 500

	points := randpoints(width, height, npts)

	rc := radialcells.NewRadialCells(points, width, height, gridstep)

	var cx, cy float32 = 1.0, 0.5
	var radius float32 = 0.15

	result := rc.RadiusQuery(cx, cy, radius)
	for _, x := range result {
		pt := points[x.Index]
		fmt.Println(pt, x.Distance)
	}

	fmt.Println(len(result))
}
Rasterization algorithm:

There is a circle of a given radius relative to the point with the center (cx, cy). The method projects points from (cx, cy) on radius horizontally and vertically. Next, from each point in the clockwise direction, we pave path to stopline (end of quadrant). For each cell containing the projected point, a checkpoint is set in one of the corners, which is checked for entering the circle. For example, for the upper-left quadrant (green dots), the test point is set to the upper-right corner of the cell, and if it enters the circle, then the next cell for the path is the upper one, otherwise the right one.

radialcells's People

Contributors

ogau avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.