Data processing: measuring – calibrating – or testing – Measurement system – Dimensional determination
Reexamination Certificate
1999-02-01
2002-10-08
Shah, Kamini (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Dimensional determination
C701S202000, C701S209000, C340S990000
Reexamination Certificate
active
06463400
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for identifying locations on a map. More particularly, the present invention relates to a method for locating and quarter sectioning an area on a map occupying a general polygon shape in an electronic map database.
2. Description of the Background Art
Electronic maps typically store latitude and longitude coordinates to identify geographical areas. To locate an area in the shape of a polygon, the longitude and latitude coordinates of points around the desired polygon are identified, and then lines connecting the points of the polygon are identified to locate the map data for the polygon.
Arizona's township sections are each intended to be square. To locate an Arizona township section, it would be desirable to simply identify the end point coordinates of the squares, and calculate the boundary lines for the square to identify the map data within the square. It would also be desirable to locate a “quarter section” of an Arizona township section square, such as a “Northwest Quarter”, in a similar manner.
Unfortunately, limitations of physical terrain and 19th century surveying techniques when the Arizona township sections were originally established made the square sections less than perfect. Some were rectangles, others had a missing corner. Some were more parallelograms rather than squares, and some were just utterly irregular.
Quarter sections of Arizona township sections were even more crudely identified. To identify quarter sections for mapping in the past, a human operator typically eyeballed a section and decided how to break the section into quarters.
To use an electronic map to identify a quarter section of an irregular Arizona township section and roughly match previous map sectioning techniques, it would be desirable to have a computerized method which would perform quartering in a way similar to the way a human might, and reject (or refuse to quarter) a section a human would reject.
To quarter a section different from a way a human would may be undesirable. For instance, it could be dangerous to identify areas for excavation, or digs, using an electronic map which mathematically determines perfect quarters of a polygon, when a goal is to avoid cutting gas pipes and the gas pipes were originally located relative to quarter section boundaries determined by human eyeballing.
SUMMARY OF THE INVENTION
In accordance with the present invention a method is provided for preparing a polygon in an electronic map database to be divided into quarters and for applying one or more tests to determine if the polygon is too irregular and should be rejected from quarter sectioning.
In one embodiment, before preparing a list of polygons for quartering, the list is scanned to find duplicate township section identifiers. Any section which is identified by multiple polygons is automatically rejected. In addition, any polygon whose identifier does not look like a township section identifier is also automatically rejected.
To prepare the polygon for quarter sectioning, the most northwest (NW), most northeast (NE), most southeast (SE), and most southwest (SW) point on the polygon are determined. A representative rectangle is then defined with the same corners.
Tests applied to determine if the polygon should be rejected from quartering include a first test to weed out a polygon which is too triangular, or where two corners of the representative rectangle are the same point. In the first test, ratios of the shortest to the longest length of opposite sides of the representative rectangle are taken. If either ratio is less than a predetermined number, the polygon is rejected from being divided into quarter sections.
A second test is an angle difference test. In the second test, an angle each side of the representative rectangle makes with respect to the x-axis is measured. If the difference in angles between two opposite sides is greater than a predetermined value, the polygon is rejected from quartering.
A third test determines how close the representative rectangle comes to actually representing the polygon's shape. In the third test, each point on the polygon between two corners is identified as “belonging on” the side of the representative rectangle connecting the two corners. Next, a distance between each point on the polygon and the side it “belongs on” is computed. The ratio of each distance to the average length of the four sides of the representative rectangle is then computed. If the ratio is greater than a predetermined number, the polygon is rejected.
A fourth test determines how closely the side of the representative rectangle follows the true lines of the polygon. In the fourth test, line segments between points on the polygon are each assigned to “belong on” a side of the representative rectangle if either of its points belong on that side. A ratio of the sum of the lengths of the line segments of the polygon that belong on a given side to the total length of the side of the representative rectangle is then taken. If the ratio is greater than a predetermined number, the polygon is rejected.
Once a polygon passes all tests, quartering is performed. For quartering, lines between the midpoints of opposite sides of the representative rectangle are drawn. The polygon is then divided into quarters using these lines.
REFERENCES:
patent: 5486822 (1996-01-01), Tenmoku et al.
patent: 5774824 (1998-06-01), Streit
patent: 5845228 (1998-12-01), Uekawa et al.
patent: 6014607 (2000-01-01), Takeshi et al.
patent: 6125323 (2000-09-01), Ito
patent: 6208935 (2001-03-01), Takaaki et al.
patent: 6259987 (2001-07-01), Timurceylan et al.
LandOfFree
Quarter sectioning algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quarter sectioning algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quarter sectioning algorithm will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2952094