Determining the convex hull of convex polygons with congruent corresponding angles

The convex hull of two polygons having congruent corresponding angles with the same orientation can be determined by analyzing the relationship of each vertex of one of the polygons relative to its adjacent vertices. More particularly a line may be defined between a selected vertex on one of the polygons and its corresponding vertex on the other polygon. If the vertices adjacent to the selected vertex both fall on the same side of the line, then a line connecting the selected vertex with its corresponding vertex lies on the convex hull of the two polygons. If, on the other hand, the vertices adjacent to the selected vertex are located on different sides of the line, then the line connecting the selected vertex with its corresponding vertex does not lie on the convex hull.

FIELD OF THE INVENTION

Various aspects of the present invention relate to the determination of the convex hulls of two convex polygons having congruent corresponding angles that are oriented in the same direction. Various aspects of the present invention are particularly applicable to the determination of the convex hull of two rectangles in order to, for example, render electronic ink between the rectangles.

BACKGROUND OF THE INVENTION

A “convex hull” is the set of points forming the smallest convex set that includes all of the points. Thus, the convex hull of two polygons is the smallest single convex polygon that encloses the two polygons. It is often useful in the field of computer science to obtain the convex hull of two polygons as quickly and efficiently as possible. For example, electronic ink may be rendered based upon a collection of sample points made with a stylus. If the electronic ink is intended to simulate the appearance of ink written with a chisel-tipped pen, then each of the sample points has a rectangular shape. Further, while the proportions of the rectangle for each sample point may be the same, the actual size of each rectangle may vary if the ink is created using a stylus and digitizer sensitive to pressure and angle differences in how the stylus is held. To accurately render the ink between two sample points, the sample points must be connected by lines that fully encompass the rectangle for each sample point. Thus, the rendered ink between two sample points is the convex hull encompassing the two rectangles making up the sample points.

As well as being useful for rendering electronic ink, a convex hull can also be used for other purposes in the field of computer science. For example, determining the convex hull of polygons is useful in rendering complex figures composed of convex polygons, such as in computer video games and other graphically-intensive applications. Similarly, a method for determining the convex hull of convex polygons can be used for tasks including collision detection between complex figures and determining whether one of the two polygons completely contains the other. In addition, there are a variety of other applications for techniques to determine the convex hull of two convex polygons.

While various techniques have been developed to calculate the convex hull of two polygons, these techniques are laborious and require a number of operations on the order of O(NlnN), where N is the number of vertices in each polygon. To render ink smoothly and in synchronism with the movement of the stylus, however, the ink must be generated and rendered very quickly. Accordingly, various aspects of the invention are directed to techniques for determining the convex hull of two polygons having congruent corresponding angles more quickly and efficiently than conventional techniques. Advantageously, various examples of the invention allow the convex hull to be determined using a number of operations on the order of O(N), rather than O(NlnN) as with conventional techniques.

BRIEF SUMMARY OF THE INVENTION

According to various aspects of the invention, the convex hull of two convex polygons having corresponding congruent angles with the same orientation can be determined by analyzing the relationship of each vertex of one of the polygons relative to its adjacent vertices. More particularly, for some examples of the invention, a line is defined between a selected vertex on one of the polygons and its corresponding vertex on the other polygon. If the vertices adjacent to the selected vertex both fall on the same side of the line, then that line lies on the convex hull of the two polygons. If, on the other hand, the vertices adjacent to the selected vertex are located on different sides of the line, then the line does not lie on the convex hull.

Typically, two lines are determined to lie on the convex hull of two convex polygons. These lines, together with the opposite sides of the polygons connected by the lines, form the convex hull for the two convex polygons. If no lines are determined to lie on the convex hull, then one of the polygons encloses the other entirely. With this arrangement, the outer polygon forms the convex hull of the two polygons. Alternately, three or more lines may be determined to lie on the convex hull, indicating that multiple vertices of each polygon are located on a single line forming the convex hull. If this occurs, two of the lines are selected, and the remaining lines are ignored. For example, when four lines passing through adjacent vertices are determined to lie on the convex hull, the first line is designated as a part of the convex hull, and the next line determined to lie on the convex hull (that is, the line terminating at the adjacent vertex) is ignored. Similarly, the third line determined to lie on the convex hull is designated as a part of the convex hull, and the fourth line determined to lie on the convex hull is ignored.

Various examples of the invention may use an even simpler technique to determine the convex hull of two rectangles oriented in the same direction. According to these aspects of the invention, the Cartesian coordinates of a selected vertex of one of the rectangles is compared with the Cartesian coordinates of the corresponding vertex of the other rectangle. More particularly, the difference in the x-coordinate values of the corresponding vertices is determined, together with the difference in the y-coordinate values of the corresponding vertices. If the selected vertex has the highest or lowest x-coordinate and y-coordinate values, and the differences have different sign values, then a line between the selected vertex and its corresponding vertex lies on the convex hull. If however, the differences have the same sign values, then a line between the vertices will not lie on the convex hull of the rectangles.

On the other hand, if the selected vertex does not have the highest x-coordinate and y-coordinate values or the lowest x-coordinate and y-coordinate values, and the coordinate value differences have the same sign values, then a line between the selected vertex and its corresponding vertex lies on the convex hull. If however, the x-coordinate and y-coordinate differences for this selected vertex have different sign values, then a line between the vertices will not lie on the convex hull of the two rectangles.

DETAILED DESCRIPTION OF THE DRAWINGS

Overview

As will be discussed in detail below, various embodiments of the invention provide a fast and efficient method for determining the convex hull between two convex polygons having congruent corresponding angles with the same orientation. Accordingly, an example environment in which different embodiments of the invention can be implemented will first be discussed. Also, in order to facilitate a better understanding of the invention, different geometric concepts, such as convex polygons, congruent corresponding angles and convex hulls will be discussed. Various embodiments of the invention for determining the convex hull of different polygons will then be described as well.

Example Operating Environment

Various techniques for determining the convex hull of convex polygons with congruent corresponding angles having the same orientation according to different embodiments of the invention may be implemented using software. That is, a tool for determining the convex hull of two convex polygons with congruent corresponding angles having the same orientation may be described in the general context of computer-executable instructions, such as program modules, executed by one or more computing devices. Generally, program modules include routines, programs, objects, components, data structures, etc. that each may perform particular tasks or implement particular abstract data types. Typically the functionality of the program modules may be combined or distributed as desired in various embodiments.

Because various embodiments of the invention may be implemented using software, it may be helpful for a better understanding of the invention to briefly discuss the components and operation of a typical programmable computer on which some embodiments of the invention may be implemented. Accordingly,FIG. 1illustrates an example of a computing device101that provides a suitable operating environment by which various embodiments of the invention may be implemented. This operating environment is only one example of a suitable operating environment, however, and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Other well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

The computing device101typically includes at least some form of computer readable media. Computer readable media can be any available media that can be accessed by the computing device101. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, punched media, holographic storage, or any other medium which can be used to store the desired information and which can be accessed by the operating environment101.

With reference toFIG. 1, in its most basic configuration the computing device101typically includes a processing unit103and system memory105. Depending on the exact configuration and type of computing device101, the system memory105may include volatile memory107(such as RAM), non-volatile memory109(such as ROM, flash memory, etc.), or some combination of the two memory types. Additionally, device101may also have mass storage devices, such as a removable storage device111, a non-removable storage device113, or some combination of these two storage device types. The mass storage devices can be any device that can retrieve stored information, such as magnetic or optical disks or tape, punched media, or holographic storage. The system memory105and mass storage devices111and113are examples of computer storage media.

The device101may have one or more input devices115as well, such as a keyboard, microphone, scanner or pointing device, for receiving input from a user. The device101may also have one or more output devices117for outputting data to a user, such as a display, a speaker, printer or a tactile feedback device. Other components of the device101may include communication connections119to other devices, computers, networks, servers, etc. using either wired or wireless media. As will be appreciated by those of ordinary skill in the art, the communication connections119are examples of communication media. All of these devices and connections are well know in the art and thus will not be discussed at length here.

Use of Polygons for Rendering Images

As will be appreciated by those of ordinary skill in the art, one form of output for the computing device101is the rendering of images on a display screen, such as a cathode ray tube (CRT) display, a liquid crystal display (LCD), a plasma display or an organic material display. For example, a user may employ the computing device101to implement a software program for receiving and storing pointing device data in the form of electronic ink. In addition to receiving and storing the pointing device data, the computing device101may also display images corresponding to the received pointing device data.

While images rendered on a display by a computing device101may appear to have smooth curves, often the images are formed by polygons having straight edges rather than by curved lines. As shown inFIGS. 2 and 3, a polygon may be convex or concave. A polygon is convex if no two points on the perimeter of the polygon can be connected by a line that is not entirely contained within the polygon. Thus, the hexagon201shown inFIG. 2is convex, because no two points on the perimeter of the polygon can be connected by a straight line without that line being contained entirely within the hexagon201. The polygon301illustrated inFIG. 3, on the other hand, is not convex (that is, the polygon301is concave). As may be seen in this figure, a line303may connect the vertex305to the vertex307without passing through the polygon301.

In order to render curved shapes to appear as smooth as possible, polygons forming an image are typically connected by straight lines that do not leave any “protruding” vertices of the polygons. More particularly, the polygons are typically connected by straight lines that enclose the polygons in the smallest amount of space to create a new convex polygon. This enclosed area formed by the connecting lines is often referred to as a “convex hull.”

FIG. 4illustrates two polygons401and403. As seen in this figure, a straight line connects each vertex of the polygon401to a corresponding vertex of the polygon403. A first line405thus connects the vertex1of the polygon401to the vertex1of the polygon403. Likewise, a first line407connects the vertex2of the polygon401to the vertex2of the polygon403, while a second line405connects the vertex3of the polygon401to the vertex3of the polygon403. A second line407then connects the vertex4of the polygon401to the vertex4of the polygon403. It should be noted, however, that the first line407connecting the vertex2of the polygon401to the vertex2of the polygon403does not enclose the vertex1of the polygon403. Similarly, the second line407connecting the vertex4of the polygon401to the vertex4of the polygon403does not enclose the vertex3of the polygon401. Accordingly, neither of lines407lies on the perimeter of the convex hull of the polygons401and403. On the other hand, the area formed by connecting the polygons401and403by the lines405encompasses every vertex of both polygons401and403to form a convex shape. Thus, connecting the polygons401and403by the lines405forms the convex hull of the polygons.

As noted above, determining the convex hulls of two convex polygons is often useful for a variety of tasks relating to the rendering of images. Various techniques for rendering electronic ink, for example, may use the convex hull of two convex polygons having congruent corresponding angles with the same orientation. More particularly, with some techniques for rendering electronic ink, a user manipulates a pointing device, such as a stylus contacting a digitizing surface, to form a series of points. Depending upon the desired appearance of the electronic ink, each point may be rendered by a circle or a polygon. Thus, if the electronic ink is to have the appearance of ink created with a regular ball point pen or pencil, then each of the points may be rendered by a circle. If, however, the electronic ink is to have the appearance of ink written with a chisel-tipped pen, then each of the points may be rendered by a rectangle, such as an elongated rectangle or square.

For example,FIG. 5illustrates a group of rectangle polygons501,503,505and507each polygon corresponding to a point of the electronic ink formed by moving a stylus over a digitizing surface. With the illustrated polygons501,503,505and507the size of each polygon depends upon the pressure applied with stylus at the time when the point was created. Thus, the larger polygon501reflects a greater stylus pressure than the smaller polygon505.

In order to render the entire length of the electronic ink formed by the points represented by the polygons501,503,505and507, a convex hull is determined for sequentially-formed polygons501,503,505and507. More particular, for each polygon501,503,505and507, a convex hull is determined that encompasses the polygon and the polygon formed immediately before it (or immediately after it). Thus, as shown inFIG. 6, lines601are determined that form convex hulls encompassing each of the polygons501,503,505and507. The convex hulls are then rendered to display the entire length of the electronic ink. Moreover, because the convex hulls encompass the polygons501,503,505and507of different sizes, the rendered electronic ink displays differences in width corresponding to the amount of pressure applied by the stylus against the digitizing surface, just as real ink would show a difference in width corresponding to the amount of pressure applied by, for example, a felt-tip pen against paper.

Determining the Convex Hull for Similar Rectangles

As noted above, it is often very useful to determine the convex hulls of two rectangles. (As used herein, the term “rectangles” encompasses both elongated rectangles and squares.)FIG. 7Aillustrates the relationship between two such rectangles701and703. In this example, the rectangles701and703have the same orientation. That is, each vertex of the rectangle701can be exactly overlaid onto its corresponding vertex of the rectangle703without having to rotate either vertex.FIG. 7Aalso includes a compass alignment, to provide a context in which to more precisely describe the relationship between the rectangle701and the rectangle703. As seen in this figure, the north-south direction of the compass alignment is parallel to the sides of the rectangles701and703. Using this compass alignment, the rectangle701may be described as southwest of the rectangle703, while the rectangle703may be described as northeast of the rectangle701. That is, each vertex of the rectangle701is southwest of its corresponding vertex in the rectangle703, while each vertex in the rectangle703is northeast of its corresponding vertex in the rectangle703.

Thus, the northwestern-most vertex of the rectangle701(labeled as vertex1) is southwest of the corresponding northwestern-most vertex of the rectangle703(also labeled as vertex1). Alternately, vertex1of the rectangle703may be considered to be northeast of vertex1of the rectangle701. Similarly, the northeastern-most vertex of rectangle701(labeled as vertex2) is southwest of the corresponding northeastern-most vertex of the rectangle703(also labeled as vertex2), while vertex2of the rectangle703is northeast of the corresponding vertex2of the rectangle701. The southeastern-most vertex of the rectangle701(labeled as vertex3) is also southwest of the corresponding southeastern-most vertex of rectangle703(labeled as a vertex3as well). Lastly, the southwestern-most vertex of the rectangle701(labeled as vertex4) is southwest of the corresponding southwestern-most vertex of the rectangle703(also labeled as a vertex4). The lines705then lay on the perimeter of the convex hull of the two rectangles701and703.

FIG. 7Billustrates a different relationship between rectangles701and703′. As seen in this figure, the rectangle703′ is southeast of the rectangle701, or, alternately stated, the rectangle701is northwest of the rectangle703′. That is, each vertex in the rectangle703′ is southeast of its corresponding vertex in the rectangle701, while each vertex in the rectangle701is northwest of its corresponding vertex in the rectangle703′. As will be appreciated from this figure, when the rectangles701and703are in this relationship, the perimeter of the convex hull of these rectangles includes a first connecting line705connecting the vertex2of each rectangle, and a second connecting line705connecting the vertex4of each rectangle.

FIG. 7Cillustrates still another relationship between rectangles701′ and703. As seen in this figure, the rectangle701′ is north of the rectangle703. More particularly, the northwestern-most vertex of the rectangle701′ (labeled as vertex1) is northwest of the corresponding northwestern-most vertex of the rectangle703(also labeled as vertex1). Alternately, vertex1of the rectangle703may be considered to be southeast of vertex1of the rectangle701′. The northeastern-most vertex of rectangle701′ (labeled as vertex2) is northeast of the corresponding northeastern-most vertex of the rectangle703(also labeled as vertex2), while vertex2of the rectangle703is southwest of the corresponding vertex2of the rectangle701′. The southeastern-most vertex of the rectangle701′ (labeled as vertex3) is also northeast of the corresponding southeastern-most vertex of rectangle703(labeled as a vertex3as well). Alternately, vertex3of the rectangle703is southwest of the corresponding vertex3of the rectangle701′. Lastly, the southwestern-most vertex of the rectangle701′ (labeled as vertex4) is northwest of the corresponding southwestern-most vertex of the rectangle703(also labeled as a vertex4), or, as may be alternately stated, vertex4of the rectangle703is southeast of its corresponding vertex4of the rectangle701′.

As seen in these figures, when the northwestern-most vertex1of a rectangle is in a northeast-southwest relationship with the northwestern-most vertex1of another rectangle having the same orientation, then a line connecting the northwestern-most vertex1of the rectangle to the northwestern-most vertex of the other rectangle lies on the convex hull of the two rectangles. If, however, the northwestern-most vertex1of a rectangle is not in a northeast-southwest relationship with the northwestern-most vertex1of the other rectangle, then a line connecting the two vertices will not lay on the convex hull of the two rectangles. Similarly, when the southeastern-most vertex3of a rectangle is in a northeast-southwest relationship with the southeastern-most vertex3of another rectangle having the same orientation, then a line connecting the southeastern-most vertex3of the rectangle to the southeastern-most vertex of the other rectangle lies on the convex hull of the two rectangles. If the southeastern-most vertex3of a rectangle is not in a northeast-southwest relationship with the southeastern-most vertex3of the other rectangle, then a line connecting the two vertices will not lay on the convex hull of the two rectangles.

It will also be noted fromFIGS. 7A–7Cthat, when the northeastern-most vertex2of a rectangle is in a northwest-southeast relationship with the northeastern-most vertex2of another rectangle having the same orientation, then a line connecting the northeastern-most vertex2of the rectangle to the northeastern-most vertex2of the other rectangle lies on the convex hull of the two rectangles. If, however, the northeastern-most vertex2of a rectangle is not in a northwest-southeast relationship with the northeastern-most vertex2of the other rectangle, then a line connecting the two vertices will not lay on the convex hull of the two rectangles. Similarly, when the southwestern-most vertex4of a rectangle is in a northwest-southeast relationship with the southwestern-most vertex4of another rectangle having the same orientation, then a line connecting the southwestern-most vertex4of the rectangle to the southwestern-most vertex of the other rectangle lies on the convex hull of the two rectangles. If the southwestern-most vertex4of a rectangle is not in a northwest-southeast relationship with the southwestern-most vertex4of the other rectangle, then a line connecting the two vertices will not lay on the convex hull of the two rectangles.

As will now be described, these relationships may be used by various embodiments of the invention to determine the convex hull of two rectangles having a same orientation.FIG. 8illustrates a tool801for determining the convex hull of two similar polygons having the same orientation, such as the similar rectangles701and703illustrated inFIGS. 7A and 7B. The tool801includes a vertex identification module803, a vertex relationship determination module805, and a convex hull determination module807. The tool801may also optionally include a convex hull rendering module809. The operation of the tool801in determining the convex hull of two rectangles having the same orientation, such as rectangles701and703, will be described in more detail with reference toFIG. 9.

To begin the process of determining the convex hull of two similar rectangles having the same orientation, the vertex identification module803first identifies the vertices of each of the rectangles. For example, as illustrated inFIG. 9, the vertex identification module803may identify each vertex of each rectangle according to Cartesian coordinates defined by an x-direction axis901parallel to the sides of the rectangles and a y-direction axis903parallel to the tops and bottoms of the rectangles. As will be appreciated by those of ordinary skill in the art, Cartesian coordinates may be used to define any point in a two-dimensional area with a single coordinate value along the x-direction axis901and a single coordinate value along the y-direction axis903. Thus, each vertex of rectangle701and each vertex of rectangle703may be defined by a single pair of “x” and “y” coordinate values. With various embodiments of the invention, the x-direction axis901may or may not include negative values. Similarly, with various embodiments of the invention, the y-direction axis903may or may not include negative values.

Accordingly, the vertex identification module803may employ the Cartesian coordinates of the vertices to identify each vertex of a rectangle and its corresponding vertex in the other rectangle. The vertex identification module803may, for example, identify the vertex of the rectangle701having the highest “y” coordinate value and the lowest “x” coordinate value as vertex1of the rectangle701. The vertex identification module803may then identify the vertex of rectangle703having the highest “y” coordinate value and the lowest “x” coordinate value as the corresponding vertex1of the rectangle703. Similarly, the vertex identification module803may then identify the vertex of the rectangle701having the highest “y” coordinate value and the highest “x” coordinate value as vertex2of the rectangle701, and identify the vertex of the rectangle703having the highest “x” coordinate and value and the highest “y” coordinate value as the corresponding vertex2of the rectangle703.

As shown inFIG. 9, the vertex identification module803may then identify the vertex of the rectangle701having the lowest “y” coordinate value and the highest “x” coordinate value as vertex3of the rectangle701, and identify the vertex of the rectangle703having the lowest “y” coordinate value and the highest “x” coordinate value as the corresponding vertex3of the rectangle703. Lastly, the vertex identification module803may identify the vertex of the rectangle701having both the lowest “y” coordinate value and the lowest “x” coordinate value as vertex4of the rectangle701. The vertex identification module803may then identify the vertex of the rectangle703having both the lowest “y” coordinate value and the lowest “x” coordinate value as the corresponding vertex4of the rectangle703.

Thus, the vertex identification module803identifies each vertex of each rectangle, and further identifies the corresponding pairs of vertices in each rectangle. It should be noted, however, that while each vertex inFIG. 9is labeled with a number from 1 through 4, any technique may be employed to identify corresponding vertices in the rectangles. For example, the x and y coordinate values of vertices may be designated as corresponding by storing the coordinates together in a predetermined memory location, rather than identifying each vertex with a matching identifying label.

Once the vertex identification module803has identified each vertex, the vertex relationship determination module805determines the relationship between the corresponding vertices in each rectangle. More particularly, the vertex relationship determination module805determines whether the vertices in each pair of corresponding vertices are in a northeast-southwest relationship or in a northwest-southeast relationship. According to various embodiments of the invention, the vertex relationship determination module805may employ the Cartesian coordinates for a pair of corresponding vertices to determine the relationship between the rectangles. More particularly, the vertex relationship determination module805may obtain the differences in the x-coordinate and y-coordinate values between any of the corresponding vertices of the rectangles to determine the relationship between the rectangles.

For example, with the rectangles701and703illustrated inFIGS. 7A–7C, the vertex relationship determination module805may obtain the difference between the x-coordinate value for the vertex1of the rectangle701and the x-coordinate value for the vertex1of the rectangle703. The vertex relationship determination module805may then also obtain the difference between the y-coordinate value for the vertex1of the rectangle701and the y-coordinate value for the vertex1of the rectangle703. If the difference in the x-coordinate values and the y-coordinate values share the same sign (that is, if the x-coordinate value difference and the y-coordinate value difference are both positive or are both negative), then the rectangles have a northeast-southwest relationship.

Thus, referring now toFIG. 7A, based upon the Cartesian coordinate system ofFIG. 9, the x-coordinate value of vertex1of the rectangle703has a higher value than the x-coordinate value of vertex1of the rectangle701. The x-coordinate value difference therefore will be positive. Similarly, the y-coordinate value of vertex1of the rectangle703has a higher value than the y-coordinate value of vertex1of the rectangle701, so the y-coordinate value difference will be positive as well. Accordingly, the vertices1of rectangles701and703shown inFIG. 7Aare in a northeast-southwest relationship.

On the other hand, if the differences in the x-coordinate values and the y-coordinate values have different signs (that is, if the x-coordinate value difference is positive and the y-coordinate value difference is negative, or if the x-coordinate value difference is negative and the y-coordinate value difference is positive), then the rectangles have a southeast-northwest relationship. For example, referring now toFIG. 7B, the x-coordinate value of vertex1of the rectangle703′ has a higher value than the x-coordinate value of vertex1of the rectangle701, so the x-coordinate value difference will be positive. The y-coordinate value of vertex1of the rectangle703′ has a lower value than the y-coordinate value of vertex1of the rectangle701, however, so the y-coordinate value difference will be negative.

While the above example considered only vertex1of the rectangle701and the corresponding vertex1of the rectangle703, it should be appreciated that the relationship between the rectangles may be obtained by comparing the difference in the x-coordinate values for a pair of corresponding vertices with the difference in the y-coordinate values of the same pair of corresponding vertices for each pair of corresponding vertices. By examining each pair of corresponding vertices, the vertex relationship determination module805can accurately determine the convex hull of the rectangles.

More particularly, when the vertex relationship determination module805determines that the x-coordinate value difference and the y-coordinate value difference for the corresponding vertices with both the highest x-coordinate value and the highest y-coordinate value have different signs, then the convex hull determination module807determines that the perimeter of the convex hull of the rectangles includes a line connecting these vertices. If, however, the convex hull determination module807determines that the x-coordinate and y-coordinate differences for these vertices have the same sign, then the convex hull determination module807determines that the line connecting these vertices will not lay on the perimeter of the convex hull of the rectangles.

Similarly, when the vertex relationship determination module805determines that the x-coordinate value difference and the y-coordinate value difference for the corresponding vertices with both the lowest x-coordinate value and the lowest y-coordinate value have different signs, then the convex hull determination module807determines that the perimeter of the convex hull of the rectangles includes a line connecting these vertices. If, however, the convex hull determination module807determines that the x-coordinate and y-coordinate differences for these vertices have the same sign, then the convex hull determination module807determines that the line connecting these vertices will not lay on the perimeter of the convex hull of the rectangles.

When the vertex relationship determination module805determines that the x-coordinate value difference and the y-coordinate value difference for the corresponding vertices with the highest x-coordinate value and the lowest y-coordinate value have the same signs, then the convex hull determination module807determines that the perimeter of the convex hull of the rectangles includes a line connecting these vertices. If, however, the convex hull determination module807determines that the x-coordinate and y-coordinate differences for these vertices have different signs, then the convex hull determination module807determines that the line connecting these vertices will not lay on the perimeter of the convex hull of the rectangles.

Further, if the vertex relationship determination module805determines that the x-coordinate value difference and the y-coordinate value difference for the corresponding vertices with the lowest x-coordinate value and the highest y-coordinate value have the same signs, then the convex hull determination module807determines that the perimeter of the convex hull of the rectangles includes a line connecting these vertices. If, however, the convex hull determination module807determines that the x-coordinate and y-coordinate differences for these vertices have different signs, then the convex hull determination module807determines that the line connecting these vertices will not lay on the perimeter of the convex hull of the rectangles.

It should be noted that, in some situations, the x-coordinate difference or the y-coordinate difference may be zero. The zero value may be treated as either positive or negative. As long as this value of zero is consistently assigned a positive or negative sign, the convex hull determination module807can determine all of the connecting lines between corresponding vertices that lay on the perimeter of the convex hull.

Once the convex hull determination module807determines the two connecting lines forming the perimeter of the convex hull of the rectangles, it then can determine the entire perimeter of the convex hull. More particularly, the convex hull determination module807may select a single vertex that will always be included in the convex hull perimeter. For example, the convex hull determination module807may select one of the vertices in a rectangle that is connected to its corresponding vertex in the other rectangle by the perimeter of the convex hull. By traveling along any connecting lines in a consistent direction (that is, either clockwise or counterclockwise), the convex hull determination module807will travel along the lines forming the perimeter of the convex hull.

Thus, referring toFIG. 7A, if the convex hull determination module807begins at vertex3of rectangle703, it may travel in a clockwise direction along the lower connecting line705to the vertex3of rectangle701(rather than along the line connecting vertex3of rectangle703to vertex4of rectangle703). Using this technique, the convex hull determination module807will then travel to vertex4of rectangle701, from there up to vertex1, and then along the upper connecting line705to vertex1of the rectangle703. From vertex1of the rectangle703, the convex hull determination module807will travel to vertex2of the rectangle703, and then return to vertex3of the rectangle703. In this manner, the convex hull determination module807can define the perimeter of the convex hull of the rectangles. Of course, still other techniques may be employed to define the entirety of the perimeter of the convex hull after the connecting lines between the rectangles have been determined. Once the convex hull determination module807has defined the perimeter of the convex hull of the two rectangles, then the convex hull rendering module809may render the defined convex hull on a display.

Determining the Convex Hull for all Types of Convex Polygons

While the various embodiments of the invention described above provide fast and efficient techniques for determining the convex hull of two similar rectangles having the same orientation, it is often useful to determine the convex hull of a variety of types of convex polygons. Advantageously, various aspects of the invention provide techniques for determining the convex hull of any pair of convex polygons having congruent corresponding angles with the same orientation. Two convex polygons have congruent corresponding angles when the angle of each vertex in one of the polygons is the same as the angle of the corresponding vertex in the other polygon. Moreover, the angles of two polygons have the same orientation when each vertex of one of the polygons can be exactly overlaid onto the vertex of the other polygon without having to rotate the vertex (that is, by only moving the vertex up, down, left or right).

Referring now toFIG. 10, this figure illustrates one possible relationship between two similar pentagons having the same orientation. As seen in this figure, the pentagon1001has five vertices labeled sequentially with numbers1–5. The pentagon1003also has five vertices labeled sequentially with numbers1–5. As will be apparent from this figure, vertex1of the pentagon1001corresponds to vertex1of the pentagon1003, and the angle of vertex1of the pentagon1001forms the same angle and has the same orientation as vertex1of the pentagon1003. Similarly, vertex2of the pentagon1001corresponds to vertex2of the pentagon1003, and the angle of vertex2of the pentagon1001forms the same angle and has the same orientation as vertex2of the pentagon1003. Likewise, vertex3of the pentagon1001corresponds to vertex3of the pentagon1003, and the angle of vertex3of the pentagon1001forms the same angle and has the same orientation as vertex3of the pentagon1003. Vertex4of the pentagon1001then corresponds to vertex4of the pentagon1003, and the angle of vertex4of the pentagon1001forms the same angle and has the same orientation as vertex4of the pentagon1003. Lastly, vertex5of the pentagon1001corresponds to vertex5of the pentagon1003, and the angle of vertex5of the pentagon1001forms the same angle and has the same orientation as vertex5of the pentagon1003.

Turning now to vertex1of the pentagon1001in more detail, the polygon segments forming vertex1may be extended to define four regions. More particularly, the line segment connecting vertex1to vertex2may be extended to form a line1005. The line segment connecting vertex1to vertex5similarly may be extended to form a line1007. Together, the intersection of lines1005and1007define four regions:1009,1011,1013and1015. As will be discussed in further detail, the perimeter of the convex hull of the two polygons will only contain a line connecting vertex1of the pentagon1001with the corresponding vertex1of the pentagon1003if vertex1of the pentagon1003falls within the region1011or the region1015. If vertex1of the pentagon1003instead falls within the region1009or the region1013, then the convex hull will not include a line connecting vertex1of pentagon1001with its corresponding vertex1of pentagon1003.

As shown inFIG. 10, vertex1of pentagon1003does not lie within either of region1011or region1015. Instead, vertex1of the pentagon1003falls within region1013. A straight line1017connecting vertex1of the pentagon1001to vertex1of the pentagon1003thus passes between vertices3–5and vertex2of the pentagon1001. Thus, a polygon that included the line1017would allow vertex2of the pentagon1001to “protrude” from its perimeter, making the polygon concave. The line1017therefore cannot be included in the perimeter of the convex hull of pentagons1001and1003.

Turning now toFIG. 11, in this figure vertex1of pentagon1003also does not lie within either of region1011or region1015, but instead falls within region1009. Accordingly, a straight line1101connecting vertex1of the pentagon1001to vertex1of the pentagon1003, if extended, would still pass between vertices2–4and vertex5of the pentagon1001. A polygon that included the line1101therefore would allow vertex5of the pentagon1001to “protrude” from its perimeter so as to make the polygon concave. The line1101therefore also cannot be included in the perimeter of the convex hull of pentagons1001and1003.

InFIG. 12, vertex1of pentagon1003does lay within the region1015. Thus, a polygon that included the line1201connecting vertex1of the pentagon1001to vertex1of the pentagon1003would not allow either vertex2or vertex5to protrude from its perimeter. Rather, the vertices2and5adjacent to the connected vertex1both fall on the same side of the line1201, so that a polygon including the polygon1001, the polygon1003and the line1201would be convex. The line1201therefore should be included in the perimeter of the convex hull of pentagons1001and1003.

From the above examples, it should be noted that a line passing through two corresponding vertices will determine if the vertices may be connected to form the perimeter of a convex. If a line extending from one vertex through its corresponding vertex splits the vertices adjacent to its corresponding vertex (as shown inFIGS. 10 and 11), then the corresponding vertices should not be connected to form the perimeter of a convex hull. If however, both adjacent vertices fall on the same side of a line extended through corresponding vertices (as shown inFIG. 12), then a line connecting the two vertices can form a portion of the perimeter of the convex hull of the two polygons. Accordingly, when various embodiments of the tool801are employed to determine the convex hull of two similar convex polygons having the same orientation, these embodiments of the tool801may use lines passing through each pair of corresponding vertices to determine which vertices should be connected to form the convex hull of the two polygons.

More particularly, the vertex identification module803will identify the vertices of each polygon. Further, the vertex identification module803will identify pairs of corresponding vertices between the polygons. For example, the vertex identification module803may identify each vertex in one of the polygons as vertex A(k), such that the value of k will range from 1 to N where N is the total number of vertices in the polygon. The vertex identification module803may then also identify each vertex in the other polygon as vertex B(k), where the vertex B(k) in the second polygon corresponds to vertex A(k) in the first polygon.

Next, the vertex relationship determination module805will examine the relationship between each pair of corresponding vertices. For example, the vertex relationship determination module805may define a line extending through both a selected vertex on one of the polygons and its corresponding vertex on the other polygon. That is, the vertex relationship determination module805may define a line extending through both vertex A(k) and vertex B(k). If the vertices adjacent to the selected vertex both fall on the same side of the line, then the convex hull determination module807determines that a connecting line connecting the vertices may be included in the perimeter of the convex hull of the two polygons. More particularly, if both the vertices A(k−1) and A(k+1) (or, alternately, both the vertices B(k−1) and B(k+1) fall on the same side of the line, then the convex hull determination module807determines that a connecting line connecting the vertices A(k) and B(k) may be included in the perimeter of the convex hull of the two polygons.

If, on the other hand, the vertices adjacent to the selected vertex are located on different sides of the line, then the vertices are not connected to form the convex hull. That is, if the vertices A(k−1) and A(k+1) (or, alternately, the vertices B(k−1) and B(k+1) fall on the different sides of the line, then the convex hull determination module807determines that a line connecting the vertices A(k) and B(k) will not be included in the perimeter of the convex hull of the two polygons. Thus, the vertex relationship determination module805examines a line extending through each pair of corresponding vertices for the two polygons, and the convex hull determination module807then determines, based upon the position of the vertices adjacent to the selected vertex, whether the selected vertex and its corresponding vertex should be connected.

It should be noted that, in some arrangements, one or both of the vertices adjacent to the selected vertex (that is, A(k−1), A(k+1) or both) may actually lie on the line extending through the selected vertex and its corresponding vertex in the second polygon. An adjacent vertex falling on the extending line may either be considered “above” the line or “below” the line. As long as the treatment of an adjacent vertex falling on the extending line is consistently used for all vertices, the convex hull determination module807will be able to determine if a line connecting the selected vertex in the first polygon to its corresponding vertex in the second polygon will lay on the convex hull of the polygons.

In this manner, the vertex relationship determination module805and the convex hull determination module807identify all possible corresponding vertices pairs that can be connected to form the convex hull. Once the lines connecting the vertices pairs have been determined, the convex hull determination module807may travel along the perimeter of the polygons and the connecting lines as described in detail above to determine the perimeter of the convex hull. The convex hull rendering module809may then render the convex hull defined by the convex hull determination module807.

Convex Hulls with more or Less than Two Connecting Lines

Typically, two similar convex polygons having congruent corresponding angles with the same orientation will have only two lines connecting corresponding vertices to form the convex hull of the polygons. In some situations, however, the tool801may be unable to identify even a single line in the convex hull perimeter that connects corresponding vertices of the polygons. When this occurs, at least in some instance, one of the polygons encompasses the other polygon entirely. Accordingly, the convex hull determination module807will determine which of the polygons encompasses the other. Various techniques for making this determination are well known in the art, and thus will not be described in further detail here. Once the encompassing polygon is identified, the convex hull determination module807can then designate that encompassing polygon as the convex hull of both polygons.

In still other situations, the tool801may identify three or more connecting lines between the two polygons, where the connected vertices of each polygon are adjacent. For example, the tool801may determine that each of vertices1,2and3of two rectangles, such as the rectangles701and703ofFIGS. 7A and 7B, should be connected, rather than vertices1and3or vertices2and4. This situation occurs, for example, when at least one side of each polygon falls on the same line (e.g., a horizontal or vertical line). For example, if both of the vertices defining one side of a first polygon shared the same x-coordinate value as both of the vertices defining the corresponding side of the second polygon, then tool801may identify three or more connecting lines between the polygons. When this occurs, the tool801may simply disregard one of two connecting lines connecting adjacent vertices. More particularly, the tool801may arrange each pair of connected vertices in sequence, and simply ignore the connecting line for every other pair of vertices in the list.

For example, the tool801may determine that the convex hull of two identical rectangles (such as the rectangles701and701shown inFIGS. 7A–7B) that are side-by-side should include a first connecting line connecting the corresponding vertices1, a second connecting line connecting the corresponding vertices2, a third connecting line connecting the corresponding vertices3, and a fourth connecting line connecting the corresponding vertices4. In this situation, the tool801may determine that the convex hull includes only the connecting lines connecting the vertices1and3, and disregard the connecting lines connecting the vertices2and4. Alternately, the tool801may determine that the convex hull includes only the connecting lines connecting the vertices2and4, and disregard the connecting lines connecting the vertices1and3. In these situations, the use of either connecting line connecting two adjacent vertices will accurately produce the convex hull of the polygons.

Conclusion