by 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,
menuBar,
filePopUp,
frame,
drawingArea;
GC gc;
XGCValues GCvalues;
/* The array of quadrilaterals */
typedef struct
{
XPoint point[5];
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;
static void
fileCB( Widget w, XtPointer Client_data, XtPointer Call_data )
{
switch ( (int)Client_data )
{
case 0:
{
exit( 0 );
break;
}
}
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
);
}
{
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
);
/* Create menu bar */
{
XmString s1, s2;
Widget widget;
s1 = XmStringCreateLocalized("File");
s2 = XmStringCreateLocalized("Help");
menuBar = XmVaCreateSimpleMenuBar( form,
"menubar",
XmVaCASCADEBUTTON, s1, 'F',
XmVaCASCADEBUTTON, s2, 'H',
XmNtopAttachment, XmATTACH_FORM,
XmNleftAttachment, XmATTACH_FORM,
XmNrightAttachment, XmATTACH_FORM,
NULL
);
if( widget = XtNameToWidget( menuBar, "button_1" ) )
XtVaSetValues( menuBar, XmNmenuHelpWidget, widget, NULL );
XmStringFree(s1);
XmStringFree(s2);
}
/* Add "File" button */
{
XmString s1;
s1 = XmStringCreateLocalized("Exit");
filePopUp = XmVaCreateSimplePulldownMenu( menuBar,
"file_menu",
0,
fileCB,
XmVaPUSHBUTTON,
s1,
NULL,
NULL,
NULL,
NULL
);
XmStringFree( s1 );
}
/* Add framed drawing area */
{
frame = XtVaCreateManagedWidget("frame",
xmFrameWidgetClass,
form,
XmNshadowThickness, 7,
XmNshadowType, XmSHADOW_IN,
XmNtopAttachment, XmATTACH_WIDGET,
XmNtopWidget, menuBar,
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 );
}
XtManageChild( menuBar );
XtRealizeWidget(topLevel);
gc = XCreateGC( XtDisplay( drawingArea ), /* Used in exposeCB */
XtWindow( drawingArea ),
0,
&GCvalues
);
XtAppMainLoop(appContext);
return;
Steve
harri...@eskimo.com