Re: Polygon-Polygon Intersection Test
- From: Ben C <spamspam@xxxxxxxxx>
- Date: 14 Mar 2006 21:28:35 GMT
On 2006-03-14, shu.miah@xxxxxxxxxxxxxx <shu.miah@xxxxxxxxxxxxxx> wrote:
After an extensive search and going through alot of material I've had
very little success.
I have a set of verticies of two simple polygons (which can be convex
[or concave]) and I wish to do a test to see whether the two polygons
intersect (i.e return a boolean value)...
I think it's quite easy.
It's no good to just have the vertices, because if the polygons can be
non-convex, a given set of vertices could be joined up in different ways
to make different polygons.
So you also need to know the edges to start with (i.e. which order to
join the vertices up in). Otherwise your problem is impossible.
The edges are line segments, so you have two sets of line segments, one
for each poly. If any line segment in one of the sets crosses any of the
line segments in the other set, then the polygons intersect. Otherwise
they don't.
So:
foreach a in A:
foreach b in B:
if a intersects b: return true
return false
is your basic program
Then all you have to worry about is how to intersect two linesegments,
which isn't too hard.
Some of the algorithms for convex polygons are more sophisticated,
basically because you can do some clever optimizations on this nested
loop based on the fact that they're convex.
.
- References:
- Polygon-Polygon Intersection Test
- From: shu . miah
- Polygon-Polygon Intersection Test
- Prev by Date: Re: Polygon-Polygon Intersection Test
- Next by Date: Weird 3D effect in my 2D screen
- Previous by thread: Re: Polygon-Polygon Intersection Test
- Next by thread: Searching for a freeware 3d plotter
- Index(es):
Relevant Pages
|
