Flipkart Interview Question
Software Engineer / DevelopersOne of the vertices or inside? No matter; the answer is still binary search, with the appropriate geometric primitives.
bool pointInPolygon() {
int i, j=polySides-1 ;
boolean oddNodes=NO ;
for (i=0; i<polySides; i++) {
if ((polyY[i]< y && polyY[j]>=y
|| polyY[j]< y && polyY[i]>=y)
&& (polyX[i]<=x || polyX[j]<=x)) {
oddNodes^=(polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x); }
j=i; }
return oddNodes; }
1. a point lies in a polygon if any ray intersecting it and the polygon from any direction intersects odd number of lines (pretty intuitive). this ray can be drawn from x or y axis.
2. let us draw a ray along x axis. in this case we can state that if we have odd number of lines cutting the ray (ie odd number of lines to the right of the point) then the point is interior.
3. what flowoing code does is.
for (i=0; i<polySides; i++) {
if ((polyY[i]< y && polyY[j]>=y
|| polyY[j]< y && polyY[i]>=y)
&& (polyX[i]<=x || polyX[j]<=x)) {
oddNodes^=(polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x); }
j=i; }
if you observe. we iterate over each line and ensure that for all lines which sweep the point along y axis we have seen that the point lies on its right.
I know this uses a even-odd algorithm ... but i dot not completely understand how this code works in the if () condition....can anyone explain ?
- lesnar June 24, 2011bool pointInPolygon() {
int i, j=polySides-1 ;
boolean oddNodes=NO ;
for (i=0; i<polySides; i++) {
if (polyY[i]<y && polyY[j]>=y
|| polyY[j]<y && polyY[i]>=y) {
if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x) {
oddNodes=!oddNodes; }}
j=i; }
return oddNodes; }