Visual C++ - Check whether a point is Inside a Triangle or Not
Here is the Visual C++ program to check whether given point is inside or outside of a triangle.
Project a line to infinite or maximum distance from the given point. Calculate the number of unique intersection between this project line and each side of a triangle. If the number of intersections are in ODD number, then the point is inside the Triangle.
Source Code
#include <iostream>
#include <math.h>
int IsPointInBoundingBox(float x1, float y1, float x2, float y2, float px, float py)
{
float left, top, right, bottom; // Bounding Box For Line Segment
// For Bounding Box
if(x1 < x2)
{
left = x1;
right = x2;
}
else
{
left = x2;
right = x1;
}
if(y1 < y2)
{
top = y1;
bottom = y2;
}
else
{
top = y2;
bottom = y1;
}
if( (px+0.01) >= left && (px-0.01) <= right &&
(py+0.01) >= top && (py-0.01) <= bottom )
{
return 1;
}
else
return 0;
}
int LineSegmentIntersection(float l1x1, float l1y1, float l1x2, float l1y2,
float l2x1, float l2y1, float l2x2, float l2y2,
float *m1, float *c1, float *m2, float *c2,
float* intersection_X, float* intersection_Y)
{
float dx, dy;
dx = l1x2 - l1x1;
dy = l1y2 - l1y1;
*m1 = dy / dx;
// y = mx + c
// intercept c = y - mx
*c1 = l1y1 - *m1 * l1x1; // which is same as y2 - slope * x2
dx = l2x2 - l2x1;
dy = l2y2 - l2y1;
*m2 = dy / dx;
// y = mx + c
// intercept c = y - mx
*c2 = l2y1 - *m2 * l2x1; // which is same as y2 - slope * x2
if( (*m1 - *m2) == 0)
return 0;
else
{
*intersection_X = (*c2 - *c1) / (*m1 - *m2);
*intersection_Y = *m1 * *intersection_X + *c1;
}
if(IsPointInBoundingBox(l1x1, l1y1, l1x2, l1y2, *intersection_X, *intersection_Y) == 1 && IsPointInBoundingBox(l2x1, l2y1, l2x2, l2y2, *intersection_X, *intersection_Y) == 1)
{
return 1;
}
else
return 0;
}
int Calculate_Area_Perimeter_Triangle(float ax, float ay, float bx, float by, float cx, float cy, float *perimeter, float *area)
{
float A = sqrt((double)(bx-ax) * (bx-ax) + (by-ay) * (by-ay));
float B = sqrt((double)(bx-cx) * (bx-cx) + (by-cy) * (by-cy));
float C = sqrt((double)(ax-cx) * (ax-cx) + (ay-cy) * (ay-cy));
// Heron's formula for area calculation
// area = sqrt( s * (s-a) * (s-b) * (s-c))
float s = (A + B + C) / 2;
*perimeter = A + B + C;
*area = sqrt( s * (s-A) * (s-B) * (s-C));
// area = 1/2 * base * height
// if side A is base, then height
float height = (*area * 2) / A;
return 1;
}
int Calculate_Triangle_Type(float ax, float ay, float bx, float by, float cx, float cy, float *angleA, float *angleB, float *angleC)
{
float m1, c1, m2, c2;
float intersection_X, intersection_Y;
// Find the angle between Line AB and BC
LineSegmentIntersection(ax, ay, bx, by, bx, by, cx, cy,
&m1, &c1, &m2, &c2, &intersection_X, &intersection_Y);
*angleB = atan( (m1 - m2) / (1 + m1 * m2)) * 180 / 3.1417;
// Find the angle between Line BC and AC
LineSegmentIntersection(bx, by, cx, cy, cx, cy, ax, ay,
&m1, &c1, &m2, &c2, &intersection_X, &intersection_Y);
*angleC = atan( (m1 - m2) / (1 + m1 * m2)) * 180 / 3.1417;
// Find the angle between Line AC and AB
LineSegmentIntersection(cx, cy, ax, ay, ax, ay, bx, by,
&m1, &c1, &m2, &c2, &intersection_X, &intersection_Y);
*angleA = atan( (m1 - m2) / (1 + m1 * m2)) * 180 / 3.1417;
if(*angleA < 90 && *angleB < 90 && *angleC < 90)
return 1; // Acute Triangle
else if(*angleA > 90 || *angleB > 90 || *angleC > 90)
return 2; // obtuse Triangle
else
return 3; // Rightangle Triangle
}
void main()
{
float m1, c1, m2, c2;
float intersection_X, intersection_Y;
float ax, ay, bx, by, cx, cy;
float perimeter, area;
float angleA, angleB, angleC;
float x, y, px, py;
int nCountIntersections = 0;
std::cout << "Program to find the given point inside or outside the triangle:\n";
std::cout << "Enter Triangle Point A - X: ";
std::cin >> ax;
std::cout << "Enter Triangle Point A - Y: ";
std::cin >> ay;
std::cout << "Enter Triangle Point B - X: ";
std::cin >> bx;
std::cout << "Enter Triangle Point B - Y: ";
std::cin >> by;
std::cout << "Enter Triangle Point C - X: ";
std::cin >> cx;
std::cout << "Enter Triangle Point C - Y: ";
std::cin >> cy;
std::cout << "Enter Point - X: ";
std::cin >> x;
std::cout << "Enter Point - Y: ";
std::cin >> y;
px = x + 1000;
py = y;
nCountIntersections += LineSegmentIntersection(ax, ay, bx, by, x, y, px, py,
&m1, &c1, &m2, &c2, &intersection_X, &intersection_Y);
nCountIntersections += LineSegmentIntersection(ax, ay, cx, cy, x, y, px, py,
&m1, &c1, &m2, &c2, &intersection_X, &intersection_Y);
nCountIntersections += LineSegmentIntersection(cx, cy, bx, by, x, y, px, py,
&m1, &c1, &m2, &c2, &intersection_X, &intersection_Y);
if( (nCountIntersections % 2) == 1)
std::cout << "The Given Point is inside the triangle\n";
else
std::cout << "The Given Point is outside the triangle\n";
Calculate_Area_Perimeter_Triangle(ax, ay, bx, by, cx, cy, &perimeter, &area);
std::cout << "\nPerimeter: " << perimeter;
std::cout << "\nArea: " << area;
int type = Calculate_Triangle_Type(ax, ay, bx, by, cx, cy, &angleA, &angleB, &angleC);
float total = angleA + angleB + angleC;
if(type == 1)
std::cout << "\nAcute Triangle";
else if(type == 2)
std::cout << "\nObtuse Triangle";
else if(type == 3)
std::cout << "\nRight Triangle";
std::cout << "\n";
}
Output
Program to find the given point inside or outside the triangle:
Enter Triangle Point A - X: 10
Enter Triangle Point A - Y: 10
Enter Triangle Point B - X: 20
Enter Triangle Point B - Y: 10
Enter Triangle Point C - X: 15
Enter Triangle Point C - Y: 15
Enter Point - X: 12
Enter Point - Y: 12
The Given Point is outside the triangle
Perimeter: 24.1421
Area: 25
Acute Triangle
Press any key to continue . . .
Program to find the given point inside or outside the triangle:
Enter Triangle Point A - X: 10
Enter Triangle Point A - Y: 10
Enter Triangle Point B - X: 20
Enter Triangle Point B - Y: 10
Enter Triangle Point C - X: 15
Enter Triangle Point C - Y: 15
Enter Point - X: 15
Enter Point - Y: 11
The Given Point is inside the triangle
Perimeter: 24.1421
Area: 25.0000
Acute Triangle
Press any key to continue . . .
|
|