Vietnamese GPS :: Intelligent on the go

This article presents a new 2D polygon clipping method, based on an extension to the Sutherland-Cohen 2D line clipping method. After discussing three basic polygon clipping algorithms, a different approach is proposed, explaining the principles of a new algorithm and presenting it step by step.

Patrick-Gilles Maillot

Sun microsystems, inc.
Desktop and Graphics Development Organization
2550 Garcia avenue, MS 21-04
Mountain View, CA 94043

ABSTRACT

An example implementation of the algorithm is given along with some results. A comparison between the proposed method, the Liang and Barsky algorithm, and the Sutherland-Hodgman algorithm is also given, showing performances up to eight times the speed of the Sutherland-Hodgman algorithm, and up to three times the Liang and Barsky algorithm. The algorithm proposed here can use floating point or integer operations; this can be useful for fast or simple implementations.

1. Introduction.

The computer graphics field has recently experienced a large increase of systems using raster display devices. These systems can display polygons or fill areas without flicker due to a display list regeneration.

It is a goal for the display generators to present these polygons, as fast as possible. One of the different graphics operations to be performed before a polygon is rendered is to clip it against a rectangular region, aligned with the axes. There are basically three well known algorithms used for the clipping of polygons.

The first one is known as the Sutherland-Hodgman [3] algorithm. In this approach, each polygon edge or vertex is clipped successively against all the clipping region edges. The algorithm recursively calls itself at each edge.

The second method has been developed by Weiler and Atherton [1] and is a more general method that can be used to compute the intersections between two polygons. Although the algorithm is powerful, it is not well adapted to the 2D case, with a rectangular clipping region, because of its complexity.

Finally, the Liang and Barsky [2] algorithm provides a polygon clipping method based on the parametric equation of the polygon edges. One edge can give four scalar parameters. By establishing a classification based on the contribution of each parameter, this algorithm produces the needed turning points. This method is said by the authors to be twice as fast as the Sutherland-Hodgman algorithm but has the drawback of requiring floating point computations.

Other approaches can be found [4], where the polygon is clipped as a polyline and only the Y intersections are used to generate the different turning points. This particular approach reduces the amount of floating point computations compared to the amount needed in the Liang and Barsky method. A last method, comparable to the Weiler-Atherton algorithm has been described by Kilgour [7].

This paper proposes a completely different approach, in which a very well known line clipping method is used for the basic intersection computations. This approach has the benefit of being the fastest for most applications. The Sutherland-Cohen line clipping algorithm [6] has been chosen because it is probably the most efficient method for trivial acceptance and rejection cases, which are both the most frequently encountered situations in visualization. This algorithm can be implemented using either integer or floating point arithmetic, thus covering a wider set of applications. It is also easy to optimize in the case of polylines, versus a single vector at a time, which corresponds well to the case of a polygon boundary. A more recent technique [5] can also be used for the 2-D line clipping algorithm involved in this method, but this approach, optimized for single, isolated vectors, is not adequate in the case of several linked vectors.

2. Principles of the proposed algorithm.

The basic idea of the proposed method is to reuse the information that has been generated by the trivial accept and reject test of a line clipping algorithm. This idea is similar to Kilgour's proposal [7], but the algorithm presented here does not assume any specific orientation for the clipping region or the polygon, does not require any sorting operation, and can be part of a pipeline implementation. Polygons with multiple boundaries are clipped one boundary at a time, so the proposed method concentrates on the case of a single boundary. The fact that a fast algorithm for trivial rejection cases is used has oriented the method to principally test for polygon clipping situations when a segment of the polygon boundaries is completely rejected. Compared with a basic line clipping algorithm, all the vertices of the polygon will have to pass an extra test. We will refer to this extra test as the "basic turning point test". It will be shown that in most cases, the extra computational cost is as low as a single bit test. The objective is then to generate the needed turning points only when the segment has been partially or totally rejected by the line clipping algorithm. Because the trivial rejection test is satisfied quickly in the Sutherland-Cohen method, the time not spent in actually clipping the segment can be used to evaluate the existence of one or more turning points. The cost of the proposed algorithm is minimal (1 bit test) when the segments of the polygon boundaries are trivially accepted.

The Cohen-Sutherland algorithm used as the line clipper in this article requires a specific coding of the different areas of the clipping region. An example of coding is given Figure 1. It is important to note that the region code values presented here should not be modified. Modifying these values also require to change the contents of the two look up tables used for the turning point computation (proposed later in this article with the example implementation).

2.1. Algorithm concepts.

As mentioned in the introduction, a standard line clipping algorithm is used. It has to compute region codes for each end point of the polygon' segments. In the case where all the segments of the polygon are inside or partially inside the clipping region, a line clipping algorithm followed by a simple test (the basic turning point test) to check if the end point of a segment lies in a corner outside the clipping area (regions noted 0011, 0110, 1100, 1001 in Figure 1), is enough to guarantee a correct polygon clipping. The more complex cases appear when the segments of the polygon are rejected by the line clipping algorithm. The proposed algorithm is the following:

Calculate the code of the first point of the polygon.

for all subsequent points (called "current point"):

Calculate the code of the current point.

Clip the segment according to the two codes.

if the segment is outside the clipping region:

Test for complex cases.

endif

Test for the basic turning point test.

Set "first point" = "current point".

endfor

The different cases encountered in this algorithm are detailed below, followed by an example of implementation.

2.2. Study of the different situations.

The first requirement of the proposed method, affects the codes returned when testing the end points of a segment of the polygon boundary. The algorithm proposed here requires an extra bit. It is necessary to provide the returned code with a flag specifying whether the original code has one or two bits that are set. For example, the original code 0001 has only one bit set, and the "actual" code (the code containing the extra bit needed) will be 00001. The code 0110 has two bits set; in this case, the "actual" code will be 10110. In the following discussions, we will ignore this extra bit, knowing that it is part of the returned code. The distinction in the regions where a segment (an edge of the polygon) starts or ends, gives different situation cases that are explained later in this paper.

A segment starting in a region with an original code of either 0001, 0010, 0100, or 1000, will be called a "1-x" segment. A segment ending in the same regions will be called a "x-1" segment. If a segment starts in a region with an original code of either 0011, 0110, 1100, or 1001, it will be called a "2-x" segment. If a segment ends in a region with an original code having two bits, it will be called a "x-2" segment.

2.2.1. The basic turning point test.

The "basic turning point test" checks if the end point of a segment lies in a corner outside the clipping area and adds the respective turning point to the clipped polygon points, depending on the result of the test. This guarantees a correctly clipped polygon when all the segments of the polygon are at least partially inside the clipping region, and some end points of the segments are in regions where the code, calculated by the Sutherland-Cohen algorithm has two bits; i.e. for four of the nine regions of the clipping region.

In an ideal case, each edge of the polygon should not be considered independent from the previous or the next one. As shown in Figure 2, if the i th edge ViVi+1 produces a turning point, then the (i+1)th edge, Vi+1Vi+2 should not produce the same turning point again. Thus, edges should be considered linked together and the basic turning point test will be applied to the end point of the edge. Because we used a hardware renderer, making it more important to limit the number of tests performed by the software algorithm than the number of points generated, the implementation example proposed in section 3 allows the generation of consecutive, coincident turning points.

2.2.2. The more complex cases.

Figure 3 shows the different generic configurations for a segment in respect to the clipping region. All the cases can be derived from those presented by symmetry or rotation. The proposed method does not have to handle the cases where the segment is partially or totally visible. In these cases, the basic turning point test suffices to generate the needed information for polygon clipping, as mentioned in the previous paragraph.

2.2.2.1. The 1-1 bit cases.

The 1-1 bit cases (lines a and b of Figure 3) is the class of configurations where the edge is outside the clipping region and both end points are in a 1-bit code region. There are two cases:

The two points have the same code, in which case no turning point has to be generated (line a).

The two points have different codes. In this case, only one turning point needs to be generated. This turning point is the clipping region corner that corresponds to the OR operation between the codes, and results in a 2-bit code that can be handled by the basic turning point test (line b).

2.2.2.2. The 2-1 and 1-2 bit cases.

The 2-1 and 1-2 bit cases (lines c and d of Figure 3) is the class of configurations where the edge is outside the clipping region and one point has a 1-bit code while the other has a 2-bit code.

If the end point of the edge is in a 1-bit region, and the result of the logical AND of the two codes is not 0, there is no need to generate a turning point, as shown in Figure 4-a, segment PÆR. If the result of the logical AND is 0, then a turning point, depending on both the 2-bit code of the end point, and the 1-bit code of the starting point, must be generated. Such a situation is shown in Figure 4-a, segment PÆQ. This case is handled by a look up table in the proposed implementation presented later in this paper.

If the end point has a 2-bit code, and if the logical AND of the two codes is not 0, this case is handled by the basic turning point test (segment RÆQ, Figure 4-b). If, on the other hand, the logical AND of the two codes is 0, two turning points must be generated. The first one depends on the values of the region codes of both points, and the second turning point will be generated by the basic turning point test, as shown in Figure 4-b, segment PÆQ.

2.2.2.3. Generating the look up table.

It is mentioned in the previous paragraph, that a look up table (Tcc in the implementation, section 3) is used in the 2-1 and 1-2 bit cases. The contents of the look up table depends on the codes used for the clipping of the segment. The implementation presented later uses the region code layout given in Figure 1. For example, let us consider the segment PÆQ, from Figure 4-b:

P has a code of 0001, and Q has a code of 0110. The basic turning point test will be applied using Q to generate the left-most turning point. The look up table is used to determine the right-most turning point. The goal is to compute a 2-bit code from the values of the codes of P and Q, that will correspond to a valid turning point. To do so, we use the following formula:

new_code = code[Q] + table[code[P]]

In the example taken here, new_code will be equal to 3. The algorithm proposed in section 3 will use the value of new_code to determine which corner of the clipping region should be added to the clipped polygon.

For a different layout of the codes, the contents of the look up table can be computed by taking successively the different possible situations of P and Q so that P has one bit set, and Q has two bits set and the segment PÆQ is completely outside the clipping region. The code for the nearest turning point from P is known, and the contents of the look up table can be computed for the element code[P]. Only 8 entries of the look up table are used. Four of them correspond to the formula given above. The other four entries correspond to the indices where region codes have two bits set. These entries are set to 1 and are used by the algorithm in section 3, in the case of a 1-1 bit segment. The 8 other entries of the look up table are set to 0.

2.2.2.4. The 2-2 bit cases.

The 2-2 bit cases (lines e, f and g of Figure 3) is the class of edges where both points are in a 2-bit region.These three situations are solved with three different cases:

If the two points have the same code. No turning point has to be generated (line e).

If the result of the logical AND of the two codes is not 0, the basic turning point test is applied to the ending point of the edge (line f).

If the result of the logical AND of the two codes is 0 (line g, Figure 3), two turning points must be generated. One is trivially generated by the basic turning point test, but the other one requires some extra computation. In this case, there can be two possible candidates, as shown in Figure 5. The proposed implementation uses a midpoint subdivision of the edge until the computed point appears in a non ambiguous region, covered by the other cases. There is a finite number of loops performed in that case, depending on the maximum precision used. When using 32-bit integers, there will be less than 32 loops performed. In the implementation proposed in section 3, the loop actually exits as soon as the mid-point has a code different from the code of the two end points, which corresponds to the gray zone in Figure 5.

3. Example of implementation.

An example implementation of the proposed algorithm is given below in the C language. Not included in this implementation is the Sutherland-Cohen algorithm. The Sutherland-Cohen code is composed of two functions:

Cp_start_clip() performs a simple coding of the first point of the polygon. This function returns SEGM if the point is inside the clipping region, NOSEGM if the point is outside.

Cp_end_clip() performs the clipping of a line coded in the two structures Cp_start and Cp_end which respectively represent the start and end point of one polygon edge. Cp_end_clip provides the following information:

- The returned status, NOSEGM, SEGM, SEGM | CLIP, which represents the visibility characteristic of the edge.

- M_start and M_end, which are the computed codes of the start and end point of the edge, respectively.

- Cp_start and Cp_end contain the clipped line coordinates at the end of the algorithm.

3.1. Structures used.

The C structures used in the clipping algorithm are:

typedef struct {

float x; /* x coordinate */

float y; /* y coordinate */

} Upoint; /* User point */

typedef struct {

Upoint Point; /* The point's coordinates */

int Code; /* The code computed for this point */

} Ppoint; /* Internal representation */

#define MAXTEST 1

#define NOSEGM 0 /* The line is rejected */

#define SEGM 1 /* The line is visible (even partially) */

#define CLIP 2 /* The line has been "clipped" */

#define TWOBITS 0x100 /* A flag to indicate a 2bit code. */

Ppoint Cp_start; /* The start point of the line */

int M_code;

Ppoint Cp_end; /* The end point of the line */

int D_code;

Ppoint C_exchange;

/* These are two look_up tables */

/* used in finding the turning point */

/* in the case 1-2. They should be */

/* modified with the regions' codes. */

int Tcc[16] = {0,-3,-6,1,3,0,1,0,6,1,0,0,1,0,0,0};

int Cra[16] = {-1,-1,-1,2,-1,-1,3,-1,-1,1,-1,-1,0,-1,-1,-1};

/* Tcc is used to compute a correct */

/* offset, while Cra gives an index in */

/* the Clip_region array, for the turning */

/* coordinates. */

Upoint Clip_region[4]; /* Clipping region coordinates in lower-left, lower-right,

* upper-left and upper-right order

*/

The function CP_space_code() returns the code associated with a given point. The returned code can be a single value, or a "OR" between a single value and a flag that indicates a 2bit code.

CP_space_code(point_to_code)

Upoint *point_to_code;

{

if (point_to_code->x < Clip_region[0].x) {

if (point_to_code->y > Clip_region[3].y) return (6 | TWOBITS);

if (point_to_code->y < Clip_region[0].y) return (12 | TWOBITS);

return (4);

}

if (point_to_code->x > Clip_region[3].x) {

if (point_to_code->y > Clip_region[3].y) return (3 | TWOBITS);

if (point_to_code->y < Clip_region[0].y) return (9 | TWOBITS);

return (1);

}

if (point_to_code->y > Clip_region[3].y) return (2);

if (point_to_code->y < Clip_region[0].y) return (8);

return (0);

}

The CP_2D_polygon_clip() function accepts an array of vertices as input and clips the polygon edges against a rectangular clip region. Turning points are generated when necessary to keep the polygon structure and ensure a correct visualization. The function generates the resulting polygons in an output array of points. "nin" represents the number of elements of "in", the points of the incoming polygon. "nout" and "out" generated by the clipping algorithm, represent respectively the number of points and the array of points of the clipped polygon.

CP_2D_polygon_clip(nin,in,nout,out)

int nin;

Upoint *in;

int *nout;

Upoint *out;

{

register int i, j, k;

register Ppoint *pt_Cp_start = &Cp_start;

register Ppoint *pt_Cp_end = &Cp_end;

/*

* Temporary data used in the case of a 2-2 bit.

*/

Upoint Cp_t_start;

Upoint Cp_t_end;

Upoint Cp_A_point;

int A_code;

/*

* Be sure to close the polygon.

*/

k = nin + 1;

in[nin] = in[0];

*nout = 0;

/*

* Compute the first point' status.

* If visible, then store the first point in the output array.

*/

if (Cp_start_clip(in)) {

out[*nout] = pt_Cp_start->Point;

*nout += 1;

}

/*

* Next polygon's points... We build a vector from the "start"

* point to the "end" point.

* Clip the line with a standard 2D line clipping method.

*/

for (i = 1; i < k; i++) {

j = Cp_end_clip(&in[i]);

/*

* If the line is visible, then store the computed point(s), and

* jump to the basic turning point test.

*/

Cp_start.Code = D_code;

if(j & SEGM) {

if (j & CLIP) {

out[*nout] = pt_Cp_start->Point;

*nout += 1;

}

out[*nout] = pt_Cp_end->Point;

*nout += 1;

} else {

/*

* Here the line has been rejected... Apply the polygon clipping.

* Begin with a 2bit end point.

*/

if (D_code & TWOBITS) {

if (!(M_code & D_code)) {

/*

* If the start point is also a 2bit... Need some more information to

* make a decision! So do mid-point subdivision.

*/

if (M_code & TWOBITS) {

j = 1;

Cp_t_start = pt_Cp_start->Point;

Cp_t_end = pt_Cp_end->Point;

while (j) {

Cp_A_point.x = (Cp_t_start.x + Cp_t_end.x) / 2.;

Cp_A_point.y = (Cp_t_start.y + Cp_t_end.y) / 2.;

A_code = CP_space_code(&Cp_A_point);

if (A_code & TWOBITS) {

if (A_code == D_code) {

Cp_t_end = Cp_A_point;

} else {

if (A_code == M_code) {

Cp_t_start = Cp_A_point;

} else {

j = 0;

}

}

} else {

if (A_code & D_code) {

A_code = M_code + Tcc[A_code & ~TWOBITS];

} else {

A_code = D_code + Tcc[A_code & ~TWOBITS];

}

j = 0;

}

}

} else {

/*

* This is for a 1 bit start point (2bit end point).

*/

A_code = D_code + Tcc[M_code];

}

out[*nout] = Clip_region[Cra[A_code & ~TWOBITS]];

*nout += 1;

}

} else {

/*

* Here we have a 1bit end point.

*/

if (M_code & TWOBITS) {

if (!(M_code & D_code)) D_code = M_code + Tcc[D_code];

} else {

D_code |= M_code;

if (Tcc[D_code] == 1) D_code |= TWOBITS;

}

}

}

/*

* The basic turning point test...

*/

if (D_code & TWOBITS) {

out[*nout] = Clip_region[Cra[D_code & ~TWOBITS]];

*nout += 1;

}

/*

* Copy the current point as the next starting point.

*/

pt_Cp_start->Point = *(in + i);

}

if (*nout) {

out[*nout] = out[0];

*nout += 1;

}

}

4. Performance.

This algorithm has been programmed on two different Sun workstations, using floating point and integer arithmetic. As a matter of comparison, the Liang and Barsky algorithm and the Sutherland-Hodgman algorithm have also been programmed in C. The Liang and Barsky algorithm had to be modified so it handles correctly the horizontal and vertical segments outside of the clipping region. Because there is absolutely no assumption on the number of vertices and on the complexity (number of boundaries, self-intersections,...) of the polygon to clip, the Sutherland-Hodgman algorithm uses dynamic memory allocation to keep the overall size of the program acceptable. If the number of vertices is limited to a given value, it is fairly easy to avoid dynamic memory allocations, and this reduces the time spent in the memory operations involved in this method. All the algorithms were compiled with the same level of optimizations and produce the same graphical results.

A study of the Sun 4-260 execution profile of the algorithms using the Unix "prof" command shows that almost 22% of the Sutherland-Hodgman algorithm is used in memory copy operations, and 8.5% in memory management. Removing dynamic memory allocation actually improves the algorithm by a factor 1.5, which is not sufficient to set it at a comparable level of performance with the proposed method. This study also shows that the CPU time spent in the CP_2D_polygon_clip function of the proposed method, not including the Cp_end_clip call, is 13.1% of the total clipping time, in both integer and float arithmetic.

The tables below give the results on two different workstations for 100000 successive calls to the polygon clipping algorithm. Different polygons were used, as shown in Figure 6. Figure 6-a is the test pattern proposed in the Liang and Barsky paper. The examples chosen here are representative of the most common situations encountered in graphics. The author believes that maximum performance possible should be achieved for the trivial acceptance or trivial rejection cases. Other cases, such as partial clipping, or even more the 2-2bit case, should give correct results when clipping occurs, but are generally not critical to the overall performance of a graphics application. Because a Sutherland-Cohen method is used for the line clipping section of our implementation, trivially rejected polygons are guaranteed to give better results that trivially accepted ones (Figure 6-d).

5. Degenerate edges.

Both Sutherland-Hodgman and Liang-Barsky algorithms produce "degenerate" edges in some cases (Figure 6-a). The proposed method does not avoid this; it even produces some degenerate edges in other cases (Figure 7), but because a code specifying if the point is an included, a turning, or a clipped point against a particular clip plane, is available at each vertex, it is quite simple to remove those extra degenerate edges by scanning, in the output array of points, the sequence of codes provided by the clipping algorithm. This is generally not necessary except if the scan conversion algorithm used to render the clipped polygon does not handle degenerate edges.

Any list of coincident consecutive turning points should be reduced to one turning point.

Then any turning point surrounded by two points having the same code should be removed.

This minimizes the number of degenerate edges, but does not remove all of them when a concave polygon, such as Figure 6-a, is split into two or more polygons. In the latter case, the Weiler-Atherton algorithm gives the best results.

6. Conclusion.

A new 2D polygon clipping algorithm has been presented and analyzed. It has three advantages: the speed (the algorithm is faster than any of the methods currently used), the possibility to use existing software as well as the fact that the algorithm can run using only integer arithmetic, and also the ease with which the number of degenerate edges can be reduced.

Special care has been taken for each of the different cases showing that it is possible to reduce the time passed in trivial acceptance and rejection of polygons. The fact that a "standard" line clipping algorithm is used gives the implementation programer the liberty to adapt his own code for the line clipping step, with the only constraint of providing the regions codes and the status used in the proposed 2D polygon clipping implementation.

7. Acknowledgments.

This work has been conducted at Sun Microsystems, for the XGL project. I want to thank my colleagues, Walt Donovan, Rab Hagy, Steve Johnson, Dave Linder, Jim Shuder, Jim Uyei, and Kevin Wu for many months of dedicated and creative work. Many thanks to the referees for their insightful suggestions. I also wish to thank Sun Microsystems in assisting me in applying for a patent on this algorithm.

References.

[1]. K. Weiler and P. Atherton, ``Hidden Surface Removal Using Polygon Area Sorting,'' Computer Graphics, vol. 11, pp. 214-222, 1977.

[2]. Y. Liang and B. Barsky, "An Analysis and Algorithm for Polygon Clipping,'' CACM, vol. 26, pp. 868-877, 1983.

[3]. I. E. Sutherland and G. W. Hodgman, "Reentrant Polygon Clipping,'' CACM, vol. 17, pp. 32-42, 1974.

[4]. Patrick-Gilles Maillot, Contribution à l'étude des systèmes graphiques, architectures logicielle et matérielle, Université Claude Bernard, Lyon I, Lyon, France, 2 juillet 1986. Ph.D Thesis

[5]. Tina M. Nicholl, D. T. Lee, and Robin A. Nicholl, "An Efficient New Algorithm For 2-D Line Clipping: Its Development And Analysis,'' ACM Computer Graphics, Siggraph `87 proceedings, vol. 21, Number 4, pp. 253-262, ACM, July 1987.

[6]. W. M. Newman, R. F. Sproull, Principles of Interactive Computer Graphics, McGraw-Hill Book Company, 1979.

[7]. A. Kilgour, "Unifying Vector and Polygon Algorithms for Scan Conversion and Clipping," Eurographics'87 proceedings, pp. 363-375, August 1987.

www.digitalmobilemap.com's comment:

When we develop VGPS, we did not use any polygon clipping algorithm listed here: Sutherland-Hodgman, Weiler and Atherton, Liang and Barsky and Patrick-Gilles Maillot.

Why we did not use any algorithm above? Because they are developed for computer which has fast CPU and plenty of memory. If you apply any of clipping algorithm above for mobile phone, it will kill your phone which has very slow CPU and only 500KB memmory!

So we invented our own clipping algorithm for mobile phone. Our algorithm can clip 50,126 streets and 11,112 points of interest in less than 300 miliseconds! It may be the fastest clipping algorithm in the world.

For your information:

1 second = 1,000 miliseconds
1 millisecond (1 ms): cycle time for frequency 1 kHz
1 millisecond: duration of light for typical photo flash strobe
1 millisecond: repetition interval of GPS C/A PN code
1.000692286 milliseconds: time taken for light to travel 300 km in a vacuum
2 milliseconds: half life of hassium-265
2.27 milliseconds: cycle time for the A above middle C in music (440 Hz); if a tuning device for musical instruments generates just one tone, it is probably this tone
3 milliseconds: a housefly’s wing flap
3.4 milliseconds: half life of meitnerium-266
5 milliseconds: a honeybee’s wing flap
8 milliseconds: camera shutter speed at setting 125
9 milliseconds: typical maximum seek time for a 7200rpm hard disk
10 milliseconds (10 ms): cycle time for frequency 100 Hz (also known as a "jiffy")
16.7 milliseconds: cycle time for American 60 Hz AC mains grid
20 milliseconds: cycle time for European 50 Hz AC mains grid
33.3 milliseconds: the amount of time one frame lasts in 30fps video
50 milliseconds: cycle time for the lowest audible tone, 20 Hz
60 milliseconds: cycle time for European 16.7 Hz AC electrified railroad power grid
30 to 100 milliseconds: typical minimum latency for a broadband internet connection (important for online gaming)
100 to 150 milliseconds: typical time for a human blink
150 to 300 miliseconds: typical time for VGPS to clip 50,126 streets and 11,112 points of interest. Time measurements are taken on Acer laptop (CPU: Intel Celeron 2.6MHz, Memmory: 256MB)

Search your city map:

A New, Fast Method For 2D Polygon Clipping