Can anyone suggest me the method to clip a polygon of n vertices against a rectangular boundary... Thx in advance "A byte is a large bit to crunch!"

Haha! I actually had to think up an algorithm for doing that, and wrote an article about it (for my own reference while implementing it).

Unedited, unreviewed: Polygon Clipping Algorithm (Word document)

Comments are appricieated, if it relates to what you want.

Hey thank u... but actually what I wanted to know was that if we had a polygon like this




/\ V1
/ \
/ \
/ \
V1 / \ V2
\ /
\ /
\ /
\ /
\/ V3


and we had to clip it against a rectangle in such a way that this polygon is at the left bottom corner of the rectangle


-----------------
| b |
| /\ |
|/ \ |
a / \ |
/| \ c |
/ -------\---------
\ d /
\ /
\ /
\ /
\/

Thru the polygon clipping algorithm we can obtain the points a, b and c...
but how do we obtain point d?

-----------------
| b |
| /\ |
|/ \ |
a / \ |
| \ c |
d -------\---------




"A byte is a large bit to crunch!"

Usually, points such as D are generated by clipping the shape to each edge individually, one after another. Search for the Sutherland-Hodgman algorithm for a good starting point.

Btw, use [ source ] and [ /source ] tags for ascii graphics.

Sorry abt the previous reply... it got a little messed up... this is what I wanted to convey...

actually what I wanted to know was that if we had a polygon like this




........................./\.V1
......................../**\
......................./****\
....................../******\
..................V1./********\.V21
.....................\********/
......................\******/
.......................\****/
........................\**/
.........................\/ V3


and we had to clip it against a rectangle in such a way that this polygon is at the left bottom corner of the rectangle


.....................-----------------
.....................|^b^^^^^^^^^^^^^|
.....................|^/\^^^^^^^^^^^^|
.....................|/**\^^^^^^^^^^^|
...................a./****\^^^^^^^^^^|
..................../|**** \^c^^^^^^^|
.................../*-------\---------
...................\*d******/
....................\******/
.....................\****/
......................\**/
.......................\/

Thru the polygon clipping algorithm we can obtain the points a, b and c...
but how do we obtain point d?

..................-----------------
..................|^b^^^^^^^^^^^^^|
..................|^/\^^^^^^^^^^^^|
..................|/**\^^^^^^^^^^^|
................a./****\^^^^^^^^^^|
..................|*****\^c^^^^^^^|
..................-------\---------
..................d







"A byte is a large bit to crunch!"

Thanx a lot

The funda is quite clear now.

"A byte is a large bit to crunch!"

That is exactly what my algorithm does. It should have featured a few illustrations.

The purpose of that algorithm is to transform any polygon so that all its vertices are within a given rectangle, without changing any (visible) angles within that rectangle.

Even though my description of it may be fuzzy, it does work and the basic idea is very simple. I''ll be ready to explain if you have questions about it.

I wrote down a step-by-step illustration of how my algorithm works.


The current point is (1). It is outside the 1st clip region, so we split it:

Because (1a)''s next point (4) is inside the 1st clip region, we move the point. It is traced on the line towards point (4):

Point (1a) is now inside all clip regions, therefor we''re done with it.Next up is point (1b). Its next point (2) is also inside the 1st clip, so we trace it on that line:

All well. Point (2) is inside the 1st, 2nd and 3rd clip region, but outside the 4th. We split it:

Point (2a)''s next point is inside the 4th clip region, so we trace it, as well as with point (2b):

On to point (3). It is outside the 2nd clip region, so it gets split:

Point (3a)''s next point is (2b) which is inside the current clip region, so it is traced:

The same is true for point (3b). Note here that this clip region does not respect the X-value at all:

Hmm... point (3b) is still outside the clip rectangle, namely the 3rd clip region. We split it:

...and, point (3ba) is traced towards (3a):

Now, interesting stuff occurs. Point (3bb)''s next point is point (4), which is also outside the 3rd clip region. When this happens, we disconnects/removes the point:

Onto point (4) which is outside the 3rd clip region. Lets split it:

What happens now, is a bit special and kind of optimazation. Accordning to the rules (4a) should be moved to same position as point (3ba), but when the next point''s x-position is equal with the clip regions x-position we behave as it had been outside it. In that case we remove it:

Finally, the last step is to trace (4b) towards (1a).

And we''re done!

Now I''m off to look at hockey!

quote:Original post by C0D1F1ED
CWizard, your illustrations are -very- nice. How did you create them? I once wanted to write a tutorial but I stopped because I didn''t know how to create such nice looking images.

I did it the hard way, although Photoshop gave a little help.

If it''s of any interst, you can download the .psd file: gd-pca-ill1.psd.zip