Quarter sectioning algorithm

• US 6,463,400 B1
• Filed: 02/01/1999
• Issued: 10/08/2002
• Est. Priority Date: 02/01/1999
• Status: Expired due to Term

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Barkley-Yeung, Ian
• Primary Examiner(s): SHAH, KAMINI S
• Application Number:
  US09/241,157
• Time in Patent Office: 1,345 Days
• Field of Search: 702/158, 701/212, 701/209, 701/201, 701/202, 340/990, 340/995
• US Class Current: 702/158
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F

Abstract

A polygon of an electronic map is prepared for dividing into quarter sections and tests are applied to determine if the polygon is too irregular for quarter sectioning. To prepare for quarter sectioning, a representative rectangle is defined having corners matching corners of the polygon. Tests to determine if the polygon should be quartered begin with a first test to weed polygons too triangular in shape. 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 quarter sectioning. In a second test an angle difference is determined by measuring the angle each side of the representative quadrilateral makes with respect to the x-axis. 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 by determining the distance between points on the polygon and the representative rectangle, and rejecting the polygon from quartering if any distance is greater than a predetermined amount. A fourth test determines how close the side of the representative rectangle follows the true lines of the polygon by determining a ratio of the total length of lines of the polygon connecting two corners to the length of a side of the representative rectangle connecting the corners, and if the ratio is greater than a predetermined number, rejecting the polygon from quartering.

Claims

1. A method of determining when a polygon identified in an electronic map should be rejected from being divided into quarter sections, the method comprising the steps of:

determining a most northwest (NW), northeast (NE), southeast (SE) and southwest (SW) point on the polygon;

defining a representative quadrilateral as having corners which are the most NW, NE, SE and SW points on the polygon, wherein a north side of the representative quadrilateral is formed by a line between the NW and NE points, a south side of is formed by a line between the SE and SW points, an east side is formed by a line between the NE and SE points and a west side is formed by a line between the NW and SW points;

calculating a first ratio as a shortest to a longest of the north side and south side of the representative quadrilateral;

calculating a second ratio as a shortest to a longest of the east side and the west side of the representative quadrilateral; and

rejecting the polygon from being divided into quarter sections when one of the first and second ratios is less than a first predetermined number.

2. The method of claim 1, wherein the first predetermined number is 0.5.

3. The method of claim 1, further comprising the steps of:

calculating a first angle between the north side of the representative quadrilateral and an x-axis;

calculating a second angle between the south side of the representative quadrilateral and the x-axis;

calculating a first difference between the first and second angles;

calculating a third angle between the east side of the representative quadrilateral and the x-axis;

calculating a fourth angle between the west side of the representative quadrilateral and the x-axis; and

calculating a second difference between the second and third angles; and

rejecting the polygon from being divided into quarter sections when one of the first difference and the second difference is greater than a second predetermined number.

4. The method of claim 3, wherein the second predetermined number is 10 degrees.

5. The method of claim 3 further comprising the steps of:

identifying points between the most NW and NE points of the polygon as belonging on the north side of the representative quadrilateral;

identifying points between the most NE and SE points of the polygon as belonging on the east side of the representative quadrilateral;

identifying points between the most SE and SW points of the polygon as belonging on the south side of the representative quadrilateral;

identifying points between the most SW and NW points of the polygon as belonging on the west side of the representative quadrilateral;

calculating a distance between each of the points identified as belonging on a side of the representative quadrilateral and the side the point belongs on;

calculating a ratio of the distance to the average length of the north, south, east and west sides of the representative quadrilateral for each of the identified points; and

rejecting the polygon from being divided into quarters when the ratio for one of the identified points is greater than a third predetermined number.

6. The method of claim 5 further comprising the steps of:

identifying line segments between points located from the most NW to the most NE points of the polygon as belonging on the north side of the representative quadrilateral;

calculating a first ratio as the sum of the lengths of the line segments belonging on the north side to a length of the north side of the representative quadrilateral;

rejecting the polygon from being divided into quarter sections when the first ratio is greater than a fourth predetermined number;

identifying line segments between points located from the most NE to the most SE points of the polygon as belonging on the east side of the representative quadrilateral;

calculating a second ratio as the sum of the lengths of the line segments belonging on the east side to a length of the east side of the representative quadrilateral;

rejecting the polygon from being divided into quarter sections when the second ratio is greater than the fourth predetermined number;

identifying line segments between points located from the most SE to the most SW points of the polygon as belonging on the south side of the representative quadrilateral;

calculating a third ratio as the sum of the lengths of the line segments belonging on the south side to a length of the south side of the representative quadrilateral;

rejecting the polygon from being divided into quarter sections when the third ratio is greater than the fourth predetermined number;

identifying line segments between points located from the most SW to the most NW points of the polygon as belonging on the west side of the representative quadrilateral;

calculating a fourth ratio as the sum of the lengths of the line segments belonging on the west side to a length of the west side of the representative quadrilateral; and

rejecting the polygon from being divided into quarter sections when the fourth ratio is greater than the fourth predetermined number.

7. The method of claim 1, further comprising the steps of:

calculating a first angle between the north side of the representative quadrilateral and an x-axis;

calculating a second angle between the south side of the representative quadrilateral and the x-axis;

calculating a third angle between the east side of the representative quadrilateral and a y-axis;

calculating a fourth angle between the west side of the representative quadrilateral and the y-axis; and

rejecting the polygon from being divided into quarter sections when one of the first, second, third and fourth angles is greater than the second predetermined number.

8. The method of claim 7 further comprising the steps of:

determining the first average length of the west side and the east side of the representative quadrilateral;

determining a second average length of the north side and the south side of the representative quadrilateral;

determining a third average length of the north, south, east and west side of the representative quadrilateral; and

rejecting the polygon from being divided into quarter sections when a ratio of a magnitude of a difference between the first average length and the second average length to the third average length is less than a third predetermined number.

9. A method of determining when a polygon identified in an electronic map should be rejected from being divided into quarter sections, the method comprising the steps of:

determining a most northwest (NW), northeast (NE), southeast (SE) and southwest (SW) point on the polygon;

defining a representative quadrilateral as having corners which are the most NW, NE, SE and SW points on the polygon, wherein a north side of the representative quadrilateral is formed by a line between the NW and NE points, a south side of is formed by a line between the SE and SW points opposite the north side, an east side is formed by a line between the NE and SE points, and a west side is formed by a line between the NW and SW points opposite the east side;

calculating angles between opposite sides of the representative quadrilateral and an x-axis;

rejecting the polygon from being divided into quarter sections when a difference between the angles is greater than a predetermined number.

10. A method of determining when a polygon identified in an electronic map should be rejected from being divided into quarter sections, the method comprising the steps of:

determining a most northwest (NW), northeast (NE), southeast (SE) and southwest (SW) point on the polygon;

defining a representative quadrilateral as having corners which are the most NW, NE, SE and SW points on the polygon, wherein a north side of the representative quadrilateral is formed by a line between the NW and NE points, a south side of is formed by a line between the SE and SW points, an east side is formed by a line between the NE and SE points and a west side is formed by a line between the NW and SW points;

identifying points of the polygon between corners defining a particular one of the sides of the representative quadrilateral as belonging on the particular side of the representative quadrilateral;

calculating a ratio of the distance between each of the points identified as belonging on the particular side of the representative quadrilateral and the particular side; and

rejecting the polygon from being divided into quarter sections when the ratio for one of the identified points is greater than a predetermined number.

11. A method of determining when a polygon identified in an electronic map should be rejected from being divided into quarter sections, the method comprising the steps of:

determining a most northwest (NW), northeast (NE), southeast (SE) and southwest (SW) point on the polygon;

defining a representative quadrilateral as having corners which are the most NW, NE, SE and SW points on the polygon, wherein a north side of the representative quadrilateral is formed by a line between the NW and NE points, a south side of is formed by a line between the SE and SW points, an east side is formed by a line between the NE and SE points and a west side is formed by a line between the NW and SW points;

identifying particular line segments connecting points on the polygon between the corners defining a given one of the sides of the representative quadrilateral as belonging on the given side of the representative quadrilateral;

calculating a ratio of the sum of the lengths of the particular line segments belonging on the given side to a length of the given side; and

rejecting the polygon from being divided into quarter sections when the ratio is greater than a predetermined number.

12. A method of determining when a polygon identified in an electronic map should be rejected from being divided into quarter sections, the method comprising the steps of:

determining a most northwest (NW), northeast (NE), southeast (SE) and southwest (SW) point on the polygon;

defining a representative quadrilateral as having corners which are the most NW, NE, SE and SW points on the polygon, wherein a north side of the representative quadrilateral is formed by a line between the NW and NE points, a south side of is formed by a line between the SE and SW points, an east side is formed by a line between the NE and SE points and a west side is formed by a line between the NW and SW points;

calculating angles between opposite sides of the representative quadrilateral and a y-axis;

rejecting the polygon from being divided into quarter sections when a difference between the angles is greater than a predetermined number.

13. A method of determining when a polygon identified in an electronic map should be rejected from being divided into quarter sections, the method comprising the steps of:

determining a most northwest (NW), northeast (NE), southeast (SE) and southwest (SW) point on the polygon;

defining a representative quadrilateral as having corners which are the most NW, NE, SE and SW points on the polygon, wherein a north side of the representative quadrilateral is formed by a line between the NW and NE points, a south side of is formed by a line between the SE and SW points, an east side is formed by a line between the NE and SE points and a west side is formed by a line between the NW and SW points;

determining the first average length of the west side and the east side of the representative quadrilateral;

determining a second average length of the north side and the south side of the representative quadrilateral;

determining a third average length of the north, south, east and west side of the representative quadrilateral; and

rejecting the polygon from being divided into quarter sections when a ratio of a magnitude of a difference between the first average length and the second average length to the third average length is less than a predetermined number.

14. A method of dividing a polygon identified in an electronic map into quarter sections, the method comprising the steps of:

determining a most northwest (NW), northeast (NE), southeast (SE) and southwest (SW) point on the polygon;

defining a representative quadrilateral as having corners which are the most NW, NE, SE and SW points on the polygon, wherein a north side of the representative quadrilateral is formed by a line between the NW and NE points, a south side is formed by a line between the SE and SW points opposite the north side, an east side is formed by a line between the NE and SE points, and a west side is formed by a line between the NW and SW points opposite the east side; and

defining quartering lines, each between midpoints of opposite sides of the representative quadrilateral.