Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (575) Games in Android Showcase (154) games submitted by our members Games in WIP (623) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 A great big mathematical and algorithmical problem for you all  (Read 4119 times) 0 Members and 1 Guest are viewing this topic.
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Posted 2009-02-19 11:35:50 »

I have between 3 and 6 lines (inclusive), which exist on a 2D plane. They are represented as an origin and normal (these are mathematical lines, not segments).

I would like to know the smallest convex polygon that they form which includes all the intersections (not all lines will intersect - there may be parallel lines but at least 3 lines will not be parallel) when each line is intersected with the others, and I need to know the order of the points in the polygon to ensure it is indeed convex (ie. 6 arbitrary points will either yield me a star of David or a hexagon - I want a hexagon).

Any takers?

Cas

pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #1 - Posted 2009-02-19 12:16:38 »

I assume you can calculate the intersection of two lines. Given that the problem specifies there are scarcely any of them it's probably sensible to ignore complexity analysis and just intersect them pairwise to get the set of points you're interested in.

Then all you're asking for is the convex hull of that set of points. There are plenty of standard algorithms to find it. Google qhull for one implementation (not sure offhand whether Java code is included).
Orangy Tang

JGO Kernel

Medals: 57
Projects: 11

Monkey for a head

 « Reply #2 - Posted 2009-02-19 13:03:09 »

I assume you can calculate the intersection of two lines. Given that the problem specifies there are scarcely any of them it's probably sensible to ignore complexity analysis and just intersect them pairwise to get the set of points you're interested in.

Then all you're asking for is the convex hull of that set of points. There are plenty of standard algorithms to find it. Google qhull for one implementation (not sure offhand whether Java code is included).
A nice method, but if I understand right that doesn't get you the smallest convex hull.

Your method will give A+B, but I think Cas is after just B. Would have been my first attempt too.

Cas, you may want to check out the Java Topography Suite, I'm using it for my map editor and it's very full featured and seems quick enough (although I've not used it in a game directly). I think you can get what you want by "noding" your lines (see bottom of the developer guide), then polygonising the result. That'll return both A and B and you'll have to go through and find the one with the smallest area.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
 Games published by our own members! Check 'em out!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #3 - Posted 2009-02-19 13:13:11 »

Your method will give A+B, but I think Cas is after just B. Would have been my first attempt too.

but B doesn't include all intersections, indeed even A+B is incorrect. From the problem description:
Quote
smallest convex polygon that they form which includes all the intersections

I can't see how that isn't just the convex hull. On the other hand, I'm doubtfull that Cas couldn't work this out on his own, so there may be more to the problem than stated.
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #4 - Posted 2009-02-19 13:17:22 »

I've narrowed down the problem a little more now, close to a real solution to it.

If I can determine that there is one side of each line which is "outside" the desired polygon, then from the cloud of points that is the intersection of each line with every other line, I can discard each point which falls in the "outside" region of each line.

This will produce only the set of 3-6 points that will be present in the final polygon.

The problem then is one of determining the order that these points should be presented. I think that given any point I should be able to then select the other point on that line, rinse, and repeat, and end up with a convex polygon.

So:
this all hinges on the plane-plane intersection I am using producing lines that can reliably be determined to have an "in front of" and "behind".

Cas

ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #5 - Posted 2009-02-19 14:20:04 »

I think I've got a better idea of your problem now.

As I see it - you're after the inverse of the convex hull - the largest polygon that doesn't contain any other point, rather than the smallest that does contains every other point. You also got the hexagon requirement.

It's probably worth checking that you can't just brute-force it : calculate the 6-subsets of the intersections, generate the convex hull of those points, check that it's a hexagon, check for point inclusion, choose the largest.

If that's a no-go (probable, there's a maximum of 21!/(15!*6!) = 54264 subsets to check) you can start being clever about choosing the six points: the six nearest the average of the intersections, the six nearest the line origins (if the line origins have any bearing on the desired output) etc

Alternatively, I'm pretty sure the Delaunay triangulation would be handy. Your desired output is the result of choosing an interior triangle and using its 3 neighbours to form a hexagon, so you'd have to check a maximum of 40 - 2*convexHullVertexCount triangles to see if the resulting hexagon is convex and choose the largest.

edit: actually, it isn't necessarily one triangle's three neighbours, so you'd have to check sets of 4 adjacent triangles.
pjt33

« JGO Spiffy Duke »

Medals: 40
Projects: 4
Exp: 7 years

 « Reply #6 - Posted 2009-02-19 15:03:28 »

Ok, I'm now completely confused about what you actually want.

I would like to know the smallest convex polygon that they form which includes all the intersections (not all lines will intersect - there may be parallel lines but at least 3 lines will not be parallel) when each line is intersected with the others, and I need to know the order of the points in the polygon to ensure it is indeed convex (ie. 6 arbitrary points will either yield me a star of David or a hexagon - I want a hexagon).

What does "includes" mean here? It doesn't seem to be "contains".
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #7 - Posted 2009-02-19 15:08:42 »

So:
this all hinges on the plane-plane intersection I am using producing lines that can reliably be determined to have an "in front of" and "behind".

For this, could you just take the side on which the majority of the intersection points lie to be the inside?
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #8 - Posted 2009-02-19 16:52:15 »

Probably could yes.

A bit more background to the problem:

I have a viewing frustum, made of 6 planes that make a truncated pyramid, which I have extracted from a projection view matrix and modelview matrix. I am intersecting this frustum with the ground plane (0, 0, 1, 0) in order to find the convex polygon that this intersection produces, which will either be a triangle, a quadrilateral, or possibly in some freaky cases, a pentagon or hexagon.

I will then quantize the coordinates of the polygon to the low resolution scale I desire, and then rasterize the resulting coordinates to get a bitmap. This bitmap will tell me the coordinates of the tiles I can see, without needing to a) have any data loaded or b) use any spatial partitioning tree.

Cas

Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #9 - Posted 2009-02-19 17:37:24 »

{snip rambling}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
 Games published by our own members! Check 'em out!
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #10 - Posted 2009-02-19 18:41:12 »

Another idea...

Your normals must be either clockwise of counter-clockwise to determine which side of the lines need to be culled.
Use the dot-product to determine whether any point is on the right or wrong side of the line.

Create a huge triangle, which is known to hold the entire area.

Now slice off parts of it, with your infinite lines.
1. Take the (set of) triangle(s), and determine whether there are intersections with the infinite line.
2a. If so, split the triangle, into 2 parts. The remaining shape might be a quad now, of so, split that into 2 triangles.
2b. If not, either keep the entire triangle, or remove it, depending on on which side of the line it is.
3. Go to 1. for each new line
4. Render the remaining triangles into your surface.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #11 - Posted 2009-02-19 18:47:40 »

Isn't it easier to calculate the frustum vertices (8 plane-plane intersection + 8 line-line intersections) and then get the intersections of the frustum's edges against the ground plane (12 lerps with easy quick rejection) to get the view polygon vertices?

edit: You can also exploit the frustum to find the vertices in order by traversing the edge-face graph - see attached code
edit2: actually tested the code this time
edit3: removed broken code - see below for working version

At the moment you're looking at 6 plane-plane intersections and 15 line-line intersections to generate the point cloud, and then unspecified amounts of other work to find the correct vertices.
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #12 - Posted 2009-02-19 19:03:24 »

In my algorithm, there is no point-cloud, so there is no unspecified amount of work anymore.

You end up with N non-intersecting triangles, that combined, make a concave convex shape.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #13 - Posted 2009-02-19 19:29:54 »

My apologies, the question was directed more to cas's current approach
Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #14 - Posted 2009-02-19 21:35:36 »

I didn't exactly want to make you feel like you had to apologize

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
ryanm

Senior Devvie

Projects: 1
Exp: 15 years

Used to be bleb

 « Reply #15 - Posted 2009-02-20 08:14:50 »

I'm just... so sensitive

Nah, I should have quoted Princec, instead my post appeared to be addressing yours without any indication that I'd actually read it.

edit: OK, I'm prepared to call this a thing of beauty now.

Code is over there - it just needs the verts to be set as required, which'll take 8 plane-plane-plane intersections. edit: which I've just implemented. I think we can cut this problem's arm off and nail it to the wall.

In summary - construct a Box object and each frame call setVertsFromPlanes( frustum plane points and normals ), then use findZIntersection( z value ) to get an ordered list of intersection vertices. I can't guarantee if it's anticlockwise or clockwise order, but that's a dot-product away if you need to know.
princec

« JGO Spiffy Duke »

Medals: 495
Projects: 3
Exp: 16 years

Eh? Who? What? ... Me?

 « Reply #16 - Posted 2009-02-20 10:41:29 »

Solved it I think - I can just run my cloud of points through the frustum to see which ones are inside or outside. Possibly a tiny bit less clever or mathematically efficient but very very easy to understand. I'll be left with 3-6 points which I can very trivially turn into a convex polygon.

I'll post the code at some point in Shared Code as it's pretty handy stuff for "infinite terrain" without the use of quadtrees.

Cas

Riven
« League of Dukes »

« JGO Overlord »

Medals: 954
Projects: 4
Exp: 16 years

 « Reply #17 - Posted 2009-02-20 20:39:47 »

It just occured to me, that if one of the frustum planes doesn't intersect the groundplane (like when the top-plane is pointing towards the sky), the convex shape around the point-cloud will not be equal to the area in view (because you are missing ground-plane intersections). The furthest intersection-points will be much nearer than the 'infinite' hits in the ground-plane that the up-plane would cause.

With my algorithm, which is not based on a point-cloud, you'll just clip an infinite area with lines, which yields the correct area, even if not all planes intersect the ground plane.

If you're culling in a (more or less) top-down game, this is not a problem ofcourse.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 ClaasJG (17 views) 2015-04-27 13:36:51 BurntPizza (32 views) 2015-04-23 03:42:11 theagentd (35 views) 2015-04-22 16:23:07 Riven (50 views) 2015-04-16 10:48:47 Duke0200 (59 views) 2015-04-16 01:59:01 Fairy Tailz (42 views) 2015-04-14 20:13:12 Riven (45 views) 2015-04-12 21:36:37 bus hotdog (61 views) 2015-04-10 02:39:32 CopyableCougar4 (66 views) 2015-04-10 00:51:04 BurntPizza (71 views) 2015-04-06 22:06:58
 theagentd 23x BurntPizza 17x wessles 15x alwex 11x 65K 11x kingroka123 11x kevglass 8x Olo 7x Ecumene 7x ra4king 7x Rayvolution 7x Riven 7x chrislo27 7x Hanksha 7x KevinWorkman 6x thedanisaur 4x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org