This page has not been substantively updated since 2009.

(in WR Franklin → Research)

PNPOLY (Point inclusion in polygon test)

This 8 line program, an update of what I wrote in 1970, tests if a point is inside a polygon in E². It handles multiple components with nested holes and islands. Compared to other routines attempting to test point inclusion, PNPOLY tends to be, simultaneously, smaller, faster, and more general.

Uniform Grids

Uniform grids are useful in many of the following applications. This idea is intended to be just sophisticated enough to solve the problem, without being so complicated that it is difficult to implement, including the messy special cases, and parallelize. (1977)

The concept, which is useful for culling pairs of objects that may intersect, is to overlay a uniform grid on the data. Then iterate over the elements, finding which grid cells each passes thru. Finally, iterate over the cells, comparing pairs of elements that pass thru the same cell. Implementing this properly requires some attention to detail. This method works well even when the data is unevenly distributed, where one's first impulse would be to use the, more complicated, quadtree.

One application is a parallelizable algorithm finds all the intersections among a large number of small line segments in E². The time to find all K intersections among N line segments is an expected θ(N+K), altho an adversary can choose input to raise that to N² . However no real data sets have exhibited that behavior. Data has been used from cartography, VLSI design, and nonuniform meshes. This is a common operation in many higher-level operations such as boolean combinations. Titles include:

1. Geometric computing and the uniform grid data technique (with V Akman, M Kankanhalli and C Narayanaswam),
2. Uniform grids: A technique for intersection detection on serial and parallel machines (with C Narayanaswami, M Kankanhalli, D Sun, MC Zhou, and PYF Wu),
3. Efficiency of uniform grids for intersection detection on serial and parallel machines (with N Chandrasekhar, M Kankanhalli, M Seshan, and V Akman),
4. Fast intersection detection on serial and parallel machines using the uniform grid technique (with N Chandrasekhar, M Kankanhalli, and V Akman), and
5. Adaptive grids for geometric operations.

Efficient Low-Level Operations

Several of these sections describe efficient low-level operations. Spending energy on simple problems may seem a waste of time, so why do I do it?

Efficient rotation in E³

1. bibtexsummary:[/wrf.bib,f-ero-83]

Studies of Fundamentals

E.g., an investigation into why raster graphics algorithms can be surprisingly counterintuitive and difficult.

For example, consider finding the raster line segment between two points, such as with the Bresenham algorithm. Now, pick two points on the interior of that line and draw the new line segment between them. Probably the points of the new line segment will not be a subset of the points of the original line segment. This does not happen with ideal, vector, lines.

The deep reason that raster graphics can be harder than vector graphics is that, in algebra, the integers are harder than the reals, not easier. E.g., first order logic over the reals with addition and multiplication is solvable. Not so over the integers. Titles include:

1. bibtexsummary:[/wrf.bib,f-prga-85]
2. bibtexsummary:[/wrf.bib,f-cesua-84]