1 -- Given three colinear points p, q, r, the function checks if
2 -- point q lies on line segment 'pr'
3 function onSegment(p,q,r)
4 if(q.x <= math.max(p.x,r.x) and q.x >= math.min(p.x,r.x) and
5 q.y <= math.max(p.y,r.y) and q.y>= math.min(p.y,r.y)) then
12 -- To find orientation of ordered triplet (p, q, r).
13 -- The function returns following values
14 -- 0 --> p, q and r are colinear
16 -- 2 --> Counterclockwise
17 function orientation(p,q,r)
18 val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y)
30 -- The function that returns true if line segment 'p1q1'
31 -- and 'p2q2' intersect.
32 function doIntersect(p1,q1,p2,q2)
33 -- Find the four orientations needed for general and
35 o1 = orientation(p1, q1, p2)
36 o2 = orientation(p1, q1, q2)
37 o3 = orientation(p2, q2, p1)
38 o4 = orientation(p2, q2, q1)
40 -- gerenal case (without limite case)
41 if(o1 ~= o2 and o3 ~= o4) then
46 -- p1, q1 and p2 are colinear and p2 lies on segment p1q1
47 if (o1 == 0 and onSegment(p1, p2, q1)) then return true end
48 -- p1, q1 and p2 are colinear and q2 lies on segment p1q1
49 if (o2 == 0 and onSegment(p1, q2, q1)) then return true end
50 -- p2, q2 and p1 are colinear and p1 lies on segment p2q2
51 if (o3 == 0 and onSegment(p2, p1, q2)) then return true end
52 -- p2, q2 and q1 are colinear and q1 lies on segment p2q2
53 if (o4 == 0 and onSegment(p2, q1, q2)) then return true end
54 return false; -- Doesn't fall in any of the above cases
57 -- Returns true if the point p lies inside the polygon[] with n vertices
58 function isInside(listPoints,p)
59 -- There must be at least 3 vertices in polygon[]
60 if (#listPoints <= 3) then return false end
61 -- Create a point for line segment from p to infinite
62 extreme = {x=1e05,y=p.y};
63 -- Count intersections of the above line with sides of polygon
65 for i=1,#listPoints do
66 ip = (i)%(#listPoints)+1
67 -- Check if the line segment from 'p' to 'extreme' intersects
68 -- with the line segment from 'polygon[i]' to 'polygon[next]'
69 if (doIntersect(listPoints[i], listPoints[ip], p, extreme)) then
70 -- If the point 'p' is colinear with line segment 'i-ip',
71 -- then check if it lies on segment. If it lies, return true,
73 if (orientation(listPoints[i], p, listPoints[ip]) == 0) then
74 return onSegment(listPoints[i], p, listPoints[ip])
79 -- Return true if count is odd, false otherwise