I have to form a Convex Hull from large amount of points and I came across this article. Whole process of pruning is described and well explained, except for one part.
I don't know what this part means and how to convert it to code:
Since the space is two-dimensional, each point has two coordinates, x > and y. Every time we read a new point, we compute the following 4 > points:
A = (Ax, Ay) which maximizes x-y B = (Bx, Xy) which maximizes x+y C = (Cx, Cy) which minimizes x-y D = (Dx, Dy) which minimizes x+y
Can anyone help me to calculate points A,B,C,D?
You're not so much calculating the points, you're selecting them from your input data:
A is the point in your input data where the value of x-y is larger than any other input data point.B is the point in your input data where the value of x+y is larger than any other input data point.C is the point in your input data where the value of x-y is smaller than any other input data point.D is the point in your input data where the value of x+y is smaller than any other input data point.