[Insight-users] Class to represent points of closed contour?
Ofri Sadowsky
ofri@cs.jhu.edu
Sat, 30 Nov 2002 15:19:00 -0500
--------------637D5D26E828F13D47022C75
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Depending on permission of my supervisors, I could send you my Polygon
class that uses itk::Mesh. It's not completely tested yet, and it's
using the STLContainerAdapter class that I was working on together with
Luis. But it's there if you want it.
As for testing whether a point is in a mesh or in a polygon. For 2D,
where the number of faces is the number of edges is the number of
verstices = n , I cannot think of a better performance time than
O(n) for a single point test. Then if you have k points, it should take
O(kn). But if you want to test many points, you may consider rendering
the polygon into a pixelized image, and then test the pixels. That works
great if the points you're testing are pixels, and not so bad in most
cases where they're not.
For dimensions greater than 2, the probelm gets complicated. I think the
most efficient algorithm should do O(f) where f is the number of faces
(or maybe boundary faces) of the mesh.
Parag Chandra wrote:
> Thanks Ofri. I am looking into itk::Mesh, and it seems it provides
> methods to SetPoint() and GetPoint(), but a PointIdentifier is
> required in both cases. All I want to do is tack points onto the end
> of a list, so rather than maintain my own counter that I have to
> increment after adding each point, is there a convenient way to just
> AddPoint(), so the PointIdentifier for a given mesh always starts at
> zero and just keeps incrementing every time a point is added?
>
> ----- Original Message -----
> From: Ofri Sadowsky
> To: Parag Chandra
> Cc: insight-users@public.kitware.com
> Sent: Wednesday, November 27, 2002 9:42 AM
> Subject: Re: [Insight-users] Class to represent points of
> closed contour?
> Joining the question.
> I have been searching for a similar thing for a while, and
> have not found it yet. I thought that itk::MeshRegion was
> supposed to handle that, but from a recent question of mine,
> it is not yet fully developed.
> In any case, you can try to use itk::Mesh to represent the
> polygon (contour). I've been working on that too for a
> while, and I'm about to get some results. But that still
> does not answer for the "IsInside" question.
>
> Ofri.
>
> Parag Chandra wrote:
>
> > Hi all, I apologize if this has been asked before, but
> > it's currently a little difficult to search the archives.
> > Basically what I want to know is, what is the best way to
> > represent the points of a closed contour that I've traced
> > out on a 2-D, binary image? I am currently just using
> > std::vector<itk::Point> for this purpose, but I would like
> > to be able to perform operations like "Is a given point
> > inside the contour or outside?", and I suspect that there
> > is already something in ITK that will let me do this.
> > Thanks in advance. Best regards,Parag Chandra
>
--------------637D5D26E828F13D47022C75
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<body bgcolor="#FFFFFF">
Depending on permission of my supervisors, I could send you my Polygon
class that uses itk::Mesh. It's not completely tested yet, and it's using
the STLContainerAdapter class that I was working on together with Luis.
But it's there if you want it.
<br>As for testing whether a point is in a mesh or in a polygon. For 2D,
where the number of faces is the number of edges is the number of verstices
= n , I cannot think of a better performance time than O(n) for
a single point test. Then if you have k points, it should take O(kn). But
if you want to test many points, you may consider rendering the polygon
into a pixelized image, and then test the pixels. That works great if the
points you're testing are pixels, and not so bad in most cases where they're
not.
<br>For dimensions greater than 2, the probelm gets complicated. I think
the most efficient algorithm should do O(f) where f is the number of faces
(or maybe boundary faces) of the mesh.
<p>Parag Chandra wrote:
<blockquote TYPE=CITE> <font face="Arial"><font size=-1>Thanks Ofri.
I am looking into itk::Mesh, and it seems it provides methods to SetPoint()
and GetPoint(), but a PointIdentifier is required in both cases. All I
want to do is tack points onto the end of a list, so rather than maintain
my own counter that I have to increment after adding each point, is there
a convenient way to just AddPoint(), so the PointIdentifier for a given
mesh always starts at zero and just keeps incrementing every time a point
is added?</font></font>
<blockquote dir=ltr
style="PADDING-RIGHT: 0px; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #000000 2px solid; MARGIN-RIGHT: 0px">
<div style="FONT: 10pt arial">----- Original Message -----</div>
<div
style="BACKGROUND: #e4e4e4; FONT: 10pt arial; font-color: black"><b>From:</b>
<a href="mailto:ofri@cs.jhu.edu" title="ofri@cs.jhu.edu">Ofri Sadowsky</a></div>
<div style="FONT: 10pt arial"><b>To:</b> <a href="mailto:pchandra@radonc.unc.edu" title="pchandra@radonc.unc.edu">Parag
Chandra</a></div>
<div style="FONT: 10pt arial"><b>Cc:</b> <a href="mailto:insight-users@public.kitware.com" title="insight-users@public.kitware.com">insight-users@public.kitware.com</a></div>
<div style="FONT: 10pt arial"><b>Sent:</b> Wednesday, November 27, 2002
9:42 AM</div>
<div style="FONT: 10pt arial"><b>Subject:</b> Re: [Insight-users] Class
to represent points of closed contour?</div>
Joining the question.
<br>I have been searching for a similar thing for a while, and have not
found it yet. I thought that itk::MeshRegion was supposed to handle that,
but from a recent question of mine, it is not yet fully developed.
<br>In any case, you can try to use itk::Mesh to represent the polygon
(contour). I've been working on that too for a while, and I'm about to
get some results. But that still does not answer for the "IsInside" question.
<p>Ofri.
<p>Parag Chandra wrote:
<blockquote TYPE="CITE"><style></style>
<font face="Arial"><font size=-1>Hi
all,</font></font> <font face="Arial"><font size=-1>I apologize if this
has been asked before, but it's currently a little difficult to search
the archives. Basically what I want to know is, what is the best way to
represent the points of a closed contour that I've traced out on a 2-D,
binary image? I am currently just using std::vector<itk::Point> for
this purpose, but I would like to be able to perform operations like "Is
a given point inside the contour or outside?", and I suspect that there
is already something in ITK that will let me do this. Thanks in advance.</font></font>
<font face="Arial"><font size=-1>Best regards,Parag Chandra</font></font></blockquote>
</blockquote>
</blockquote>
</body>
</html>
--------------637D5D26E828F13D47022C75--