Re: Novice 2D question: How to find points in a convex hull/polygon in a 2D grid (including points on the border) ?
- From: "Wessam Bahnassi" <wbahnassi@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Sat, 9 Apr 2005 08:48:04 +0300
Not DX related, but perhaps a normal polygon rasterizing algorithm can do
the job?
Wessam Bahnassi
Microsoft DirectX MVP,
Lead Programmer
In|Framez
<aredo3604gif@xxxxxxxxx> wrote in message
news:limd51lpaakrfmh7ii6fea5sqvnskqnsvo@xxxxxxxxxx
>I don't have knowledge of texturing and 3D algorithms but I have to
> solve an issue for a program.
> On a integer coordinates 2D grid world I have to determine which
> points lie inside a convex hull/polygon. The convex hull vertex lists
> is given and already known in clockwise order.
> Now, I looked at Andrew, QuickHull, Graham Scan and such but I
> couldn't find any example to reverse the problem. Graham Scan actually
> checks all the points in a set to find the convex hull but I already
> got the convex hull and what I need is a way to do the reverse that
> Graham Scan does. I need to build up a list of elements inside the
> convex hull that lie on 2D grid points and their maximum number (the
> area made of 2D grid points in practice) including those that lie on
> the convex hull border (between any two vertices of the convex hull
> the 2D grid points that lie on the line joining them).
> I thought about the fact that if Graham Scan could be inverted it
> would automatically give me the number of maximum elements that could
> be contained within the convex hull as well as the list of of them,
> right ? But I couldn't find any example, not even pseucode ones to
> invert Graham Scan to obtain what I need.
>
> I tried using a cross-product approach by scanning the minimum
> rectangle of 2D grid points enclosing the convex polygon:
> E = vertex[i+1] - vertex[i]
> V = P - vertex[i]
> S = sign of (E x V)
>
> with S that should be 0 if it's on the border, and changes from -1 to
> +1 (negative to positive or viceversa) if it's outside the polygon,
> otherwise if the sign doesn't change it's inside it,right?
>
> ...but whenever I have an edge, a border line, that's aligned
> vertically or horizontally to the grid any test involving vertices
> from that edge to the point gives wrong results, with S=0 when a point
> it's not on the border as well as misdetecting vertices themselves.
> Why doesn't cross-product work ? Is the implementation wrong ? And if
> yes, what's the correct one to ensure proper detection of point
> inside/outside/on border ?
>
> What should I use ? Dot product instead ? Or any better approach? I
> need to detect grid points on the boundary of the polygon/convex hull
> (which means adding the vertices themselves to the list of points
> inside it/on the border)
>
>
> Could anyone please help me about how to solve this ?
> Thanks.
.
- References:
- Prev by Date: Re: Update to 2005 April Runtime application problem
- Next by Date: Re: Update to 2005 April Runtime application problem
- Previous by thread: Re: Novice 2D question: How to find points in a convex hull/polygon in a 2D grid (including points on the border) ?
- Next by thread: How to calculate the size of the surface?
- Index(es):
Relevant Pages
|
