Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
how to cut polygon with line?

Subject: how to cut polygon with line?

From: Christoph Wasshuber

Date: 16 May, 2003 10:10:32

Message: 1 of 6

I have a polygone given by a vector
of vertices x and a vector of vertices y
(x, and y coordinates) and would like to
cut this polygon with a line segment
defined by (x1,y1) and (x2,y2).

Is there some built in function which supports
this? Or do I have to write one myself, taking
care of all possibilities of line does not cut
polygone, line overlays a polygon edge, ...

Chris....

Subject: how to cut polygon with line?

From: John D'Errico

Date: 16 May, 2003 13:21:43

Message: 2 of 6

In article <3EC4FF68.AFD5358C@ti.com>,
 Christoph Wasshuber <wasshub@ti.com> wrote:

> I have a polygone given by a vector
> of vertices x and a vector of vertices y
> (x, and y coordinates) and would like to
> cut this polygon with a line segment
> defined by (x1,y1) and (x2,y2).
>
> Is there some built in function which supports
> this? Or do I have to write one myself, taking
> care of all possibilities of line does not cut
> polygone, line overlays a polygon edge, ...
>
> Chris....

Nothing public that I know of. Watch out for
non-convex polygons too, because the line may
cross several sections of the polygon, leaving
you with multiple disjoint polygons.

I'd be tempted to triangulate the polygon.
Then it becomes a problem of cutting each of
a set of disjoint triangles.

John D'Errico

Subject: how to cut polygon with line?

From: Michael Garrity

Date: 16 May, 2003 14:05:14

Message: 3 of 6

Christoph Wasshuber wrote:
> I have a polygone given by a vector
> of vertices x and a vector of vertices y
> (x, and y coordinates) and would like to
> cut this polygon with a line segment
> defined by (x1,y1) and (x2,y2).
>
> Is there some built in function which supports
> this? Or do I have to write one myself, taking
> care of all possibilities of line does not cut
> polygone, line overlays a polygon edge, ...
>
> Chris....

 I'm sure someone has code for this lying around,
but it is really quite simple, and it is a beautiful
algorithm. It is worth exploring. It comes from a paper
by Ivan Sutherland and Gary Hodgman in 1974 (1).
It goes something like this:

function pout=polyclip(pin,x1,x2)
    plane=[x1(2)-x2(2),x2(1)-x1(1),0];
    plane(3)=x1(1)*plane(1)+x1(2)*plane(2);
    n=size(pin,1);
    s=pin(end,:);
    pout=[];
    for ci=1:n
        p=pin(ci,:);
        if (inside(p,plane))
            if (inside(s,plane)) % case 1
                pout=[pout; p];
            else % case 4
                t=clip(s,p,plane);
                pout=[pout; t; p];
            end
        else
            if (inside(s,plane)) % case 2
                t=clip(s,p,plane);
                pout=[pout;t];
            end
        end

        s=p;
    end

function in=inside(p,plane)
    d=p(1)*plane(1)+p(2)*plane(2);
    if (d > plane(3))
        in=1;
    else
        in=0;
    end

function c=clip(p1,p2,plane)
    d1=p1(1)*plane(1)+p1(2)*plane(2)-plane(3);
    d2=p2(1)*plane(1)+p2(2)*plane(2)-plane(3);
    t=(0-d1)/(d2-d1);
    c=p1 + t*(p2-p1);


 Let's try it:

n=25;
p=zeros(n,2);
for index=1:n
    ang=2*pi*index/(n+1);
    p(index,1) = (1+rand)*cos(ang);
    p(index,2) = (1+rand)*sin(ang);
end

c=polyclip(p,[-1 -1],[1 1]);
patch(p(:,1),p(:,2),zeros(size(p,1),1));
hold on;
patch(c(:,1),c(:,2),zeros(size(c,1),1));
hold off;

 So, how does it work? It handles each edge in turn
and looks at whether the current point and previous
point are inside. That gives us 4 cases. Those are:

 1) inside->inside
    We just add the new point to the output.

 2) inside->outside
    We figure out where the edge crossed the clip
    plane and add that to the output.

 3) outside->outside
    We add that crossing point and the current
    point to the output.

 4) outside->inside
    We don't do anything.

 This handles arbitrary polygons (without holes), and
it can be extended to clip against any convex polygon
(instead of a line) by looping over all of the edges. It
does have one strange quirk. If the clip would result in
two disjoint polygons, then this algorithm leaves a little
zero area segment connecting the two pieces. There
are other algorithms that don't have that quirk, but they
are a bit more complex, and they aren't nearly as
pretty.

    -MPG-


1) Reentrant Polygon Clipping
Sutherland, I. E. and Hodgman, G. W.
Communications of the ACM, 17(1)
January 1974, pp. 32-42

Subject: how to cut polygon with line?

From: Christoph Wasshuber

Date: 16 May, 2003 15:35:00

Message: 4 of 6

Michael,

thanks a lot. This is what I was looking
for. Very clever algorithm.

Your case 3 and 4, I guess, have to be
exchanged, the title or the explanation.

One other question. I have here on my
shelf an old "Collected Algorithms from ACM".
It is practically useless since there is no
index or table of contents. The algorithms
are numbered from 1 to 527 in 4 binders. Is
something like this available on CD so that
one could do a search? Or is there anything
like that in existence?

Chris....

Subject: how to cut polygon with line?

From: Michael Garrity

Date: 16 May, 2003 17:00:04

Message: 5 of 6

Christoph Wasshuber wrote:
> Michael,
>
> thanks a lot. This is what I was looking
> for. Very clever algorithm.
>
> Your case 3 and 4, I guess, have to be
> exchanged, the title or the explanation.
>

 Oops, you're right, I switched the explanations.
Sorry about that.

> One other question. I have here on my
> shelf an old "Collected Algorithms from ACM".
> It is practically useless since there is no
> index or table of contents. The algorithms
> are numbered from 1 to 527 in 4 binders. Is
> something like this available on CD so that
> one could do a search? Or is there anything
> like that in existence?
>

 It is probably in their online library. I don't
use that, so I'm not sure.

    -MPG-

Subject: how to cut polygon with line?

From: John D'Errico

Date: 16 May, 2003 19:50:27

Message: 6 of 6

In article <3EC54B74.8FE4BBA3@ti.com>,
 Christoph Wasshuber <wasshub@ti.com> wrote:

> Michael,
>
> thanks a lot. This is what I was looking
> for. Very clever algorithm.
>
> Your case 3 and 4, I guess, have to be
> exchanged, the title or the explanation.
>
> One other question. I have here on my
> shelf an old "Collected Algorithms from ACM".
> It is practically useless since there is no
> index or table of contents. The algorithms
> are numbered from 1 to 527 in 4 binders. Is
> something like this available on CD so that
> one could do a search? Or is there anything
> like that in existence?
>
> Chris....

I have the same 4 binders on a shelf.

A quick check shows you can find many of them
on netlib. It lets you do searches as you want,
then download the software. Much better than
the blue binders.

www.netlib.org

John

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us