A polygon consists of a list of points of arbitrary length. A point has an x, y and z value (All ints). Is there an algorithm to find if two polygons intersect?
I've gotten as far as assigning line objects to every side of the polygon, where a line has a start Point and an end Point. What now?
How much easier would it be to calculate if the polygons had a specified number of sides?
~Watercleave
Finding polygon intersection in 3d space
Moderators: phlip, Moderators General, Prelates

 Posts: 10
 Joined: Sat Aug 28, 2010 8:08 am UTC
 Robert'); DROP TABLE *;
 Posts: 730
 Joined: Mon Sep 08, 2008 6:46 pm UTC
 Location: in ur fieldz
Re: Finding polygon intersection in 3d space
You can do that by asking whether any of the points of the second polygon are inside the first, which means you don't have to keep track of lines between the points. However, this isn't simplified if you know the number of sides. Wikipedia has more.
...And that is how we know the Earth to be bananashaped.
 Toeofdoom
 The (Male) Skeleton Guitarist
 Posts: 3446
 Joined: Wed Jan 10, 2007 10:06 am UTC
 Location: Melbourne, Australia
 Contact:
Re: Finding polygon intersection in 3d space
It looks like you might have missed the bit about "3d space".
Anyway, in 3d you should be able to check if 2 triangles intersect, though I'm not going to go into the maths yet because it seems like you have a bigger problem (and I don't remember the maths): a list of more than 3 points doesn't necessarily define a single polygon in 3D space. If all the points are coplanar, no problem, just break them into a bunch of triangles. Otherwise you're going to need a better definition of your polygons (or maybe polygon isn't even the right word?)
Anyway, in 3d you should be able to check if 2 triangles intersect, though I'm not going to go into the maths yet because it seems like you have a bigger problem (and I don't remember the maths): a list of more than 3 points doesn't necessarily define a single polygon in 3D space. If all the points are coplanar, no problem, just break them into a bunch of triangles. Otherwise you're going to need a better definition of your polygons (or maybe polygon isn't even the right word?)
Hawknc wrote:Gotta love our political choices here  you can pick the unionised socially conservative party, or the freemarket even more socially conservative party. Oh who to vote for…I don't know, I think I'll just flip a coin and hope it explodes and kills me.
Website

 Posts: 167
 Joined: Tue Jan 20, 2009 12:02 pm UTC
 Location: trapped in a profile factory please send help
Re: Finding polygon intersection in 3d space
Toeofdoom wrote:It looks like you might have missed the bit about "3d space".
Anyway, in 3d you should be able to check if 2 triangles intersect, though I'm not going to go into the maths yet because it seems like you have a bigger problem (and I don't remember the maths): a list of more than 3 points doesn't necessarily define a single polygon in 3D space. If all the points are coplanar, no problem, just break them into a bunch of triangles. Otherwise you're going to need a better definition of your polygons (or maybe polygon isn't even the right word?)
Terminology: A vertex is a point somewhere in 3D space. A line joins two vertices. Those lines mark the edges of a 2D surface called a polygon (e.g. a triangle, a square). Several polygons combine to form a 3D object.

 Posts: 10
 Joined: Sat Aug 28, 2010 8:08 am UTC
Re: Finding polygon intersection in 3d space
I've figured out a solution of sorts, but it would probably be very slow:
Define every polygon on a twodimensional plane. Also give it three angles, by which it is rotated in 3d pace to find its actual position.
Given two polygons:
 Find every line in polygon 1.
 For each line:
* Rotate it through the reverse of the rotation on polygon 2.
* Find the vertex where the line intersects polygon 2's plane.
* Steal the Java.awt.Polygon contains(Point p) function and use it to check if the vertex is within the polygon.
* If it is, return true. If not, repeat for all lines.
 Repeat for polygon 2
~Watercleave
Define every polygon on a twodimensional plane. Also give it three angles, by which it is rotated in 3d pace to find its actual position.
Given two polygons:
 Find every line in polygon 1.
 For each line:
* Rotate it through the reverse of the rotation on polygon 2.
* Find the vertex where the line intersects polygon 2's plane.
* Steal the Java.awt.Polygon contains(Point p) function and use it to check if the vertex is within the polygon.
* If it is, return true. If not, repeat for all lines.
 Repeat for polygon 2
~Watercleave
 Toeofdoom
 The (Male) Skeleton Guitarist
 Posts: 3446
 Joined: Wed Jan 10, 2007 10:06 am UTC
 Location: Melbourne, Australia
 Contact:
Re: Finding polygon intersection in 3d space
Axidos wrote:Terminology: A vertex is a point somewhere in 3D space. A line joins two vertices. Those lines mark the edges of a 2D surface called a polygon (e.g. a triangle, a square). Several polygons combine to form a 3D object.
Cool, confirmation that polygons are 2D?
That algorithm does sound kinda slow, but if it works that might not be a problem. Anyway, I think the fastest way might be to use something like this: http://www.cgafaq.info/wiki/Triangle_Tr ... tersection (that paper is http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf if you really want it)
Essentially the algorithm goes like this:
1. For each polygon, check if all of its points are on the same side of the plane that the other polygon lies on. If so, there's no intersection  return false.
2. Find the line of intersection of the 2 planes defined by the polygons.
3. If it enters either polygon, your polygons intersect, return true. Else, return false.
For more general stuff about planes and polygons: http://en.wikipedia.org/wiki/Plane_(geometry)
Hawknc wrote:Gotta love our political choices here  you can pick the unionised socially conservative party, or the freemarket even more socially conservative party. Oh who to vote for…I don't know, I think I'll just flip a coin and hope it explodes and kills me.
Website

 Posts: 167
 Joined: Tue Jan 20, 2009 12:02 pm UTC
 Location: trapped in a profile factory please send help
Re: Finding polygon intersection in 3d space
Toeofdoom wrote:Axidos wrote:Terminology: A vertex is a point somewhere in 3D space. A line joins two vertices. Those lines mark the edges of a 2D surface called a polygon (e.g. a triangle, a square). Several polygons combine to form a 3D object.
Cool, confirmation that polygons are 2D?
In various fields of geometry they might not be. In 3D modelling where all things (objects) are expressed as a combination of surfaces created by joining points, polygons are those surfaces. Granted, you can warp a polygon so it's not strictly 2D, even though in a lot of cases it would still have zero depth like a 2D object should.
Who is online
Users browsing this forum: No registered users and 8 guests