This is a tough question, completely dependent on what “3 or more” means to you. If you have an object of 50 click, forget about it. 3? 4? That’s doable. the fewer the clicks, the easier this gets. And you must also realize that a 2d shape, using Vector2s, has areas, while a 3D shape, using Vector3s like you described, has a volume. I wont be going over volume of a random assortments of points because that just gets even more complex, so I’d highly recommend you just avoid that path in your project.
For 3 clicks on a 2D, this is going to be real easy, as all you have is a triangle no matter how the clicks are arranged. The area of a triangle is easily stated as A = hw/2, Easy! However it’s not quite that easy, as we don’t know for sure that there will be a convenient flat line to call our base. I’ve derived a longer formula that works for any orientation of a triangle, which replaces h with adjacent sidesin(Θ), where Θ is the angle between our base and the adjacent side. This angle can be computed with the inverse cos of (base/adjacent side). You want all of this to be computed given arbitrary Points in the form of Vector2s. We don’t know these, so they are simply going to be x1, y1, x2, so on. We can assume that our ‘base’ is between p1 and p2, so that the length of our base can be defined as b^2 = (x2-x1)^2 + (y2-y1)^2 (Pythagoreans theorem). The height value will be the same using either side, so we will just use p1 and p2. h is then calculated as a * sin(cos^-1(b/a)), where a is the length of our adjacent side defined as a^2 = (x3-x1)^2 + (y3-y1)^2. So, in total used our variables b and a, the final equation of A is given as b * a * sin(cos^-1(b/a)). Phew, and that was the easy one!
I’m going to walk you through 4 points, purely to show you how ridiculous this is going to get if you want any more than 4. But first, a quick explanation of why triangles are so easy: they are always convex. Once you introduce a 4th point, it becomes possible to create concave shapes, which in turns creates multiple possibilities of how to orientate the shape. For example, if you have 4 points in a square, you could connect them with 4 lines by drawing an hourglass. Making a shape convex out of those points would be easy, but what about… lets say 3 points in a triangle, and then 1 in the center? There are no convex ways to connect these 4 points, and now 3 possible orientations of points. This however can be negated, by either automatically canceling any point inside of the triangle of the first 3 points, or forcing lines to be drawn as points are placed, such that p1 -p2- p3 - p4 - p1, are linked in the order placed. One of these MUST be done. otherwise you’re getting nowhere. I don’t know your game, but the first pattern is much easier, so we’re going with that one. Now the given problem is easier, but it’s also a two stepper.
We’re going to assume 3 points have already been placed and we’ve used the above formula to calculate its area, and are about to place a new point somewhere on our plane. Calculating the new area is as easy as drawing a new triangle to the two closest points, and adding the area together, as any convex quadrilateral can be divided in to two triangles. We already have that equation, but the hard part is now to determine which two points we’re closest to… and to cancel out any points inside our triangle. First, lets tackle our “collision” detection, to make sure all new points are valid. This is a tough one because there’s not just two possible options, there’s 3. You can either place the point inside the triangle and be cancelled, place it outside within a golden region and create your ideal convex quadrilateral, or place it in a bad spot creating a concave quadrilateral. In the third case, our new point has to take over an older point, so that the existing point is removed, and we’re back to being a now slightly larger triangle. So, we will test every new point to see which region it is in. This is mostly a series of if statements based on the following image I made in paint for you: [88120-ツ.png|88120]
Anything in our green region will create a new convex quadrilateral, which is exactly what we want here. Anything in the red zone can just be ignored. Anything in the yellow zone however, would have to remove the point closest to it, and take that points role. If we know which region the point is in, the next step isn’t so bad, but finding the region gets a little tricky. We have 3 lines, these three lines can be represented by the connections between any two points, since triangles couldn’t possibly overlap. The only way I know how to do this is by checking to see whether each point is above or below a line. First we must check if any lines are vertical, because those can’t have any equation and must be caught as exceptions. those are easier however, as a vertical line would only need to check if the x value is greater or lower.
How to find the equation of a line: we could use the standard linear equation of y = mx + b, but instead we will be using linear interpolation, as it’s faster in this scenario. We can use linear interpolation to get a y value for an x value on some line that passes through any two points, and then compare this to this y value to Py. This equation would look something like… f(Px) = ((y2-y1)*(Px-x1)/(x2-x1)) + y1, where P1 and P2 were any two points on any of our three lines. Running this three times, would give us 3 y values, which we would check if it was lower or higher than our Py. In the end this would give us 3 bools, and using these bools would tell us which region our point is in, and from that we can continue to proceed to the next step.
To find out which section the new point is in is by far the hardest step here! I’ll skip a lot of the thought process behind it and skip to how we can do it. First, we can check if our new point is within the triangle, or outside of it. We can do this by several popular methods, but for this example we will be using the Barycentric Coordinate System, which is worth looking in to if you’re a diehard fan of geometry. Now that we know if it’s inside or outside of the triangle, lets assume our new point is now outside the triangle. This gives us 6 total regions to decide from, for which we will be using basic if logic to check for, because it’s late and I’m tired. First we’ll see if point 2 is above or below our line 0-1. From there, we can check if our new point is above or below the other two lines, each possible result giving different answers, and so on, as described in the code example below.
Now for what to do based on which section our new point landed in! If we are in the red zone, we simply disregard the new point. That is by far the easiest. If we are in yellow, you can check the distance of each point, and remove the point with the shortest distance, and add our new point to the list/array of points. If it’s in the green point, you’ll have to check (based on on our bools) exactly which region it’s in, and use the two points connecting to it to calculate the area of that triangle (using the above method) and add it to your previous triangle. This would give you your new Quadrilateral and it’s area.
Here’s all of that, in c#
List<Vector2> points = new List<Vector2> ();
float area;
bool AddPoint (Vector2 newPoint)
{
if (points.Count > 0)
{
foreach (Vector2 p in points)
if (p == newPoint)
return false;
}
if (points.Count>1)
{
//Check for in-line points, delete midpoint
float f = points[0].y+(points[1].y-points[0].y)*(newPoint.x-points[0].x)/(points[1].x-points[0].x);
if (newPoint.y==f)
return false;
}
switch (points.Count+1)
{
case 1:
points.Add (newPoint);
DrawPoint (newPoint);
return true;
case 2:
//rearange points for simplicity
if (points [0].x>newPoint.x)
{
Vector2 temp = points [0];
points [0] = newPoint;
points.Add (temp);
}
else if (points [0].x==newPoint.x)
points.Add (new Vector2(newPoint.x+1, newPoint.y)); //Now p0 is to the left of p1
DrawPoint (newPoint);
DrawLine (points[0], points[1]);
return true;
case 3:
//Check for in-line points, delete midpoint
if (newPoint.y==points [0].y+(points [1].y-points [0].y)*(newPoint.x-points [0].x)/(points [1].x-points [0].x))
{
if (newPoint.x<points [0].x)
{
DeleteLine (points [0], points [1]);
points [0] = newPoint;
DrawLine (points [0], points [1]);
}
else if (newPoint.x>points [1].x)
{
DeleteLine (points [0], points [1]);
points [1] = newPoint;
DrawLine (points [0], points [1]);
}
//else, point between lines, can be ignored
return false;
}
points.Add (newPoint);
DrawPoint (newPoint);
DrawLine (points [0], newPoint);
DrawLine (points [1], newPoint);
area = ComputeArea (points[0], points[1], newPoint);
return true;
case 4:
//we will be using these A LOT
float x0 = points [0].x;
float y0 = points [0].y;
float x1 = points [1].x;
float y1 = points [1].y;
float x2 = points [2].x;
float y2 = points [2].y;
float Px = newPoint.x;
float Py = newPoint.y;
//Test if point is inside triangle
float denom = ((y1-y2)*(x0-x2)+(x2-x1)*(y0-y2));
float a = ((y1-y2)*(Px-x2)+(x2-x1)*(Py-y2))/denom;
float b = ((y2-y0)*(Px-x2)+(x0-x2)*(Py-y2))/denom;
float c = 1-(a+b);
if (0<=a && a<=1 && 0<=b && b<=1 && 0<=c && c<=1)
return false; //Ignore this point, inside triangle
bool abv01 = false; //line 0-1
bool abv12 = false; //line 1-2
bool abv20 = false; //line 2-0
while (x0==x1 || x0==x2 || x0==Px || x1==x2 || x1==Px || x2==Px)
{
//Vertical line exists
if (x0==x1 || x0==x2 || x0==Px)
x0 += x0>500? -1 : 1; //Replace 500 with middle of screen value
else if (x1==x2 || x1==Px)
x1 += x1>500? -1 : 1;
else if (x2==Px)
x2 += x2>500? -1 : 1;
}
float f1 = y0+(y1-y0)*(Px-x0)/(x1-x0);
if (Py>f1)
abv01 = true;
float f2 = y1+(y2-y1)*(Px-x1)/(x2-x1);
if (newPoint.y>f2)
abv12 = true;
float f3 = y2+(y0-y2)*(Px-y2)/(x0-x2);
if (newPoint.y>f3)
abv20 = true;
float f4 = y0+(y1-y0)*(x2-x0)/(x1-x0);
Vector2 p1 = new Vector2(), p2 = new Vector2();
//All values callibrated to coordinates based in sample image, top left p0, top right p1, bottom p2.
//Values adjusted based on actual position of p3 relative to p0 and p1
if (y2>f4) //line 0-1 is on bottom, or "upside down"
{
abv01 = !abv01;
abv12 = !abv12;
abv20 = !abv20;
}
if (x2<x0) //If x2 is not between x0 and x1
abv20 = !abv20;
else if (x2>x1)
abv12 = !abv12;
if ((abv01 && abv12 && abv20) || (!abv01 && abv12 && !abv20) || (!abv01 && !abv12 && abv20))
{
points.Add (newPoint);
DrawPoint (newPoint);
if (abv12) DrawLine (newPoint, points [0]);
if (abv20) DrawLine (newPoint, points [1]);
if (!abv01) DrawLine (newPoint, points [2]);
if (!abv12) p1=points[1];p2=points[2];
if (!abv20) p1=points[2];p2=points[0];
if (abv01) p1=points[0];p2=points[1];
DeleteLine (p1, p2);
area += ComputeArea (newPoint, p1, p2);
}
else
{
//DoStuffForYellow
if (abv12)
{
DeleteLine (points[0], points[1]);
DeleteLine (points[0], points[2]);
points [0] = newPoint;
DrawLine (points[0], points[1]);
DrawLine (points[0], points[2]);
}
else if (abv20)
{
DeleteLine (points[1], points[0]);
DeleteLine (points[1], points[2]);
points [1] = newPoint;
DrawLine (points[1], points[0]);
DrawLine (points[1], points[2]);
}
else
{
DeleteLine (points[2], points[0]);
DeleteLine (points[2], points[1]);
points [2] = newPoint;
DrawLine (points[2], points[0]);
DrawLine (points[2], points[1]);
}
}
return true;
default:
Debug.Log ("Too many points!");
//Do nothing?
return false;
}
}
float ComputeArea (Vector2 p1, Vector2 p2, Vector2 p3)
{
float a = Mathf.Sqrt(Mathf.Pow(p3.x-p2.x, 2) + Mathf.Pow(p3.y-p2.y, 2));
float b = Mathf.Sqrt(Mathf.Pow(p3.x-p1.x, 2) + Mathf.Pow(p3.y-p1.y, 2));
return a * b * Mathf.Sin(Mathf.Acos(b/a))/2;
}
void DrawPoint(Vector2 p)
{
//DrawPoint
}
void DrawLine (Vector2 p1, Vector2 p2)
{
//DrawLine
}
void DeleteLine (Vector2 p1, Vector2 p2)
{
//DeleteLine
}
This was fun.
tl;dr: math
