Method and apparatus for calculating geometry of a moving haven

• US 7,043,361 B1
• Filed: 11/26/2003
• Issued: 05/09/2006
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: Northrop Grumman Systems Corporation (Northrop Grumman Corporation)
• Original Assignee: Northrop Grumman Corporation
• Inventors: Wall, Mathew D.
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US10/724,308
• Time in Patent Office: 895 Days
• Field of Search: 701/200, 701/201, 701/202, 701/207, 701/208, 701/211, 340/988, 340/990, 340/995.19
• US Class Current: 701/211
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/203 Specially adapted for sailing ships

Abstract

Boundaries of a moving haven along a voyage plan are constructed with the utilization of simple shapes, rectangles and arcs, each of which are drawn with selected line segments. A buffer, internal to the moving haven boundary, is created, which, when crossed initiates a warning that the boundary of the moving haven is being approached. Procedures for the implementation of the moving haven boundary and the buffer are substantially similar, with but few modification from the procedure that generates the moving haven needed to establish the procedure to implement the procedure that generates the buffer.

Claims

1. A method for generating a moving haven boundary along a voyage plan comprising the steps of:

establishing a width for said moving haven boundary;

creating rectangles centered on said voyage plan, said rectangles having edges separated by said width and lengths equal to lengths of strait line portions of said voyage plan; and

determining pie shaped areas between rectangles at waypoints of said voyage plan, each of said pie shaped areas having an arc centered at a waypoint and extending between vertices of rectangles on either side of said waypoint,

establishing said moving haven boundary with a polygonal line comprising said edges and said arcs.

2. A method in accordance with claim 1 wherein said creating rectangles step includes the steps of:

establishing a first rectangle having said width and a length substantially equal to said specified distance;

establishing subsequent rectangles between adjacent waypoints, said rectangles having said width and lengths substantially equal to distances between said adjacent waypoints; and

establishing a last rectangle between said end point and a last waypoint.

3. A method in accordance with claim 1 wherein said arcs are approximated with the steps of:

establishing a first vector between said given waypoint and a vertex of a rectangle terminating at said given waypoint;

noting said vertex of said terminating rectangle as an end point of said first vector;

establishing a second vector between said given waypoint and a vertex of a rectangle originating at said given waypoint;

noting said vertex of said originating rectangle as an end point of said second vector;

determining angular distance between said first and second vectors;

rotating said first vector by a selected angle to establish a third vector;

noting an end point of said third vector;

repeating rotations of a vector established by a previous rotation by said selected angle until said angular distance between said first and second vectors has been traversed;

noting end points of vectors determined by said repeating rotations; and

connecting said end points in a sequential manner to approximate said arcs.

4. A method in accordance with claim 1 further including the steps of:

forming buffer rectangles centered on said boundary having widths equal to twice a selected distance from said boundary and lengths equal to distances between vertices of said boundary;

forming buffer arcs between vertices of said buffer edges, said buffer edges and said buffer arcs establishing polygonal lines internal and external to said boundary; and

selecting said internal polygonal lines as a buffer boundary.

5. A method in accordance with claim 4 wherein said forming buffer arcs step includes the steps of:

establishing a first vector between a vertex of an end edge of a selected buffer rectangle and a point at which said end edge intersects said moving haven boundary;

noting said vertex of said selected buffer rectangle as an end point of said first vector;

establishing a second vector between a vertex of a leading edge of a buffer rectangle next adjacent to said selected buffer rectangle and a point at which said leading edge of said next adjacent rectangle intersects said boundary;

noting said vertex of said next adjacent rectangle as an end point of said second vector;

determining angular distance between said first and second vectors;

rotating said first vector by a selected angle to establish a third vector;

noting an end point of said third vector;

repeating rotations of a vector established by a previous rotation by said selected angle until said angular distance between said first and second vectors has been traversed;

noting end points of vectors determined by said repeating rotations; and

connecting said end points in a sequential manner to approximate said arcs.

6. A method for generating a moving haven boundary along a voyage plan comprising the steps of:

establishing an ordered list of points representing a polygonal line, said polygonal line indicative of said voyage plan;

providing a width of said moving haven boundary;

generating sets of line segments between said points, each set establishing a rectangle having said width and a length determined by a distance between adjacent points;

determining intersecting line segments of adjacent rectangles;

creating arcs between said intersecting line segments about obtuse angles at waypoints of said polygonal line; and

forming said moving haven boundary utilizing said arcs and line segments of said rectangles.

7. A method in accordance with claim 6 wherein said creating arcs step includes the steps of:

establishing a first vector along a first line segment of first and second intersecting line segments;

establishing a second vector along said second line segment;

determining angular distance between said first and second vectors;

rotating said first vector by a selected angle to establish a third vector;

repeating rotations of a vector established by a previous rotation by said selected angle until said angular distance between said first and second vectors has been traversed; and

connecting end points of said first, second, and third vectors and all vectors created by said repeating rotations in to establish arc representative line segments.

8. A method in accordance with claim 7 wherein said forming step includes the steps of:

combining said line segments and said arc representative line segments to provide a set of combined line segments;

identifying a starting line segment from said set of combined line segments, said starting line segment having a starting point and an ending point;

selecting a line segment intersecting said starting line segment in accordance with a predetermined selection criteria, thereby providing a selected line segment;

eliminating all line segments intersecting said starting segment other than said selected line segment;

repeating said selecting step using said selected line segment as said starting line segment until all line segments have been selected.

9. A method in accordance with claim 8 wherein said identifying step includes the steps of:

selecting line segments in said set of combined line segments that are entirely on or have a beginning on said moving haven boundary, thereby establishing an acceptable set of starting line segments;

locating line segments in said acceptable set that have start points at a preselected position in said moving haven, thereby providing a set of possible starting line segments, should only one such line segment be in said acceptable set, this line segment is chosen as a starting segment; and

choosing a line segment in said set of possible starting line segments that points mostly in a predetermined direction, should more than one line segment be in said acceptable set.

10. A method in accordance with claim 8 wherein said selecting step includes the steps:

finding all line segments intersecting said starting line segment, thereby establishing a set of intersecting line segments;

dropping all line segments in said set of intersecting line segments touching said starting point of said starting line;

eliminating all line segments in said set of intersecting line segments that do not result in a turn of a predetermined direction;

determining points of intersection with said starting line segment of line segments remaining in said set of intersecting line segments;

finding a point of intersection that is closest to said starting point of said starting line, thereby establishing a closest point of intersection;

eliminating all line segments that do not include said closest point of intersection;

selecting, from line segments remaining in said set of intersecting line segments a line, a line segment having a turn angle in said predetermined direction that is smaller than turn angles of all other line segments remaining in said set of intersecting line segments.

11. A method in accordance with claim 6 wherein said creating arcs step includes the steps of:

establishing a first vector along a first line segment;

establishing a second vector along a line segment intersecting said first line segment;

determining angular distance between said first and second vectors;

rotating said first vector by a selected angle to establish a third vector;

repeating rotations of a vector established by a previous rotation by said selected angle until said angular distance between said first and second vectors has been traversed;

connecting end points of said first, second, and third vectors and all vectors created by said repeating rotations in a sequential manner to establish arc representative line segments; and

including said arc representative line segments in said set of combined line segments.

12. A method in accordance with claim 6 further including the step of:

generating a buffer within said moving haven boundary having an outer buffer boundary at a selected distance from said moving haven boundary.

13. A method in accordance with claim 12 wherein said generating step includes the steps of:

constructing buffer rectangles centered on said moving haven boundary having widths equal to twice said selected distance and lengths equal to distances between corners and arcs of said moving haven boundary;

creating buffer arcs between said buffer edges of said buffer rectangles on either side of waypoints of said voyage plan, said buffer edges and said buffer arcs establishing polygonal lines internal and external to said boundary; and

selecting said internal polygonal lines as said buffer boundary.

14. A method in accordance with claim 13 wherein said creating buffer arcs step includes the steps of:

establishing a first vector between a vertex of an end edge of a selected buffer rectangle and a point at which said end edge intersects said moving haven boundary;

noting said vertex of said selected buffer rectangle as an end point of said first vector;

establishing a second vector between a vertex of a leading edge of a buffer rectangle next adjacent to said selected buffer rectangle and a point at which a leading edge of said next adjacent rectangle intersects said moving haven boundary;

noting said vertex of said next adjacent rectangle as an end point of said second vector;

determining angular distance between said first and second vectors;

rotating said first vector by a selected angle to establish a third vector;

noting an end point of said third vector;

repeating rotations of a vector established by a previous rotation by said selected angle until said angular distance between said first and second vectors has been traversed;

noting end points of vectors determined by said repeating rotations; and

connecting said end points in a sequential manner to approximate said arcs.

15. A method in accordance with claim 13 wherein said constructing step includes buffer start segment determining steps of:

selecting a line segment that is as least as long as all other line segments, thereby providing a selected line segment;

finding a center of said selected line segment, thereby establishing a first and second line segments, a first originating at said center and a second ending at said center; and

choosing one of said first and second line segments as said buffer start segment.

16. An apparatus for providing a moving haven boundary along a voyage plan comprising:

generator means for generating a polygonal line having line segments and waypoints of said voyage plan;

rectangle means coupled to said generator means for establishing rectangle line segments of rectangles along respective segments of said polygonal line, each rectangle centered on said polygonal line of said voyage plan, having a width equal to a preselected width of said moving haven and a length equal to its respective line segment length;

arc means coupled to said rectangle means for providing an arc between a trailing edge of a first rectangle and a leading edge of a second rectangle at a selected waypoint, said leading and trailing edges intersecting at said selected waypoint, said arc being represented by a series of arc line segments and formed about an obtuse angle formed by said polygonal line at said selected waypoint; and

boundary means coupled to said rectangle means and said arc means for generating said moving haven boundary.

17. An apparatus in accordance with claim 16 where said boundary means includes:

segment means coupled to said rectangle means and said arc means for combining said rectangle line segments and said arc line segments, thereby establishing a set of line segments;

start means coupled to said segment means for selecting a starting line segment from said set of line segments;

intersect means coupled to said start means and said segment means for selecting a line segment intersecting said starting line segment in accordance with a predetermined selection criteria, thereby selecting a second line segment; and

repeat means coupled to said intersect means and said segment means for designating said second line segment to said intersect means as a starting line segment and selecting a further line segment in accordance with said predetermined selection criteria and thereafter utilizing said further line segment as a starting line segment until all line segments in said segment means have been utilized.

18. An apparatus in accordance with claim 17 wherein said start means includes:

selector means coupled to said segment means for selecting line segments from said set of line segments that are entirely on or have a beginning on said moving haven boundary, thereby providing an acceptable starting line set;

locator means coupled to said selector means for providing line segments in said acceptable starting line set having a starting point at a preselected position, thereby providing a set of possible starting line segments; and

choice means coupled to said locator means for choosing a line segment in said set of possible starting line segments that points mostly in a predetermined direction.

19. An apparatus in accordance with claim 16 further including:

buffer rectangle means coupled to said boundary means for generating rectangles about said boundary polygonal line;

buffer arc means coupled to said buffer rectangle means for generating arcs between end edges of first rectangles and leading edges of second rectangles; and

buffer polygonal line means coupled to said buffer rectangle means and said buffer arc means for utilizing said rectangles and said arcs to establish a buffer polygonal line within said moving haven boundary.

20. An apparatus in accordance with claim 19 wherein said buffer arc means includes;

first vector means coupled to said buffer rectangle means for converting said end edges to first vectors;

second vector means coupled to said buffer rectangle means for converting said leading edges to second vectors;

angle means coupled to receive said first and second vectors for determining angles between corresponding first and second vectors;

rotator means coupled to receive said first vectors and said angles between corresponding first and second vectors for rotating said first vectors by preselected angular increments until said angles have been traversed; and

end point means coupled to receive rotated vectors for noting end points of vectors at each angular increment and coupling said end points to said buffer polygonal line said end points and said rectangles are utilized to establish said buffer polygonal line within said moving haven boundary.