-2

I am working on an assignment in which we are given a (my_x,my_y) coordinate and we have to tell whether this coordinate lies in the free space or inside an obstacle.

enter image description here

enter image description here

As you can see, from the picture, I have to tell whether a certain point lies among any of the obstacle.

Checking for out of boundary is easy and simple. Similarly I check for circle as (pseudo code):

if sqrt((my_x-5)^2+(my_y-3.5)^2) <= 0.5

this means it is inside circle.

if ((my_x >= 3.5 || my_x <= 6.5) && ((my_y >= 5 || my_y <= 6)

this means it is inside rectangle.

However I am stuck for the triangle case. The main reason is that my_x and my_y are of decimal type and can take any value suppose up to 2 decimal figures. Now one was is to have several if conditions and then check each.

I want to know is there is some better algorithm to define the triangle may be using equations and what it might be.

Community
  • 1
  • 1
M T
  • 161
  • 1
  • 2
  • 13
  • 1
    Use barycentric coordinates for the 2D case: http://en.wikipedia.org/wiki/Barycentric_coordinates_%28mathematics%29#Determining_whether_a_point_is_inside_a_triangle – Marco A. Feb 12 '14 at 19:21

1 Answers1

0

You can you the concept of vector products to find if a point is inside a triangle or not :-

suppose point is (x,y) which you need to check. (x1,y1),(x2,y2),(x3,y3) are three vertices of the triangle. then each triple ((x1,y1),(x2,y2),(x,y)),((x2,y2),(x3,y3),(x,y)),((x3,y3),(x1,y1),(x,y)) are of same sign. 

vector product of (x1,y1),(x2,y2),(x,y)

vp = (x-x2)*(y1-y2) - (y-y2)*(x1-x2)

Hence using same equation for all triples :-

sign1 = sign((x-x2)*(y1-y2) - (y-y2)*(x1-x2))
sign2 = sign((x-x3)*(y2-y3) - (y-y3)*(x2-x3))
sign3 = sign((x-x1)*(y3-y1) - (y-y1)*(x3-x1))


if(sign1==sign2==sign3) { //inside

       return(true);

}

else return(false)      // outside
Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19