Finding polygon intersection in 3d space

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Watercleave
Posts: 10
Joined: Sat Aug 28, 2010 8:08 am UTC

Finding polygon intersection in 3d space

Postby Watercleave » Sun Sep 19, 2010 2:40 pm UTC

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

User avatar
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

Postby Robert'); DROP TABLE *; » Sun Sep 19, 2010 4:01 pm UTC

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 banana-shaped.

User avatar
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

Postby Toeofdoom » Mon Sep 20, 2010 7:33 am UTC

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?)
Hawknc wrote:Gotta love our political choices here - you can pick the unionised socially conservative party, or the free-market 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

Axidos
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

Postby Axidos » Mon Sep 20, 2010 9:21 am UTC

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.

Watercleave
Posts: 10
Joined: Sat Aug 28, 2010 8:08 am UTC

Re: Finding polygon intersection in 3d space

Postby Watercleave » Mon Sep 20, 2010 1:40 pm UTC

I've figured out a solution of sorts, but it would probably be very slow:

Define every polygon on a two-dimensional 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

User avatar
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

Postby Toeofdoom » Mon Sep 20, 2010 3:45 pm UTC

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 free-market 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

Axidos
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

Postby Axidos » Mon Sep 20, 2010 4:06 pm UTC

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.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests