Open main menu

Difference between revisions of "SCI/FreeSCI/Pathfinding/Patent"

m
Deleting repeated reference, fixing broken link to pdf file to a newer location of the same file
m (Adding link to the patent to the espacenet database, change "Notes" to "References")
m (Deleting repeated reference, fixing broken link to pdf file to a newer location of the same file)
Line 1: Line 1:
=Patent=
=Patent=
In Section "Patents and infringement" we provide a brief discussion on patents and patent infringement. In Section "Sierra's pathfinding patent" we summarize Sierra's pathfinding patent. <ref>K. A. Williams, D. C. Iden and L. L. Scott. System and methods for intelligent movement on computer displays, [http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US5287446 US PATENT 5287446] , 1990.</ref>
In Section "Patents and infringement" we provide a brief discussion on patents and patent infringement. In Section "Sierra's pathfinding patent" we summarize Sierra's pathfinding patent. <ref name="displaymove">K. A. Williams, D. C. Iden and L. L. Scott. System and methods for intelligent movement on computer displays, [http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US5287446 US PATENT 5287446] , 1990.</ref>


==Patents and infringement==
==Patents and infringement==
A patent gives its holder the right to exclude others from using his or her invention. In exchange for that right the patent holder must fully disclose the invention in the patent document. After the patent expires others may use the invention. A patent document consists of two parts, the specification and the claims.
A patent gives its holder the right to exclude others from using his or her invention. In exchange for that right the patent holder must fully disclose the invention in the patent document. After the patent expires others may use the invention. A patent document consists of two parts, the specification and the claims.


The specification section describes the invention in detail using everyday language. The claim section defines exactly what is patented. It uses a legal jargon that is difficult to understand for non-patent professionals. Information on how to interpret patent claims can be found in.<ref>H. M. Eisenberg. Patent law you can use. Reading a Patent - Part II The Description and the Claims, http://www.yale.edu/ocr/invent_guidelines/docs/reading_patent2_claims.pdf, 1999.</ref> For some patents infringement can be avoided by providing extra functionality on top of what is patented. Whether or not this is the case depends on the exact wording of the claims. For Sierra's pathfinding patent this is not the case. This means that a substantially different algorithm is required to avoid infringement.
The specification section describes the invention in detail using everyday language. The claim section defines exactly what is patented. It uses a legal jargon that is difficult to understand for non-patent professionals. Information on how to interpret patent claims can be found in.<ref>H. M. Eisenberg. [http://www.yale.edu/ocr/pfg/guidelines/docs/reading_patent2_claims.pdf Patent law you can use. Reading a Patent - Part II The Description and the Claims] (pdf), 1999.</ref> For some patents infringement can be avoided by providing extra functionality on top of what is patented. Whether or not this is the case depends on the exact wording of the claims. For Sierra's pathfinding patent this is not the case. This means that a substantially different algorithm is required to avoid infringement.


==Sierra's pathfinding patent==
==Sierra's pathfinding patent==
The AvoidPath input consists of a start point and an end point and a set of constraining polygons.<ref>    K. A. Williams, D. C. Iden and L. L. Scott. System and methods for intelligent movement on computer displays, United States Patent No. 5287446, 1990.</ref> The output is a path from start point to end point that does not violate any constraints. The patent states that polygons can be assumed not to be self-intersecting. The patent further implies that a point cannot be inside two or more polygons. From that we conclude that any two polygons can be assumed not to intersect. The patent describes three optimization levels. We label these from 0 (no optimization) to 2 (maximum optimization). The optimization levels determine how optimized (in terms of length) the returned path will be.
The AvoidPath input consists of a start point and an end point and a set of constraining polygons.<ref name="displaymove" /> The output is a path from start point to end point that does not violate any constraints. The patent states that polygons can be assumed not to be self-intersecting. The patent further implies that a point cannot be inside two or more polygons. From that we conclude that any two polygons can be assumed not to intersect. The patent describes three optimization levels. We label these from 0 (no optimization) to 2 (maximum optimization). The optimization levels determine how optimized (in terms of length) the returned path will be.


The patent mentions three types of polygons. The first type is the <tt>barred access</tt> polygon that cannot be entered. The second type is the <tt>total access</tt> polygon that cannot be entered unless the start or end point is inside the polygon. The third type is the <tt>near-point access</tt> polygon. For a point <i>p</i> and a polygon <i>P</i> the <i>near point</i> is a point on the edges of <i>P</i> at minimal distance from <i>p</i>. A path may start in a near-point access polygon, but it must exit the polygon through the near-point. Similarly, a path may end in such a polygon, but it must enter the polygon through the near-point. The patent does not accurately describe the semantics of the different polygon types so we had to determine them in another way. We discuss this in Polygon types section.
The patent mentions three types of polygons. The first type is the <tt>barred access</tt> polygon that cannot be entered. The second type is the <tt>total access</tt> polygon that cannot be entered unless the start or end point is inside the polygon. The third type is the <tt>near-point access</tt> polygon. For a point <i>p</i> and a polygon <i>P</i> the <i>near point</i> is a point on the edges of <i>P</i> at minimal distance from <i>p</i>. A path may start in a near-point access polygon, but it must exit the polygon through the near-point. Similarly, a path may end in such a polygon, but it must enter the polygon through the near-point. The patent does not accurately describe the semantics of the different polygon types so we had to determine them in another way. We discuss this in Polygon types section.
236

edits