Combined polygons for a curve and a line

Question

I have a curve and a straight line along the ordinate, I need to obtain closed polygons of points on the left and right with respect to the straight line, formed due to the intersections of the straight line with the curve.

I will illustrate:

In the figure there is a curve and a straight line, closed polygons are formed on the left and right with respect to the straight line, I need to get them different lists.

Illustration for a common understanding of the task. Colors are made for the sake of clarity, that it is necessary to obtain two lists of polygons for the left and right cases, respectively.

Can you implement this with gdi?

Answer 1

The first thing to get right are the data structures.

Assuming you are collecting the mouse locations in a

List<Point> allPoints = new List<Point>();

we then will need to partition those points into list of right and left polygons, i.e. two lists of list of points..:

List<List<Point>> leftList = new List<List<Point>>();
List<List<Point>> rightList = new List<List<Point>>();

Next we need to do the partitioning. In a general solution we would need a function(point, line), which determines in which hemisphere the point lies.

Let's write the full signature int OnSideOff(Point p, Point p1, Point p2) and then cheat:

int OnSideOff(Point p, Point p1, Point p2)
{
    // simplistic test, for vertical lines only
    if (p.X < p1.X) return -1;
    else if (p.X > p1.X) return 1;
    else return 0;
}

This will obviously only work for vertical lines; you can find posts for the general case if you try..

Before we can follow through with the partitioning we will need another helper function:

We can't expect that all or even any point actually lies on the line. Therefore we need to start and end each polygon with a point on the line, ideally the crossing between the last and current point and the line.

You will find post for line intersection code but I will, surprise: cheat again...:

Point Crossing(Point p, Point p0, Point p1, Point p2)
{
    // simplistic again
    return  new Point(p1.X, (p.Y + p0.Y) / 2 );
}

Now we're all set up to do the partitioning:

List<Point> curLeft = new List<Point>();
List<Point> curRight = new List<Point>();

bool left = OnSideOff(allPoints[0], P1, P2) > 0;

for (int i = 1; i < allPoints.Count; i++)   // *
{
    Point p = allPoints[i];
    Point cross = Crossing(p, allPoints[i-1], P1, P2);
    if ( OnSideOff(p, P1, P2) >= 0)  // right
    {
        if (left)  // was left
        {
            curLeft.Add(cross);
            leftList.Add(curLeft.ToList());  //**
            left = false;
            curLeft.Clear();
            curRight.Add(cross);
        }
        curRight.Add(p);
    }
    else  // left
    {
        if (!left)  // was right
        {
            curRight.Add(cross);
            rightList.Add(curRight.ToList());  //**
            left = true;
            curRight.Clear();
            curLeft.Add(cross);
        }
        curLeft.Add(p);
    }
}

The code uses these variables:

Size sz = pictureBox1.ClientSize;
Point P1 = new Point(sz.Width / 2, 0);
Point P2 = new Point(sz.Width / 2, sz.Height);

Notes:

//* I throw away the 1st point because I am lazy; there are of course ways to do it right; all I wanted was a cheap way to call the crossing method ;-)

//** we need to keep the points, so we copy them with the ToList method!

Here is is at work: