Categories
OpenVoronoi

Arc predicates

I started working on arc-sites for OpenVoronoi. The first things required are an in_region(p) predicate and an apex_point(p) function. It is best to rapidly try out and visualize things in python/VTK first, before committing to slower coding and design in c++.

in_region(p) returns true if point p is inside the cone-of-influence of the arc site. Here the arc is defined by its start-point p1, end-point p2, center c, and a direction flag cw for indicating cw or ccw direction. This code will only work for arcs smaller than 180 degrees.


Here randomly chosen points are shown green if they are in-region and pink if they are not.

apex_point(p) returns the closest point to p on the arc. When p is not in the cone-of-influence either the start- or end-point of the arc is returned. This is useful in OpenVoronoi for calculating the minimum distance from p to any point on the arc-site, since this is given by (p-apex_point(p)).norm().


Here a line from a randomly chosen point p to its apex_point(p) has been drawn. Either the start- or end-point of the arc is the closest point to out-of-region points (pink), while a radially projected point on the arc-site is closest to in-region points (green).

The next thing required are working edge-parametrizations for the new type of voronoi-edges that will occur when we have arc-sites (arc/point, arc/line, and arc/arc).

Categories
Research

Uniform random points in a circle using polar coordinates

I need this seldom enough to forget how it's done - but then it's annoying to have to think/google for the solution again when I do need it... So I'll document here.

The task is to generate uniformly distributed numbers within a circle of radius R in the (x,y) plane. At first polar coordinates seems like a great idea, and the naive solution is to pick a radius r uniformly distributed in [0, R], and then an angle theta uniformly distributed in [0, 2pi]. BUT, you end up with an exess of points near the origin (0, 0)!  This is wrong because if we look at a certain angle interval, say [theta, theta+dtheta], there needs to be more points generated further out (at large r), than close to zero. The radius must not be picked from a uniform distribution, but one that goes as

pdf_r = (2/R^2)*r

That's easy enough to do by calculating the inverse of the cumulative distribution, and we get for r:

r = R*sqrt( rand() )

where rand() is a uniform random number in [0, 1]. Here is a picture:

fig2

some matlab code here.

The thinking for generating random points on the surface of a sphere in 3D is very similar. If I get inspired I will do a post on that later, meanwhile you can go read these lecture notes.