# Edge effects in K-function

I am trying to write some codes for distance-based evaluation of point process such as $G$, $F$ and $K$ functions. In the implementation of $K$ there is a case to consider edge effect to have an unbiased $K$ measure. A simple (!) but perfect (also common) solution is to consider the intersection area of a circle drawn on each point ($center(x,y)$) with a specified radius ($r$) with the region of study. Although the concept ($K$) is purely statistical the intersection of a circle with region (in simple case a rectangle but normally a polygon) is pure geometrical problem. Any idea on:

• how to find intersection area of a circle with arbitrary shape polygon?
• how to find weights for $K$ more efficiently?
-
I know that there are already packages in R for K-function with edge effects. I prefer however to write my own code in Python purely and understand the concepts and solutions fully. –  Developer Apr 30 '12 at 13:02
Currently I use square approximation of circle. It works well but apparently involves some biases. You may also discuss the error being added by this approximation. Thanks –  Developer Apr 30 '12 at 13:04

Most GIS software will compute these areas. The calculations have to be repeated, though, for a very large number of circles, which can take a long time when using vector (linestring) representations of the polygon and the circles.

A reasonably efficient method in this circumstance is to rasterize the polygon, representing it with a binary (0-1) indicator: $1$'s for the inside, $0$'s for the outside. A focal mean of radius $r$ produces a grid whose values give the desired relative areas. Because a focal mean is the convolution of the grid with a simple kernel (itself a binary indicator of the interior of a circle of radius $r$), it can be computed with a fast Fourier transform. For relatively large values of $r$, this will be much more efficient than direct calculation of all the relative areas.

This image is a hillshaded rendering of an $r=34.3$ kilometer radius circular focal mean of a map of the state of Kentucky. Values range from $0$ along the boundary (shown in dark blue) up to $1$ at all points in the interior more than $34.3$ kilometers from the boundary (shown in light gray).

(It should be evident that generic edge-correction formulas will not be accurate for such convoluted polygons.)

Such a grid has to be computed for each radius. To minimize work, consider computing a short sequence of grids for a series of radii, then interpolate between them for all other radii. Do not try to achieve very high resolution: it usually is not warranted. This grid, for instance, is relatively small (at 204 rows by 400 columns), but is fine enough to resolve a fairly tortuous boundary. (In principle, at this resolution thousands of these convolutions could be computed in the space of one second using appropriate software.)

Note that it will not be necessary actually to display such grids: they will be represented internally as matrices and are used only to retrieve their values.

Often these functions (K, etc.) need to be computed only for circles centered at relatively small sets of points. In that case, direct calculation of the areas, circle by circle, may be faster than the FFT: but still a raster representation will expedite the calculation and is easy to code (compared to the computational geometry algorithms needed for the vector representations of the polygon and the circles).

-