[vtkusers] (no subject)

[Benjamin King]

Hello Shyam,

I don't know about the most efficient way to find the kernel of a polygon 
but in principle you could do it like this:

0) extend each edge to a straight line. That way you divide the whole plane 
into two half-planes.
1) discard the half plane from which you can see the outside of the edge 
and keep the other one.
2) the intersection of all the half-planes you kept is the kernel.

In practice (and with VTK), you could clip the whole polygon against each 
of the extended edges (use a vtkClipPolyData and a suitable 
vtkImplicitPlane for each edge). That may be slower than necessary but it's 
built in VTK, so you don't have much to do to get a first impression.

Either way, the resulting polygon is your kernel. It is guaranteed to be 
convex but it may be empty.

But if I understood you right, you don't know the edges in advance, so it 
is generally not possible to draw the kernel. Consider the following ugly 
ASCII picture to see the problem:

These points:
.     .
  . .
  . .
.     .

may either be this polygon:
_______
\     /
 \   /
 |   |
 /   \
/_____\

or this one:
 ______
|      |
|  __  |
| |  | |
| /  \ |
|/    \|

There are more possibilities, but you see what I mean.

So what can you do? First, try to specify the types of polygons you expect 
very precise. Then see if you can get away with taking the mean of the 
points. That approach will work for the hour glass shaped example above, 
for a star and for every convex polygon. If it doesn't work, see if you can 
find a point 'in the middle' the polygon you expect, for example by finding 
a bounded maximum of a distance map or whatever.
It really depends on your possible input data, so get a good feel - or 
better yet: a good knowledge - of that first.

Hope it helps,
  Benjamin


On Wed, 15 Oct 2003 15:12:39 +0530, Shyam Prakash 
<ramakrishna.prakash at quest-global.com> wrote:

> 			Thanks a million. Your solution(proposed method
> #1) perfectly matches my requirements. The only challenge ahead of me
> right now is to find out the Kernel of the polygon as sometime my
> polygons may be concave. Do you know about the availability of such
> algorithm?
>
> Thanks and Regards
> Shyam
>
> -----Original Message-----
> From: vtkusers-admin at vtk.org [mailto:vtkusers-admin at vtk.org] On Behalf
> Of Benjamin King
> Sent: Tuesday, October 14, 2003 6:11 PM
> To: Shyam Prakash; vtkusers at vtk.org
> Subject: Re: [vtkusers] (no subject)
>
> Hello Shyam,
>
> I'll try to explain the method I proposed with more detail, so you can
> see if it's applicable for you.
>
> You are interested in the boundary of a closed polygon that is described
> by a set of points. The more you know about the possible forms of the
> polygon and about the distribution of the points, the easier it is to 
> find the solution.
>
> The proposed method generalizes as follows:
>
> 1) Find a point c from which all the polygon edges are visible. I think
> the set of all such points is called the kernel of that polygon, but I'm 
> not
>
> quite sure. For convex polygons it is easy to find - the whole area of
> the polygon is the kernel and the mean of all the points belongs to it. 
> It
> will also work for certain non-convex polygons like the bean shaped one 
> you mentioned or a star shaped one, but it may be harder to find a 
> suitable point because you don't know the edges of the polygon in 
> advance.
>
> 2) Sort the points with respect to the angle of the line segment between
>
> them and c and you're done.
>
> So my advice to you is to check if the polygons you want to find have a 
> non-empty kernel and if it is easy to find a point of the kernel with
> only the pointset you have.
>
> If that is not the case but your points are dense, you can also start
> with two sets of points, a connected set A (empty in the beginning) and 
> an unconnected set B (all remaining points). Move any point from B to A.
> And now iteratively seek the closest pair (a, b) with a in A and b in B, 
> connect them and move b to A until B is empty. As the last step you
> would have to connect the first and the last point.
>
> And if the points on the boundary of the polygon aren't even dense but
> you have only a few points, you can connect each one to every other one -
> form a 'clique' in graph theoretic terms - and try to find the shortest 
> path that visits each point expect for the first exactly once and the 
> first twice. Such a path is called a hamilton path (and the graph is 
> called hamiltonian) and it is computationally intensive to find. It can 
> still happen that this scheme finds a polygon that you don't expect, but 
> at
> least it won't intersect with itself.
>
> There may be other suitable methods for your problem, but you have to 
> specify it in more detail to find them.
>
>
> Hope that helps,
> Benjamin
>
>
>> Hello Benjamin,
>> 		Thanks for the reply. Sorry that I did not explain the
>> problem completely. The cross section whose perimeter I am trying to
>> determine may not be circle always. I doubt I can use the method you
>> mentioned for irregular cross section (for instance, consider a bean
>> shaped c/s). Please let me have your views.
>>
>> Thanks
>> Shyam
>>
>> -----Original Message-----
>> From: vtkusers-admin at vtk.org [mailto:vtkusers-admin at vtk.org] On Behalf
>> Of Benjamin King
>> Sent: Tuesday, October 14, 2003 3:01 PM
>> To: Shyam Prakash; vtkusers at vtk.org
>> Subject: Re: [vtkusers] (no subject)
>>
>> Hello Shyam,
>>
>> I'm not sure if there is a direct solution in VTK, but you could first
>> find another point c inside the circle (i.e. the mean of all the
> points
>> or
>> just the point at the top) and then build an array that associates
> each
>> pointid i with the angle of the line between c and i. If you sort that
>
>> array by
>> the angle values, you get a suitable sequence of point ids. This is
> also
>> a resonably fast way to do this because the time for the sort (O(n log
> n))
>>
>> will always dominate the time for creating the array (O(n)). And you
>> won't get away without sorting.
>> You could also use any convex hull algorithm, but I don't think
> vtkHull
>> will do.
>>
>> Hope it helps,
>> Benjamin
>>
>>> Hi,
>>> My output polydata represents a circle. The point ids on
>>> this poly data are distributed randomly(please refer the attached
>>> image). Is it possible to get the ordered points (for example if I
>> start
>>> with point id 0, then the preferred enumeration order will be
>>> 0 - 1 - 2 - 4 - 6 - 9 - 10 - 11 - 8 - 7 - 5 - 3 or in the
>> anticlockwise
>>> direction.
>>> The basic idea is to find the perimeter of the circle (i.e by
>> measuring
>>> the distance between set of points and finally adding all the
>> individual
>>> distances) . For this I need the points in the order of appearance.
>> Can
>>> you please suggest a way to achieve this.
>>> Thanks
>>> Shyam
>>>
>>
>>
>>
>
>
>