[vtkusers] polygon fill / PointInPolygon

[Karthik Krishnan]

chensiqi wrote:
>
>
> A further question:
>
> If all my points on coplanar, the normal direction that returns from
> ComputeNomal will be either [0,0,1] or [0,0,-1], which makes sense in
> 3D view.
> Rays shooting along this normal direction will never intersect with
> the edges of the polygon. 
As I mentioned below, rays are fired along the plane that is
perpendicular to the normal (supplied as argument), not along the normal.
> I guess this is the reason why the whole region inside the bounding
> box is decided as "inside" ( 0 is an even number ).
>
> I did another experiment by choosing normal direction as [0.707,
> 0.707, 0]. The result is better, at least not the whole region in the
> bounds are given as "inside". But there many isolated points are still
> given wrong decisions due to numerical problem, I think.
In practice the method shoots more than 1 ray (upto 10 rays) in random
directions. This is to account for the possibility that you could have a
ray intersecting a vertex (and hence two lines there) and an inside
point being misclassified as outside (or vice versa). There is also a
tolerance used for checks, which is pretty tight.
>
> What should I do under this coplanarity conditon?
It should work just fine for a coplanar polygon. You can try debugging.
Its a fairly straightforward method and I can't imagine how it might fail.
>
> Thanks
> Siqi
>
> > Date: Tue, 16 Dec 2008 04:11:13 -0500
> > From: karthik.krishnan at kitware.com
> > To: pidanchen at hotmail.com
> > CC: vtkusers at vtk.org
> > Subject: Re: [vtkusers] polygon fill / PointInPolygon
> >
> > chensiqi wrote:
> > >
> > > Hi, VTKers
> > >
> > > I wonder if there is any Polygon fill algorithm implemented in
> > > VTKPolygon class?
> > >
> > > If not, maybe Loop through all the points using PointInPolygon is the
> > > only way I can think of.
> > Yes, at present the only way in VTK.
> > >
> > > Is that " n " in the parameter list of PointInpolygon the normal
> > > direction? How to estimate it?
> > Yes it is.
> > vtkPolygon::ComputeNormal should do the job for you.
> >
> > The method works by firing rays and checking the number of times a ray
> > drawn through the line intersects the polygon. Even times implies
> > outside, odd times => inside. The normal is needed to get the direction
> > the rays are fired in (they are perpendicular to the normal). The class
> > could have computed the normal for you, but it is left to the user for
> > efficiency, since its likely that you will call the methods several
> > times and wouldn't want to recompute the polygon normal each time.
> >
> > > int vtkPolygon::*PointInPolygon* (double x[3], int numPts, double
> > > *pts, double bounds[6], double *n)
> > >
> > > Thanks for your help.
> > >
> > > Siqi
> > >
> > >
> > >
> > >
> ------------------------------------------------------------------------
> > > 更多热辣资讯尽在新版MSN首页！ 立刻访问！ <http://cn.msn.com/>
> > >
> ------------------------------------------------------------------------
> > >
> > > _______________________________________________
> > > This is the private VTK discussion list.
> > > Please keep messages on-topic. Check the FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
> > > Follow this link to subscribe/unsubscribe:
> > > http://www.vtk.org/mailman/listinfo/vtkusers
> > >
> >
> > --
> > Karthik Krishnan
> > R & D Engineer,
> > Kitware Inc,
> > Ph: 518 371 3971 x119
> > Fax: 518 371 3971
> >
>
>
> ------------------------------------------------------------------------
> 使用新一代 Windows Live Messenger 轻松交流和共享！ 立刻下载！
> <http://im.live.cn/>

-- 
Karthik Krishnan
R & D Engineer,
Kitware Inc,
Ph:  518 371 3971 x119
Fax: 518 371 3971