Wikipedia

Line clipping: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
No edit summary
m add links
 
(149 intermediate revisions by 97 users not shown)
Line 1:
{{Short description|In [[computer graphics]], '''line clipping''' is the process of removing lines or portionsremoval of lines outside of an area of interest. Typically, any line or part thereof which is outside of the viewingview area is removed./volume}}
[[Image:Line2_clipping.png|370x370px|right|Example of line clipping for a two-dimensional region]]
 
In [[computer graphics]], '''line clipping''' is the process of removing ([[Clipping (computer graphics)|clipping]]) lines or portions of lines outside an area of interest (a [[viewport]] or [[view volume]]). Typically, any part of a line which is outside of the viewing area is removed.
There are two common algorithms for line clipping: Cohen-Sutherland and Liang-Barsky.
 
There are two common algorithms for line clipping: [[Cohen–Sutherland]] and [[Liang–Barsky]].
== Cohen-Sutherland ==
 
A line-clipping method consists of various parts. Tests are conducted on a given line segment to find out whether it lies outside the view area or volume. Then, [[intersection]] calculations are carried out with one or more clipping boundaries.<ref>{{Cite web|url = http://www.cse.unt.edu/~renka/4230/LineClipping.pdf|title = Line Clipping|date = 2014-10-19|publisher = Department of Computer Science & Engineering, University of North Texas|last = Renka|first = R. J.|access-date = 2016-01-12}}</ref> Determining which portion of the line is inside or outside of the clipping volume is done by processing the endpoints of the line with regards to the intersection.
This algorithm divides a 2D space into 9 parts, of which only the middle part (viewport) is visible. The algorithm includes, excludes or partially includes the line based on where the two endpoints are:
 
==Cohen–Sutherland==
* Both endpoints are in the viewport (bitwise OR of endpoints == 0): trivial accept.
{{Main|Cohen–Sutherland algorithm}}
* Both endpoints are in the same part, which is not visible (bitwise AND of endpoints != 0): trivial reject.
In computer graphics, the Cohen–Sutherland algorithm (named after [[Danny Cohen (computer scientist)|Danny Cohen]] and [[Ivan Sutherland]]) is a line-clipping algorithm. The algorithm divides a 2D space into 9 regions, of which only the middle part (viewport) is visible.
* Both endpoints are in different parts: In case of this non trivial situation the algorithm finds one of the two points that are outside the viewport (there is at least one point outside). The intersection of the outpoint and extended viewport border is then calculated (i.e. with the parametric equation for the line) and this new point replaces the outpoint. The algorithm repeats until a trivial accept or reject occurs.
 
In 1967, flight-simulation work by Danny Cohen led to the development of the Cohen–Sutherland computer graphics two-dimensional and three-dimensional line clipping algorithms, created with Ivan Sutherland.
The numbers in the figure below are called [[outcodes]]. An outcode is computed for each of the two points in the line. The first bit is set to 1 if the point is above the viewport. The bits in the outcode represent: Top, Bottom, Right, Left. For example the outcode 1010 represents a point that is top-right of the viewport.
 
==Liang–Barsky==
1001 | 1000 | 1010
{{Main|Liang–Barsky algorithm}}
| |
The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen–Sutherland, but Cohen–Sutherland does trivial accepts and rejects much faster, so it should be considered instead if most of the lines you need to clip would be completely in or out of the [[clip window]].
-----------------------
| |
0001 | 0000 | 0010
| |
------------------------
| |
0101 | 0100 | 0110
 
==Cyrus–Beck==
{{Main|Cyrus–Beck algorithm}}
 
Very similar to Liang–Barsky line-clipping algorithm. The difference is that Liang–Barsky is a simplified Cyrus–Beck variation that was optimized for a rectangular clip window.
Here is the algorithm for Cohen-Sutherland
<pre><nowiki>
procedure CohenSutherlandLineClipAndDraw(
x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer);
{ Cohen-Sutherland clipping algorithm for line P0=(x1,y0) to P1=(x1,y1)
and clip rectangle with diagonal from (xmin,ymin) to (xmax,ymax).}
type
edge = (LEFT,RIGHT,BOTTOM,TOP);
outcode = set of edge;
var
accept,done : boolean;
outcode0,outcode1,outcodeOut : outcode;
{Outcodes for P0,P1, and whichever point lies outside the clip rectangle}
x,y : real;
procedure CompOutCode(x,y: real; var code:outcode);
{Compute outcode for the point (x,y) }
begin
code := [];
if y > ymax then code := [TOP]
else if y < ymin then code := [BOTTOM];
if x > xmax then code := code +[RIGHT]
else if x < xmin then code := code +[LEFT]
end;
 
The Cyrus–Beck algorithm is primarily intended for clipping a line in the parametric form against a convex polygon in 2 dimensions or against a convex polyhedron in 3 dimensions.<ref>Cyrus, M., Beck, J.: [https://www.sciencedirect.com/science/article/pii/0097849378900213 Generalized Two and Three Dimensional Clipping], Computers & Graphics, Vol. 3, No. 1, pp. 23–28, 1978.</ref>
begin
accept := false; done := false;
CompOutCode (x0,y0,outcode0); CompOutCode (x1,y1,outcode1);
repeat
if(outcode0=[]) and (outcode1=[]) then {Trivial accept and exit}
begin accept := true; done:=true end
else if (outcode0*outcode1) <> [] then
done := true {Logical intersection is true, so trivial reject and exi
t.}
else
{Failed both tests, so calculate the line segment to clip;
from an outside point to an intersection with clip edge.}
begin
{At least one endpoint is outside the clip rectangle; pick it.}
if outcode0 <> [] then
outcodeOut := outcode0 else outcodeOut := outcode1;
{Now find intersection point;
use formulas y=y0+slope*(x-x0),x=x0+(1/slope)*(y-y0).}
if TOP in outcodeOut then
begin {Divide line at top of clip rectangle}
x := x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y := ymax
end
if BOTTOM in outcodeOut then
begin {Divide line at bottom of clip rectangle}
x := x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y := ymin
end
else if RIGHT in outcodeOut then
begin {Divide line at right edge of clip rectangle}
y := y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
x := xmax
end
else if LEFT in outcodeOut then
begin {Divide line at left edge of clip rectangle}
y := y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x := xmin
end;
{Now we move outside point to intersection point to clip,
and get ready for next pass.}
if (outcodeOut = outcode0) then
begin
x0 := x; y0 := y; CompOutCode(x0,y0,outcode0)
end
else
begin
x1 := x; y1 := y; CompOutCode(x1,y1,outcode1);
end
end {subdivide}
until done;
if accept then MidpointLineReal(x0,y0,x1,y1,value) {Version for real coordin
ates}
end; {CohenSutherlandLineClipAndDraw}
</nowiki></pre>
 
==Nicholl–Lee–Nicholl==
C# implementation for Cohen-Sutherland algorithm
{{Main|Nicholl–Lee–Nicholl algorithm}}
<pre><nowiki>
internal sealed class CohenSutherlandClipping : IClippingAlgorithm
{
private Vector2 _clipMin, _clipMax;
 
The Nicholl–Lee–Nicholl algorithm is a fast line-clipping algorithm that reduces the chances of clipping a single line segment multiple times, as may happen in the Cohen–Sutherland algorithm. The clipping window is divided into a number of different areas, depending on the position of the initial point of the line to be clipped.
public IEnumerable<Vector2> GetBoundingPolygon()
{
yield return _clipMin;
yield return new Vector2(_clipMax.X, _clipMin.Y);
yield return _clipMax;
yield return new Vector2(_clipMin.X, _clipMax.Y);
}
 
==Fast clipping==
public void SetBoundingRectangle(Vector2 start, Vector2 end)
This algorithm has similarities with Cohen–Sutherland. The start and end positions are classified by which portion of the 9-area grid they occupy. A large switch statement jumps to a specialized handler for that case. In contrast, Cohen–Sutherland may have to iterate several times to handle the same case.<ref>{{cite journal|last1=Sobkow | first1 = Mark S. | last2 = Pospisil | first2 = Paul | last3 = Yang | first3 = Yee-Hong | title = A Fast Two-Dimensional Line Clipping Algorithm via Line Encoding | url = https://www.sciencedirect.com/science/article/pii/0097849387900616 | journal = Computers & Graphics | volume = 11 | number = 4 | pages = 459–467 | year = 1987}}</ref>
{
_clipMin = start;
_clipMax = end;
}
 
== ''O''(lg ''N'') algorithm ==
public void SetBoundingPolygon(IEnumerable<Vector2> points)
This algorithm classifies vertices against the given line in the implicit form ''p'': ''ax'' + ''by'' + ''c'' = 0. As the polygon is assumed to be convex and vertices are ordered clockwise or anti-clockwise, binary search can be applied and leads to a ''O''(lg ''N'') run-time complexity.<ref>[[Václav Skala|Skala, V.]]: ''O''(lg ''N'') Line Clipping Algorithm in E2, Computers & Graphics, Pergamon Press, Vol. 18, No. 4, 1994.</ref>
{
throw new NotSupportedException("see Capabilities =)");
}
 
==Skala==
private int getPointCode(Vector2 point)
This algorithm is based on [[homogeneous coordinates]] and [[Duality (projective geometry)|duality]].<ref>Skala, V.: [https://www.researchgate.net/profile/Vaclav_Skala/publication/220067375_A_new_approach_to_line_and_line_segment_clipping_in_homogeneous_coordinates/links/02bfe50f2654923b6f000000/A-new-approach-to-line-and-line-segment-clipping-in-homogeneous-coordinates.pdf A new approach to line and line segment clipping in homogeneous coordinates], The Visual Computer, ISSN 0178-2789, Vol. 21, No. 11, pp. 905–914, Springer Verlag, 2005.</ref> It can be used for line or line-segment clipping against a rectangular window, as well as against a convex polygon. The algorithm is based on classifying a vertex of the clipping window against a half-space given by a line ''p'': ''ax'' + ''by'' + ''c'' = 0. The result of the classification determines the edges intersected by the line ''p''. The algorithm is simple, easy to implement and extensible to a convex window as well. The line or line segment '''p''' can be computed from points '''r'''<sub>1</sub>, '''r'''<sub>2</sub> given in homogeneous coordinates directly using the cross product as
{
:'''p''' = '''r'''<sub>1</sub> × '''r'''<sub>2</sub> = (''x''<sub>1</sub>, ''y''<sub>1</sub>, ''w''<sub>1</sub>) × (''x''<sub>2</sub>, ''y''<sub>2</sub>, ''w''<sub>2</sub>)
int result = 0;
or as
 
:'''p''' = '''r'''<sub>1</sub> × '''r'''<sub>2</sub> = (''x''<sub>1</sub>, ''y''<sub>1</sub>, 1) × (''x''<sub>2</sub>, ''y''<sub>2</sub>, 1).
if (point.X < _clipMin.X) ++result;
else if (point.X > _clipMax.X) result |= 2;
 
if (point.Y > _clipMax.Y) result |= 4;
else if (point.Y < _clipMin.Y) result |= 8;
 
return result;
}
 
public bool ClipLine(ref Line line)
{
Vector2 P = line.End - line.Start;
int startCode = getPointCode(line.Start);
int endCode = getPointCode(line.End);
float dxdy = 0, dydx = 0;
 
if (P.X != 0) dydx = P.Y / P.X;
if (P.Y != 0) dxdy = P.X / P.Y;
 
for (int stage = 0; stage < 4; stage++)
{
if ((startCode | endCode) == 0) return true;
else if ((startCode & endCode) != 0) return false;
 
if (startCode == 0)
{
int buf1 = startCode; startCode = endCode; endCode = buf1;
Vector2 buf2 = line.Start; line.Start = line.End; line.End = buf2;
}
 
if ((startCode & 1) == 1)
{
line.Start.Y += dydx * (_clipMin.X - line.Start.X);
line.Start.X = _clipMin.X;
}
else if ((startCode & 2) == 2)
{
line.Start.Y = line.Start.Y + dydx * (_clipMax.X - line.Start.X);
line.Start.X = _clipMax.X;
}
else if ((startCode & 4) == 4)
{
line.Start.X = line.Start.X + dxdy * (_clipMax.Y - line.Start.Y);
line.Start.Y = _clipMax.Y;
}
else if ((startCode & 8) == 8)
{
line.Start.X = line.Start.X + dxdy * (_clipMin.Y - line.Start.Y);
line.Start.Y = _clipMin.Y;
}
 
startCode = getPointCode(line.Start);
}
 
return true;
}
 
public ClippingCapabilities Capablities { get { return ClippingCapabilities.RectangleWindow; } }
 
public override string ToString()
{
return "Cohen-Sutherland algorithm";
}
}
</nowiki></pre>
 
== Liang-Barsky ==
 
The Liang-Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping box to determine the intersections between the line and the clipping box. With these intersections it knows which portion of the line should be drawn. This algorithm is significantly more efficient than Cohen-Sutherland.
 
C# implementation for Liang-Barsky algorithm
<pre><nowiki>
internal sealed class LiangBarskyClipping : IClippingAlgorithm
{
private Vector2 _clipMin, _clipMax;
 
public IEnumerable<Vector2> GetBoundingPolygon()
{
yield return _clipMin;
yield return new Vector2(_clipMax.X, _clipMin.Y);
yield return _clipMax;
yield return new Vector2(_clipMin.X, _clipMax.Y);
}
 
public void SetBoundingRectangle(Vector2 start, Vector2 end)
{
_clipMin = start;
_clipMax = end;
}
 
public void SetBoundingPolygon(IEnumerable<Vector2> points)
{
throw new NotSupportedException("see Capabilities =)");
}
 
private delegate bool ClippingHandler(float p, float q);
 
public bool ClipLine(ref Line line)
{
Vector2 P = line.End - line.Start;
 
float tMinimum = 0, tMaximum = 1;
 
ClippingHandler pqClip = delegate(float directedProjection, float directedDistance)
{
if (directedProjection == 0)
{
if (directedDistance < 0) return false;
}
else
{
float amount = directedDistance / directedProjection;
if (directedProjection < 0)
{
if (amount > tMaximum) return false;
else if (amount > tMinimum) tMinimum = amount;
}
else
{
if (amount < tMinimum) return false;
else if (amount < tMaximum) tMaximum = amount;
}
}
return true;
};
 
if (pqClip(-P.X, line.Start.X - _clipMin.X))
{
if (pqClip(P.X, _clipMax.X - line.Start.X))
{
if (pqClip(-P.Y, line.Start.Y - _clipMin.Y))
{
if (pqClip(P.Y, _clipMax.Y - line.Start.Y))
{
if (tMaximum < 1)
{
line.End.X = line.Start.X + tMaximum * P.X;
line.End.Y = line.Start.Y + tMaximum * P.Y;
}
if (tMinimum > 0)
{
line.Start.X += tMinimum * P.X;
line.Start.Y += tMinimum * P.Y;
}
return true;
}
}
}
}
return false;
}
 
public ClippingCapabilities Capablities { get { return ClippingCapabilities.RectangleWindow; } }
 
public override string ToString()
{
return "Liang-Barsky algorithm";
}
}
</nowiki></pre>
 
== Fast-Clipping ==
C# implementation for Fast-Clipping algorithm
<pre><nowiki>
internal sealed class FastClipping : IClippingAlgorithm
{
private Vector2 _clipMin, _clipMax;
 
public IEnumerable<Vector2> GetBoundingPolygon()
{
yield return _clipMin;
yield return new Vector2(_clipMax.X, _clipMin.Y);
yield return _clipMax;
yield return new Vector2(_clipMin.X, _clipMax.Y);
}
 
public void SetBoundingRectangle(Vector2 start, Vector2 end)
{
_clipMin = start;
_clipMax = end;
}
 
public void SetBoundingPolygon(IEnumerable<Vector2> points)
{
throw new NotSupportedException("see Capabilities =)");
}
 
#region отсечения концов отрезка
 
private void clipStartTop(ref Line line)
{
line.Start.X += line.Dx * (_clipMin.Y - line.Start.Y) / line.Dy;
line.Start.Y = _clipMin.Y;
}
 
private void clipStartBottom(ref Line line)
{
line.Start.X += line.Dx * (_clipMax.Y - line.Start.Y) / line.Dy;
line.Start.Y = _clipMax.Y;
}
 
private void clipStartRight(ref Line line)
{
line.Start.Y += line.Dy * (_clipMax.X - line.Start.X) / line.Dx;
line.Start.X = _clipMax.X;
}
 
private void clipStartLeft(ref Line line)
{
line.Start.Y += line.Dy * (_clipMin.X - line.Start.X) / line.Dx;
line.Start.X = _clipMin.X;
}
 
private void clipEndTop(ref Line line)
{
line.End.X += line.Dx * (_clipMin.Y - line.End.Y) / line.Dy;
line.End.Y = _clipMin.Y;
}
 
private void clipEndBottom(ref Line line)
{
line.End.X += line.Dx * (_clipMax.Y - line.End.Y) / line.Dy;
line.End.Y = _clipMax.Y;
}
 
private void clipEndRight(ref Line line)
{
line.End.Y += line.Dy * (_clipMax.X - line.End.X) / line.Dx;
line.End.X = _clipMax.X;
}
 
private void clipEndLeft(ref Line line)
{
line.End.Y += line.Dy * (_clipMin.X - line.End.X) / line.Dx;
line.End.X = _clipMin.X;
}
 
#endregion
 
public bool ClipLine(ref Line line)
{
int lineCode = 0;
 
if (line.End.Y < _clipMin.Y) lineCode |= 8;
else if (line.End.Y > _clipMax.Y) lineCode |= 4;
 
if (line.End.X > _clipMax.X) lineCode |= 2;
else if (line.End.X < _clipMin.X) lineCode |= 1;
 
if (line.Start.Y < _clipMin.Y) lineCode |= 128;
else if (line.Start.Y > _clipMax.Y) lineCode |= 64;
 
if (line.Start.X > _clipMax.X) lineCode |= 32;
else if (line.Start.X < _clipMin.X) lineCode |= 16;
 
// 9 - 8 - A
// | | |
// 1 - 0 - 2
// | | |
// 5 - 4 - 6
switch (lineCode)
{
// Из центра
case 0x00: return true;
 
case 0x01: clipEndLeft(ref line); return true;
 
case 0x02: clipEndRight(ref line); return true;
 
case 0x04: clipEndBottom(ref line); return true;
 
case 0x05:
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
 
case 0x06:
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
 
case 0x08: clipEndTop(ref line); return true;
 
case 0x09:
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
 
case 0x0A:
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
 
// Слева
case 0x10: clipStartLeft(ref line); return true;
 
case 0x12: clipStartLeft(ref line); clipEndRight(ref line); return true;
 
case 0x14:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
return true;
 
case 0x16:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
if (line.End.X > _clipMax.X) clipEndRight(ref line);
return true;
 
case 0x18:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
return true;
 
case 0x1A:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
if (line.End.X > _clipMax.X) clipEndRight(ref line);
return true;
 
// Справа
case 0x20: clipStartRight(ref line); return true;
 
case 0x21: clipStartRight(ref line); clipEndLeft(ref line); return true;
 
case 0x24:
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
return true;
 
case 0x25:
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndBottom(ref line);
if (line.End.X < _clipMin.X) clipEndLeft(ref line);
return true;
 
case 0x28:
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
return true;
 
case 0x29:
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndTop(ref line);
if (line.End.X < _clipMin.X) clipEndLeft(ref line);
return true;
 
// Снизу
case 0x40: clipStartBottom(ref line); return true;
 
case 0x41:
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
 
case 0x42:
clipStartBottom(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
return true;
 
case 0x48:
clipStartBottom(ref line);
clipEndTop(ref line);
return true;
 
case 0x49:
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
 
case 0x4A:
clipStartBottom(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
 
// Снизу слева
case 0x50:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
 
case 0x52:
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) return false;
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) clipStartLeft(ref line);
return true;
 
case 0x58:
clipEndTop(ref line);
if (line.End.X < _clipMin.X) return false;
clipStartBottom(ref line);
if (line.Start.X < _clipMin.X) clipStartLeft(ref line);
return true;
 
case 0x5A:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) return false;
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) return false;
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
return true;
 
// Снизу-справа
case 0x60:
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
 
case 0x61:
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) return false;
clipStartBottom(ref line);
if (line.Start.X > _clipMax.X) clipStartRight(ref line);
return true;
 
case 0x68:
clipEndTop(ref line);
if (line.End.X > _clipMax.X) return false;
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
 
case 0x69:
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) return false;
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) return false;
if (line.End.Y < _clipMin.Y) clipEndTop(ref line);
if (line.Start.Y > _clipMax.Y) clipStartBottom(ref line);
return true;
 
// Сверху
case 0x80: clipStartTop(ref line); return true;
 
case 0x81:
clipStartTop(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
return true;
 
case 0x82:
clipStartTop(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
return true;
 
case 0x84:
clipStartTop(ref line);
clipEndBottom(ref line);
return true;
 
case 0x85:
clipStartTop(ref line);
if (line.Start.X < _clipMin.X) return false;
clipEndLeft(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
 
case 0x86:
clipStartTop(ref line);
if (line.Start.X > _clipMax.X) return false;
clipEndRight(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
 
// Сверху-слева
case 0x90:
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
 
case 0x92:
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) return false;
clipStartTop(ref line);
if (line.Start.X < _clipMin.X) clipStartLeft(ref line);
return true;
 
case 0x94:
clipEndBottom(ref line);
if (line.End.X < _clipMin.X) return false;
clipStartLeft(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
 
case 0x96:
clipStartLeft(ref line);
if (line.Start.Y > _clipMax.Y) return false;
clipEndRight(ref line);
if (line.End.Y < _clipMin.Y) return false;
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
return true;
 
// Сверху-справа
case 0xA0:
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
 
case 0xA1:
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) return false;
clipStartTop(ref line);
if (line.Start.X > _clipMax.X) clipStartRight(ref line);
return true;
 
case 0xA4:
clipEndBottom(ref line);
if (line.End.X > _clipMax.X) return false;
clipStartRight(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
 
case 0xA5:
clipEndLeft(ref line);
if (line.End.Y < _clipMin.Y) return false;
clipStartRight(ref line);
if (line.Start.Y > _clipMax.Y) return false;
if (line.End.Y > _clipMax.Y) clipEndBottom(ref line);
if (line.Start.Y < _clipMin.Y) clipStartTop(ref line);
return true;
}
 
return false;
}
 
public ClippingCapabilities Capablities { get { return ClippingCapabilities.RectangleWindow; } }
 
public override string ToString()
{
return "Fast-Clipping algorithm";
}
}
</nowiki></pre>
 
==See also==
* [[Clipping (computer graphics)]]
 
==References==
{{compu-graphics-stub}}
{{Reflist}}
 
{{DEFAULTSORT:Line Clipping}}
[[Category:Computer graphics]]
[[Category:Clipping (computer graphics)]]
Retrieved from "https://en.wikipedia.org/wiki/Line_clipping"