【转帖】finding whether a given point is inside a polyline
 

finding whether a given point is inside a polyline

finding whether a given point is inside a polyline
hi all,
i'm using an mfc application for viewing editing a dwg drawing file. i'm using the dwgdirect version 1.11.01.
i've added polylines to an existing drawing. i need to know how to find out a given point is inside a polyline or not. is there any function provided for this functionality.
can anyone say the solution for this problem.
thanks & regards,
rajesh parameswaran

rajuinnet
# 12th august 2004, 12:54 am

registered user join date: mar 2003
location: spain
posts: 86
if what you want is to know if a given point is inside one of the added polylines, i think you could just "make a selection" (similar to odamfcapp)when the user picks a point and analyse the selected entities set in order to know if any of the polylines added to the drawing is in that selection set.
in order to distinguish the added polylines from other entities in the selection set you should had marked the added polylines in some way, what i do is adding an xdata to this entities.
but if you need to know if a given point is in a given polyline i think you could use oddbcurve getdistatpoint() function.
sorry if i misunderstood your question.

suaser
# 12th august 2004, 01:06 am

founding member join date: jun 2002
location: bulgaria
posts: 377
here is a sample code that works for 2d polygons, hope it helps (may not compile, but you should be able to run it; also increase the epsilon):
code:
inline int idxmod(const int i, const int n) {return (i+n)%n;}
// returns 1 when point on or inside polygon, 0 otherwise
int ge2_pointinpoly(const odgepoint2d p1, const vector<odgepoint2d>& pnt)
{
const double epsilon = 0.001;
int i,j,e; double t;

int n = (int)pnt.size();
double x = p1.x;
double y = p1.y;
e = 0;
for (i=0; i<n; ++i) {
t = (x-pnt[i].x)*(pnt[idxmod(i+1,n)].y-pnt[i].y) - (y-pnt[i].y)*(pnt[idxmod(i+1,n)].x-pnt[i].x);
if (fabs(t) <= epsilon && (x-pnt[i].x)*(x-pnt[idxmod(i+1,n)].x) <= 0. && (y-pnt[i].y)*(y-pnt[idxmod(i+1,n)].y) <= 0.)
return 1;
j = pnt[i].y<pnt[idxmod(i+1,n)].y;

// count iff (x,y) is strictly to the left of edge
if (pnt[idxmod(i+(1-j),n)].y < y && y < pnt[idxmod(i+j,n)].y && (j ? t : -t) < 0.)
e = !e;
else
if (y==pnt[i].y)
{// find [j] and [i] strictly above/below y
if (i==0) {
for (j=n-1; y==pnt[j].y; --j);
n = j;
}
else
j = i-1;

while (y==pnt[idxmod(i+1,n)].y)
++i;

/* count iff y is strictly between [j] and [i] */
e ^= (y-pnt[j].y)*(y-pnt[idxmod(i+1,n)].y) < 0.;
}// if
}//for

return e;
}
regards
chudomir

chudo
# 12th august 2004, 02:01 am

registered user join date: jan 2003
posts: 16
how about the following:
imagine a reference line which is completely at the left of a polygon (calculate extends, decrease the extends->x with one and you got your line outside the polygon).
code:
*
| +---------+
| / |
#..../........q |
| + |
| | +----+ |
#...|..|.p | |
| +--+ +----+
*
^- reference line (l)
l -> q: one intersection with the edges of the polygon -> odd -> inside
l -> p: two intersections with the edges of the polygon -> even -> outside
exception for a point on an edge: inside?

dm, arkey systems bv
# 12th august 2004, 02:04 am

registered user join date: oct 2003
posts: 344
i always followed the same rule of odd and even. from the comp.algorithm newsgroup.
andrew

andrew.truckle@cartosurveys.co.uk
# 13th august 2004, 06:06 am

registered user join date: may 2004
location: poland
posts: 132
quote:
originally posted by dm, arkey systems bv
how about the following:
imagine a reference line which is completely at the left of a polygon (calculate extends, decrease the extends->x with one and you got your line outside the polygon).
code:
*
| +---------+
| / |
#..../........q |
| + |
| | +----+ |
#...|..|.p | |
| +--+ +----+
*
^- reference line (l)
l -> q: one intersection with the edges of the polygon -> odd -> inside
l -> p: two intersections with the edges of the polygon -> even -> outside
exception for a point on an edge: inside?
there are some exceptions that makes this method not so simple as it look like.
code:
*
| +---------+
| / |
| / |
| + |
|...|..+.o |
| | |\ |
| +--+ +-------+
*
*
| +---------+
| / |
| / + |
| + / \ |
|...|..+.o \ |
| | | \ |
| +--+ +---+
*

sliwka
# 13th august 2004, 06:27 am

registered user join date: jan 2003
posts: 16
consider endpoints not to be part of the line... so if you find an intersection on the endpoint just skip it...

dm, arkey systems bv
# 16th august 2004, 02:17 am

softdev join date: jun 2002
location: st'petersburg, russia
posts: 522

sliwka,
these exceptions are not very hard.
if ray goes through the vertex - need to look on two edges, going from this vertex. if them both are in one side of ray (first your picture) - then we should interpret this as even number of intersections. if them are in different sides of ray - this should be interpreted as odd number of intersections. to find are edges on one side of ray, or on different sides, it is easy to use cross product.
one more exception case is
1) ray goes through the vertex
2) one of the edges (or both edges), going from this vertex, are codirectional with the ray.
in this case it is not clear wether edges in one side of ray or in different sides.
but in this case edges, that are codirectional with ray, should be ignored (previous or next edge should be taken instead of one(s) codirectional with ray).
btw, i believe that code, posted by chudomir, works
sincerely yours,
george udov

george udov
# 17th august 2004, 12:53 am

founding member join date: jun 2002
location: bulgaria
posts: 377
thanks, i'm not its author, and don't know how it works, but it seemed to work for the cases we've tested...
regards
chudomir
best regards
chudomir

chudo

none
? | ?
thread tools



display modes
linear mode


search this thread

rate this thread
excellent
good
average
bad
terrible

posting rules
you may post new threads
you may post replies
you may post attachments
you may edit your posts
is on
are on
code is off
html code is off
forum jump
user control panel private messages subscriptions who's online search forums forums home general topics news questions and remarks business issues industry commentary general software issues documentation issues future directions dwg libraries dwgdirect.net dwgdirect, c++ version dwgdirectx, activex version adtdirect/c3ddirect opendwg toolkit/viewkit dgn libraries dgndirect, c++ version (2.x+) dgndirect libraries (legacy 0.99xx)
all times are gmt -7. the time now is 01:01 amfff">.
- - -
copyright ?2000 - 2009, jelsoft enterprises ltd.
copyright 1998-2008 open design alliance inc.
if what you want is to know if a given point is inside one of the added polylines, i think you could just "make a selection" (similar to odamfcapp)when the user picks a point and analyse the selected entities set in order to know if any of the polylines added to the drawing is in that selection set.
in order to distinguish the added polylines from other entities in the selection set you should had marked the added polylines in some way, what i do is adding an xdata to this entities.
but if you need to know if a given point is in a given polyline i think you could use oddbcurve getdistatpoint() function.
sorry if i misunderstood your question.
here is a sample code that works for 2d polygons, hope it helps (may not compile, but you should be able to run it; also increase the epsilon):
code:
inline int idxmod(const int i, const int n) {return (i+n)%n;}
// returns 1 when point on or inside polygon, 0 otherwise
int ge2_pointinpoly(const odgepoint2d p1, const vector<odgepoint2d>& pnt)
{
const double epsilon = 0.001;
int i,j,e; double t;

int n = (int)pnt.size();
double x = p1.x;
double y = p1.y;
e = 0;
for (i=0; i<n; ++i) {
t = (x-pnt[i].x)*(pnt[idxmod(i+1,n)].y-pnt[i].y) - (y-pnt[i].y)*(pnt[idxmod(i+1,n)].x-pnt[i].x);
if (fabs(t) <= epsilon && (x-pnt[i].x)*(x-pnt[idxmod(i+1,n)].x) <= 0. && (y-pnt[i].y)*(y-pnt[idxmod(i+1,n)].y) <= 0.)
return 1;
j = pnt[i].y<pnt[idxmod(i+1,n)].y;

// count iff (x,y) is strictly to the left of edge
if (pnt[idxmod(i+(1-j),n)].y < y && y < pnt[idxmod(i+j,n)].y && (j ? t : -t) < 0.)
e = !e;
else
if (y==pnt[i].y)
{// find [j] and [i] strictly above/below y
if (i==0) {
for (j=n-1; y==pnt[j].y; --j);
n = j;
}
else
j = i-1;

while (y==pnt[idxmod(i+1,n)].y)
++i;

/* count iff y is strictly between [j] and [i] */
e ^= (y-pnt[j].y)*(y-pnt[idxmod(i+1,n)].y) < 0.;
}// if
}//for

return e;
}
regards
chudomir
how about the following:
imagine a reference line which is completely at the left of a polygon (calculate extends, decrease the extends->x with one and you got your line outside the polygon).
code:
*
| +---------+
| / |
#..../........q |
| + |
| | +----+ |
#...|..|.p | |
| +--+ +----+
*
^- reference line (l)
l -> q: one intersection with the edges of the polygon -> odd -> inside
l -> p: two intersections with the edges of the polygon -> even -> outside
exception for a point on an edge: inside?
i always followed the same rule of odd and even. from the comp.algorithm newsgroup.
andrew
quote:
originally posted by dm, arkey systems bv
how about the following:
imagine a reference line which is completely at the left of a polygon (calculate extends, decrease the extends->x with one and you got your line outside the polygon).
code:
*
| +---------+
| / |
#..../........q |
| + |
| | +----+ |
#...|..|.p | |
| +--+ +----+
*
^- reference line (l)
l -> q: one intersection with the edges of the polygon -> odd -> inside
l -> p: two intersections with the edges of the polygon -> even -> outside
exception for a point on an edge: inside?
there are some exceptions that makes this method not so simple as it look like.
code:
*
| +---------+
| / |
| / |
| + |
|...|..+.o |
| | |\ |
| +--+ +-------+
*
*
| +---------+
| / |
| / + |
| + / \ |
|...|..+.o \ |
| | | \ |
| +--+ +---+
*
consider endpoints not to be part of the line... so if you find an intersection on the endpoint just skip it...

sliwka,
these exceptions are not very hard.
if ray goes through the vertex - need to look on two edges, going from this vertex. if them both are in one side of ray (first your picture) - then we should interpret this as even number of intersections. if them are in different sides of ray - this should be interpreted as odd number of intersections. to find are edges on one side of ray, or on different sides, it is easy to use cross product.
one more exception case is
1) ray goes through the vertex
2) one of the edges (or both edges), going from this vertex, are codirectional with the ray.
in this case it is not clear wether edges in one side of ray or in different sides.
but in this case edges, that are codirectional with ray, should be ignored (previous or next edge should be taken instead of one(s) codirectional with ray).
btw, i believe that code, posted by chudomir, works
sincerely yours,
george udov
thanks, i'm not its author, and don't know how it works, but it seemed to work for the cases we've tested...
regards
chudomir
best regards
chudomir