Open Mobile Map

Line Clipping

It is desirable to restrict the effect of graphics primitives to a subregion of the canvas, to protect other portions of the canvas.

All primitives are clipped to the boundaries of this clipping rectangle; that is, primitives lying outside the clip rectangle are not drawn.

The default clipping rectangle is the full canvas (the Window), and it is obvious that we cannot see any graphics primitives outside the screen.

So, if we clip lines outside the window we may have the result as Fig (b) below:

Before we discuss clipping lines, let’s look at the simpler problem of clipping individual points.

If the x coordinate boundaries of the clipping rectangle are Xmin and Xmax, and the y coordinate boundaries are Ymin and Ymax, then the following inequalities must be satisfied for a point at (X,Y) to be inside the clipping rectangle:

Xmin < X < Xmax and Ymin < Y < Ymax

If any of the four inequalities does not hold, the point is outside the clipping rectangle. From now we will study actual clipping algorithms.

Cohen-Sutherland Clipping

To clip a line, we need to consider only its endpoints, not its infinitely many interior points.

If both endpoints of a line lie inside the clip rectangle, the entire line lies inside the clip rectangle and can be trivially accepted.

If one endpoint lies inside and one outside, the line intersects the clip rectangle and we must compute the intersection point.

If both endpoints are outside the clip rectangle, the line may or may not intersect with the clip rectangle, and we need to perform further calculations to determine whether there are any intersections.

To do this, Cohen-Sutherland Clipping Algorithm first encode the line endpoints. Encoding is done by four criteria. So, four bit is need to each endpoint.

1)Is the point Above the window? (Top)

2)Is the point Under the window? (Bottom)

3)Is the point on the Left side of the window? (Left)

4)Is the point on the Right side of the window? (Right)

1 for True, 0 for False.

After encoding, we may accept if the line is fully inside the window, or discard if the line is fully outside the window.

Four Clipping Cases

There can be four cases.

First, see the line AB. Both endpoints can be encoded as 0000. So, it means that the line is fully inside the window, So Accept all.

Second, see the line EF (0010 , 1010) Result of logical and operation is not 0000 (0010), and it means the it is fully outside the window, so discard.

Third, see the line CD(0000, 1010). This is the case of one endpoint inside the window and the other is not. In this case the line may be shorten.

Forth, see the line GH and IJ (0001, 1000). We can not make a decision only with outcodes. Because it may be fully outside the window like line GH, and it may have some intersections like line IJ. So in this case, the line may be discarded or shorten.

Overall Steps for Cohen-Sutherland Clipping Algorithm

This is the overall algorithm of Cohen-Sutherland Clipping Algorithm.

If the line enters and if the line is fully inside the window –> Accept & End.

If the line fully outside the window –> Reject & End.

If the line intersecting on a point –> Compute an intersected point and split the line on that point.

Change the outcode & loop again.

Detail Steps for Cohen-Sutherland Clipping Algorithm

End-points pairs are check for trivial acceptance or trivial rejected using the outcode.

If not trivial-accepance or trivial-rejected, divided into two segments at a clip edge.

Iteratively clipped by testing trivial-acceptance or trivial-rejected, and divided into two segments until completely inside or trivial-rejected.

Trivial acceptance/reject test

To perform trivial accept and reject tests, we extend the edges of the clip rectangle to divide the plane of the clip rectangle into nine regions. Each region is assigned a 4-bit code deteermined by where the region lies with respect to the outside halfplanes of the clip-rectangle edges. Each bit in the outcode is set to either 1 (true) or 0 (false); the 4 bits in the code correspond to the following conditions:

* Bit 1 : outside halfplane of top edge, above top edge

Y > Ymax

* Bit 2 : outside halfplane of bottom edge, below bottom edge

Y < Ymin

* Bit 3 : outside halfplane of right edge, to the right of right edge

X > Xmax

* Bit 4 : outside halfplane of left edge, to the left of left edge

X < Xmin

Conclusion

In summary, the Cohen-Sutherland algorithm is efficient when outcode testing can be done cheaply (for example, by doing bitwise operations in assembly language) and trivial acceptance or rejection is applicable to the majority of line segments .(For example, large windows - everything is inside , or small windows - everything is outside).

Pseudo-code of Cohen-Sutherland Algorithm.

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;

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 exit.*/

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 := ymax

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 coordinates*/

end; /*CohenSutherlandLineClipAndDraw*/

This note describes the technique and gives the solution to finding the shortest distance from a point to a line or line segment. The equation of a line defined through two points P1 (x1,y1) and P2 (x2,y2) is

P = P1 + u (P2 - P1)

The point P3 (x3,y3) is closest to the line at the tangent to the line which passes through P3, that is, the dot product of the tangent and line is 0, thus

(P3 - P) dot (P2 - P1) = 0Substituting the equation of the line gives

[P3 - P1 - u(P2 - P1)] dot (P2 - P1) = 0Solving this gives the value of u

Substituting this into the equation of the line gives the point of intersection (x,y) of the tangent as

x = x1 + u (x2 - x1)
y = y1 + u (y2 - y1)

The distance therefore between the point P3 and the line is the distance between (x,y) above and P3.

Notes

• The only special testing for a software implementation is to ensure that P1 and P2 are not coincident (denominator in the equation for u is 0)
• If the distance of the point to a line segment is required then it is only necessary to test that u lies between 0 and 1.
• The solution is similar in higher dimensions.

Sample java source code

/*
* DistancePointSegmentExample, calculate distance to line
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program.  If not, see <www.gnu.org/licenses/>.
*
* Example implementation of “Minimum Distance between a Point and a Line”
import java.awt.geom.Point2D;

public class DistancePointSegmentExample {

/**
* Wrapper function to accept the same arguments as the other examples
*
* @param x3
* @param y3
* @param x1
* @param y1
* @param x2
* @param y2
* @return
*/
public static double distanceToSegment(double x3, double y3, double x1, double y1, double x2, double y2) {
final Point2D p3 = new Point2D.Double(x3, y3);
final Point2D p1 = new Point2D.Double(x1, y1);
final Point2D p2 = new Point2D.Double(x2, y2);
return distanceToSegment(p1, p2, p3);
}

/**
* Returns the distance of p3 to the segment defined by p1,p2;
*
* @param p1
*                First point of the segment
* @param p2
*                Second point of the segment
* @param p3
*                Point to which we want to know the distance of the segment
*                defined by p1,p2
* @return The distance of p3 to the segment defined by p1,p2
*/
public static double distanceToSegment(Point2D p1, Point2D p2, Point2D p3) {

final double xDelta = p2.getX() - p1.getX();
final double yDelta = p2.getY() - p1.getY();

if ((xDelta == 0) && (yDelta == 0)) {
throw new IllegalArgumentException(”p1 and p2 cannot be the same point”);
}

final double u = ((p3.getX() - p1.getX()) * xDelta + (p3.getY() - p1.getY()) * yDelta) / (xDelta * xDelta + yDelta * yDelta);

final Point2D closestPoint;
if (u < 0) {
closestPoint = p1;
} else if (u > 1) {
closestPoint = p2;
} else {
closestPoint = new Point2D.Double(p1.getX() + u * xDelta, p1.getY() + u * yDelta);
}

return closestPoint.distance(p3);
}

/**
* @param args
*/
public static void main(String[] args) {
// Test example
System.out.println(String.format(”Distance from 5,5 to (10,10)-(20,20): %f”, distanceToSegment(5, 5, 10, 10, 20, 20)));
System.out.println(String.format(”Distance from 15,15 to (10,10)-(20,20): %f”, distanceToSegment(15, 15, 10, 10, 20, 20)));
System.out.println(String.format(”Distance from 15,15 to (20,10)-(20,20): %f”, distanceToSegment(15, 15, 20, 10, 20, 20)));
System.out.println(String.format(”Distance from 0,15 to (20,10)-(20,20): %f”, distanceToSegment(0, 15, 20, 10, 20, 20)));
System.out.println(String.format(”Distance from 0,25 to (20,10)-(20,20): %f”, distanceToSegment(0, 25, 20, 10, 20, 20)));
System.out.println(String.format(”Distance from -13,-25 to (-50,10)-(20,20): %f”, distanceToSegment(-13, -25, -50, 10, 20, 20)));

// Should give:
// Distance from 5,5 to (10,10)-(20,20): 7.071068
// Distance from 15,15 to (10,10)-(20,20): 0.000000
// Distance from 15,15 to (20,10)-(20,20): 5.000000
// Distance from 0,15 to (20,10)-(20,20): 20.000000
// Distance from 0,25 to (20,10)-(20,20): 20.615528
// Distance from -13,-25 to (-50,10)-(20,20): 39.880822
}

}