Plotting inequalities algorithm

Question

I'm writing a simple graphing application using HTML5 canvas. The input is a system of inequalities like this (all functions are linear):

4x + y >= 4
x  + y <= 4
x,y >= 0

The output I desire is a set of points that form the shape to fill. For example, for this example the graph would be:

And the set of points: [0,4], [1,0], [4,0]. What is the algorithm to find these points? I know that the intersection point of lines is the solution of the linear system, but I can't figure out how to do the filling right. Please note, this question is not about the implementation of graphing system, but how to find the filled shape points.

Answer 1

It looks to me that your problem is really 2 problems: do the equations define a closed polygon, and how to fill it?

For instance,
* if your equations included x + y > 10, and x + y < 5, there is no way you'll find a solution to that, there is nothing to fill, * if your equations were simply x > 0, y > 0, you would have a problem because the surface to paint would be unbounded / infinite.

Whether there is a solution to your system of equations is I believe roughly equivalent of the simplex algorithm in Linear Programming: Phase I of the algorithm determines if the problem is feasible at all.

Whether that solution forms a closed polygon is not something typically of interest for Linear Programming. However, you could approach that by checking whether the 4 problems: Minimize x, Maximize x, Minimize y, Maximize y, given your inequations, have a solution. If any of these problems doesn't, then you know the problem is unbounded - which I think implies the polygon isn't closed.

Once you know the polygon is closed, I would simply compute the intersection points of all the lines, potentially reduce it to its convex hull, and then fill the resulting polygon.

Answer 2

You can exploit the fact that any region defined as the union of linear half-spaces must be a single convex region, though possibly semi-infinite, which potentially adds messiness.

1. Begin by adding a rectangular "window" of inequalities that's a superset of the domain you're graphing. This way you can ignore cases where the result is a semi-infinite space.

2. Find the intersection points between all pairs of the boundaries. This is two nested loops and an intersection checker. (If desired, you can first find all intersection of the non-window inequalities, set the window to include all these, then add window-related intersections.)

3. Throw out all points that fail to satisfy any inequality.

4. If there are any points left, use a convex hull algorithm to find the enclosed region and draw it.

Note that if the graphing window is known in advance, you can make intersection calculation much more efficient by considering only the segments of boundaries lying inside the window and using an arrangement algorithm like enhanced Bentley-Ottman.