Re: Re: Interior of a polygon
- To: mathgroup at smc.vnet.net
- Subject: [mg28604] Re: [mg28578] Re: Interior of a polygon
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Tue, 1 May 2001 00:17:30 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
on 01.5.1 0:02 AM, David Terr at dterr at wolfram.com wrote:
> Andrzej Kozlowski wrote:
>
>> Well, yes but we all know this. This was discussed on this list in detail
>> last year, and exactly the same method was described by a number of
>> different people. But this was not the point of the question this time. THe
>> point was to find all the points which have integer coordinates which lie
>> inside. Your suggestion simply gives the most obvious and probably
>> inefficient method which I referred to as "brute force" and which Mariusz
>> Jankowski (who asked the original question) had known about already before
>> he sent his message to the mathgroup.
>>
>> Andrzej
>>
>> on 01.4.28 8:47 AM, DennisW555 at dennisw555 at aol.com wrote:
>>
>>> To find if a point is inside a polygon simply start at one vertex and
>>> accumulate the angles from the point to each sucessive vertex, all the way
>>> around to that starting vertex. Keep track of the sense, as some will be
>>> negative angles and some positive. If the magnitude of the sum of angles is
>>> 2
>>> Pi the point is inside. If the sum is zero the point is outside. I set the
>>> decision threshold at Pi for simplicity. With this method the polygon does
>>> not
>>> need to be convex. I pretend the polygon points are in the xy plane and
>>> take
>>> cross products between successive vectors from the point to the vertex.
>>> Then
>>> the magnitude of the sum of the z components of the cross products is the
>>> quantity to test. To do this a vertex at coordinates {x,y} becomes {x,y,0},
>>> likewise for the point.
>>>
>>> I hope this helps,
>>>
>>> Dennis Wangsness
>>>
>>
>> --
>> Andrzej Kozlowski
>> Toyama International University
>> JAPAN
>>
>> http://platon.c.u-tokyo.ac.jp/andrzej/
>> http://sigma.tuins.ac.jp/
>
> To find the set of all points inside a polygon or any region is no easy matter
> since there are infintely many. How would you represent the collection of all
> such
> points? The simplest way to do this is to return the interior of the polygon
> itself, but since you're starting with the polygon, this begs the question.
> Thus I
> don't think there's any simple answer to your question.
>
> David
>
>
We are assuming that the polygon is compact (of course!). The problem is not
to find the set of all points inside the polygon, which would be impossible,
but only to find the points which have integer coordinates. THere are only
finitely many such points. To do so is actually "a simple matter", the only
difficulty is to do so in an efficient tmanner.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/