## Am I inside - an answer.c

### Am I inside - an answer.c

Thanks to all who sent/posted ideas on how to tell if
a point is in a quadrilateral.

First, let me see if I can correctly state the problem I'm
trying to solve.

Given any quadrilateral Q whose sides do not intersect and
a point P. Is P inside Q?  NB:  Q may or may not
be convex.

The approach I used is based on a response from Chad Wolfsheimer:

Algorithm:
Given: a point q and a polygon P whose vertices have y-coordinate distinct
from y(q) where y(q) is the y-coordinate of point q.
Output: an indication of whether q is inside or outside P
Compute the maximum x-coordinate xm of the vertices of P.
Let s be the segment with endpoints q and (xm,y(q)).
i=0.
For each edge e of P do
If segments s and e intersect then
i=i+1
If i is odd then
return "inside"
else
return "outside"

The attached code compiled using on a RH 5.0 using egcs-1.1b and
lesstif-0.87.0 ( Motif 2.0 compatibility ).  The widget code works for
me.  How is more by accident than by design as I'm still learning
lesstif/Motif.  The real action is in inputCG which processes all
mouse input events.

The algorithm as coded:

0.  For all sides do:
1.  Ensure that the side spans the point vertically.
2.  Compute the x value of the side that corresponds to the
y value of the point.
3.  If the computed x value is greater that the point x value
( to the right of the point ) count the line.
4.  If the count is odd "I'm Inside!!"

Note: For convience the first point of each polygon is repeated as
the fifth point for use in XDrawLine.

/* Begin C code */

#include <stdio.h>

#include <Xm/Xm.h>
#include <Xm/Form.h>
#include <Xm/Frame.h>
#include <Xm/DrawingA.h>

/* Widget specific stuff */
XtAppContext appContext;
Widget topLevel,
form,
filePopUp,
frame,
drawingArea;

GC        gc;
XGCValues GCvalues;

/* The array of quadrilaterals */
typedef struct
{
XPoint point[5];

} Polygon;

Polygon   polygon[4];
int       nPoly = 3;

/* Callbacks */
/* Is this point inside one of the polygons? */
static void inputCB( Widget w, XtPointer Client_data, XtPointer Call_data )
{
XmDrawingAreaCallbackStruct *CB = (XmDrawingAreaCallbackStruct *)Call_data;

int i, j;
int inside;

inside = -1;
if( CB->event->type == ButtonPress )
{
for( i=0; i<nPoly; i++ )
{
int count=0;

for( j=0; j<4; j++ )
{
int x;
int dx, dy;

if( ( CB->event->xbutton.y < polygon[i].point[j].y
&&
CB->event->xbutton.y < polygon[i].point[j+1].y )
||
( CB->event->xbutton.y > polygon[i].point[j].y
&&
CB->event->xbutton.y > polygon[i].point[j+1].y ) )
continue;

dx = polygon[i].point[j+1].x - polygon[i].point[j].x;
dy = polygon[i].point[j+1].y - polygon[i].point[j].y;

if( dy == 0 )
{
if(  CB->event->xbutton.x == polygon[i].point[j+1].x )
count++;
continue;
}

x = ( CB->event->xbutton.y * dx
- polygon[i].point[j].y * dx
+ polygon[i].point[j].x * dy ) / dy;

if( x > CB->event->xbutton.x )
count++;
}
if( count & 1 )
{
inside = i;
break;
}
}
if( inside != -1 )
fprintf( stderr, "Point (%i,%i) is inside polygon %i\n",
CB->event->xbutton.x, CB->event->xbutton.y, inside );
else
fprintf( stderr, "Point (%i,%i) is outside all polygons\n",
CB->event->xbutton.x, CB->event->xbutton.y );
}
return;

}

/* Exit button is the only File option */
static void
fileCB( Widget w, XtPointer Client_data, XtPointer Call_data )
{
switch ( (int)Client_data )
{
case 0:
{
exit( 0 );
break;
}
}

}

/* Draw the polygons */
static void exposeCB( Widget w, XtPointer Client_data, XtPointer Call_data )
{
Colormap  colors;
XColor    exact, screen;
int       i;

/* Polygon 1 - a square */
polygon[0].point[0].x =  50;
polygon[0].point[0].y =  50;
polygon[0].point[1].x = 150;
polygon[0].point[1].y =  50;
polygon[0].point[2].x = 150;
polygon[0].point[2].y = 150;
polygon[0].point[3].x =  50;
polygon[0].point[3].y = 150;
polygon[0].point[4].x =  50;
polygon[0].point[4].y =  50;

/* Polygon 2 - a V */
polygon[1].point[0].x = 250;
polygon[1].point[0].y =  50;
polygon[1].point[1].x = 300;
polygon[1].point[1].y = 200;
polygon[1].point[2].x = 350;
polygon[1].point[2].y =  50;
polygon[1].point[3].x = 300;
polygon[1].point[3].y = 250;
polygon[1].point[4].x = 250;
polygon[1].point[4].y =  50;

/* Polygon 3 - a Parallelogram */
polygon[2].point[0].x = 500;
polygon[2].point[0].y = 220;
polygon[2].point[1].x = 575;
polygon[2].point[1].y = 120;
polygon[2].point[2].x = 575;
polygon[2].point[2].y =  20;
polygon[2].point[3].x = 500;
polygon[2].point[3].y = 120;
polygon[2].point[4].x = 500;
polygon[2].point[4].y = 220;

colors = DefaultColormapOfScreen(XtScreen(w));
XLookupColor( XtDisplay( w),
colors,
"green",
&exact,
&screen
);
XAllocColor( XtDisplay( w ),
colors,
&screen
);

GCvalues.foreground = screen.pixel;
XChangeGC( XtDisplay( w ),
gc,
GCForeground|GCBackground,
&GCvalues
);

for( i=0; i<nPoly; i++ )
{
XFillPolygon( XtDisplay( w ),
XtWindow( w ),
gc,
polygon[i].point,
4,
Nonconvex,
CoordModeOrigin
);
}

XLookupColor( XtDisplay( w),
colors,
"darkgreen",
&exact,
&screen
);
XAllocColor( XtDisplay( w ),
colors,
&screen
);

GCvalues.foreground = screen.pixel;
XChangeGC( XtDisplay( w ),
gc,
GCForeground|GCBackground,
&GCvalues
);
XSetLineAttributes( XtDisplay( w ),
gc,
3,
LineSolid,
CapRound,
JoinRound );

for( i=0; i<nPoly; i++ )
{
XDrawLines( XtDisplay( w ),
XtWindow( w ),
gc,
polygon[i].point,
5,
CoordModeOrigin
);
}

}

int main( int argc, char *argv[] )
{
char *Fallback[] =
{
NULL
};

XtSetLanguageProc(NULL, NULL, NULL);

topLevel = XtVaAppInitialize(&appContext,
"Inside",
NULL,
0,
&argc, argv,
Fallback,
NULL
);

form = XtVaCreateManagedWidget("form",
xmFormWidgetClass,
topLevel,
XmNtraversalOn, False,
NULL
);

{
XmString s1, s2;
Widget widget;

s1 = XmStringCreateLocalized("File");
s2 = XmStringCreateLocalized("Help");

XmNtopAttachment,   XmATTACH_FORM,
XmNleftAttachment,  XmATTACH_FORM,
XmNrightAttachment, XmATTACH_FORM,
NULL
);

if( widget = XtNameToWidget( menuBar, "button_1" ) )

XmStringFree(s1);
XmStringFree(s2);
}

{
XmString s1;

s1 = XmStringCreateLocalized("Exit");

0,
fileCB,
XmVaPUSHBUTTON,
s1,
NULL,
NULL,
NULL,
NULL
);

XmStringFree( s1 );
}

/* Add framed drawing area */
{
frame =  XtVaCreateManagedWidget("frame",
xmFrameWidgetClass,
form,
XmNtopAttachment,  XmATTACH_WIDGET,
XmNleftAttachment,  XmATTACH_FORM,
XmNrightAttachment, XmATTACH_FORM,
XmNbottomAttachment,   XmATTACH_FORM,
NULL
);
drawingArea = XtVaCreateManagedWidget("drawing_area",
xmDrawingAreaWidgetClass,
frame,
XtNheight, 300,
XtNwidth, 700,
NULL
);
XtAddCallback( drawingArea, XmNinputCallback,  inputCB,  NULL );
XtAddCallback( drawingArea, XmNexposeCallback, exposeCB, NULL );

}

XtRealizeWidget(topLevel);

gc = XCreateGC( XtDisplay( drawingArea ),  /* Used in exposeCB */
XtWindow( drawingArea ),
0,
&GCvalues
);

XtAppMainLoop(appContext);

return;

}

--
Steve
harri...@eskimo.com

This question has nothing to do with linux other than that
is the OS I use.  The question is:

Given a regular quadrilateral defined by the 4 vertices,
and
Given a random point
question
Is the point inside the quadrilateral?

What is the fastest way to answer this question?

Thanks
--
Steve

6. Ldap

8. Test