Am I inside - an answer.c

Am I inside - an answer.c

Post by Steven M. Harringt » Sat, 21 Nov 1998 04:00:00



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];

} 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
                                 );

  /* 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
 
 
 

1. Am I inside?

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

2. postfix : mail deferred

3. HELP! I am trapped inside of XDM!!!

4. NYC LOCAL: Thursday 21 November 2002 UNIGROUP: Carl Sayres on End to End Java Wireless Applications

5. How can I tell whether I am logging in on console inside .login?

6. Ldap

7. I am looking for a simple answer - CompTIA, LPI or Red Hat Certification?

8. Test

9. "Linux Inside": Spoof of Intel Inside

10. Formattet output inside variable / line brak inside variable

11. FTP client inside linux firewall communicating with FTP server inside another linux firewall

12. This clone thing...am I stupid, or am I right?