Version 3.40, May, 2004.
As may be seen within
www.geodyssey.com.
Tested with Internet Explorer 5, Opera 4 and Mozilla 1.4.
Last updated 2004/05/05.
Information in this document is subject to change without notice.
Hipparchus® is a registered trademark of Geodyssey Limited.
© Copyright 1992-2004 by Geodyssey Limited.
All rights reserved, worldwide.
Here are some general comments.
The Utilities divide into six categories:
Here's an alphabetic index of the Utilities.
The Hipparchus Utilities are batch programs written in ANSI C and distributed in source. For maximum portability, they employ a simple console interface implemented using only the stdin, stdout and stderr facilities of the C language run-time library. Run-time file I/O is restricted to the stream I/O facilities of C/C++.
Because many of the Utilities write or read binary data elements or structures, it is essential that the Utilities be compiled and run in the target computing environment of the application they support. Otherwise, differences in machine architecture and compiled structures may render the results unuseable.
Most of the Utilities call functions of the Hipparchus Auxiliary Library and the Hipparchus Library proper. Before attempting to compile the Utilities, the developer should first compile and build a local Hipparchus Auxiliary Library for the target application platform and verify the availability of the Hipparchus Library binaries for that platform.
Executable copies of the utilities will normally be invoked from a system console, but note that they may also be invoked from Galileo via the Shell command.
The Utilities share a common command-line interface. Their command line takes this form:
utility-name [options] in-file-name [out-file-name] [options]
where:
At run time, Utilities report their usage in response to a command line specifying no parameters or one specifying the help option ("/h" or "/?").
These Utilities all have to do with the generation and modification of Voronoi cell structures for use as spatial indexes within the Hipparchus-based application. Although the application can construct such an index on the fly, most will employ an index built off-line, using one or more of these utilies:
Before reading this text you should be familiar with Chapter 6 of the Hipparchus tutorial: Working With Voronoi Cells.
This example assumes that an application has a set of points that reasonably well mimics the density of all the data in a system.
The process begins by selecting a "starter" set of cell centerpoints (in this case dodeca04.pts), and a set of points representing the density of the data (in this case wells.ptz). Note that the density point coordinate file is expressed in binary concise direction cosines. As it is read and converted to cell coordinates many times during the execution of the program, this format makes the process considerably faster.
In a preliminary step, a Voronoi index consisting of about 800 cells is constructed from a starter index (isotype) - to be used as the first in a series of gradually densified indexes.
What follows is a number of "densification steps", carried out until the population of points in any cell is within a given target. First, the densification file is read and points are deposited in the cells they belong to. The count of points in each cell is recorded, as well as the mid-point of all the densification points in that cell. Each cell with a population above the target is then "split" into two cells by replacing its center with two new centers, strategically positioned so that the new cells tend to remain "round", and that the new cell centers are placed closest to the highest density of the points in the new cells.
In each of these steps, a check is made for a zero-length edge. If this condition is discovered, two of the closest diagonally opposite points (among the four that form a "corner") are "nudged" closer together. The process is repeated as necessary.
Once the sufficient number of cells is added to reduce the population in any cell below the target, a number of "final" cell geometry adjustments are carried out:
First, the cell centers are moved toward the gravity center of the cell. The purpose of this is to increase the "roundness" of the cells.
Next, cells are checked for a below-minimum edge length, and if such is found, participating centers are moved closer to each other. This is done to improve the computational properties of the structure.
Last, the cells are reordered, also in order to improve the computational properties of the structure.
After a final consistency check, the structure is written to a file.
To learn more, please inspect the source of the cellbld.c source program and its included components.
To see the program in action, please download the console program cellbld.exe for Win32 and its two related data files: dodeca04.pts and wells.ptz (3 MB), then start the program from a command console with the program and its two data files in your "current directory". The download is available at www.geodyssey.com.
This Utility provide for the transcription of point or vertex latitude-longitude coordinates between ASCII and packed binary formats. Although most coordinate data will originate in the ASCII format, high volume vector coordinates often can be more efficiently archived or reprocessed in packed binary format. Many of the other Hipparchus Utilities accept coordinates in either format.
Objects constructed in the context of a particular Voronoi cell structure have a precise canonical form in memory, which form is defined by the constructor functions of the Hipparchus Library, namely h7_GlobalToPset, h7_GlobalToLset and h7_GlobalToRset. All elements of an object's canonical form are binary values of type integer, float or double. Owing to differing machine architectures, such internal objects clearly are not directly cross-platform portable.
Some operating systems (such as Windows 95/98/2000/XP/NT and many Unix systems) support memory-mapped file access via their virtual memory manager. Within such systems an external file that represents a Hipparchus internal object is known as a Hipparchus Binary Object (HBO). Such objects may be opened and closed using functions of section h8 of the Hipparchus Auxiliary Library. Once open, an HBO may be accessed by a program just as if it were memory resident. Any operation permissible in Hipparchus for a memory object may be carried out on an HBO, via buffers managed by the operating systems's virtual memory manager. It is not required that such objects first be fetched into real memory. Therefore, operations on Hipparchus Binary Objects are not restricted by real memory constraints, and otherwise complex operations such as region intersections may be carried out very efficiently.
An application can generate HBO's on the fly (see Galileo). Another alternative is to generate them off-line using Hipparchus Utilities. Three programs are provided for this purpose:
These programs accept coordinate inputs in either ASCII or packed binary format, generating HBO files accessible via memory-mapped file facilities of the operating system (if available). Construction of the HBO file is always carried out in the context of an application-specific Voronoi index.
Recognizing that the preponderance of such data is unchanging (static), and to demonstrate the value of the Voronoi tessellation as an efficient spatial index, a simple yet effective file system is provided via functions of the Hipparchus Auxiliary Library and certain Hipparchus Utilities.
Known as Hipparchus Point-Line-Region collection files (PLR's), simple stream I/O files constructed according to the Hipparchus PLR schema may be accessed efficiently by the Hipparchus-based application to retrieve application coordinate data in a form immediately useable by the application. PLR collections are indexed primarily by the identifiers of the Voronoi cells that contain (own) the collection's member points or vertices. For line or region collections, secondary indexing is provided by line or region identifier. Construction of a PLR collection is always carried out in the context of an application-specific Voronoi index.
A PLR collection is created using one of these Hipparchus Utilities:
Several Utilities support the capture or real-time simulation of GPS receiver interface message traffic. GPS ASCII interface messages (known as Natianal Marine Electronics Association (NMEA) sentences) may be captured and converted to ASCII lat/long line sets or may be generated for subsequent transmission between computers, simulating real-time GPS reception.
Two utilities are provided. They are: