A great big mathematical and algorithmical problem for you all

General Discussions
#1

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 :slight_smile:

#2

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).

#3

A nice method, but if I understand right that doesn’t get you the smallest convex hull.

http://www.triangularpixels.com/Junk/Hull.png

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

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.

#4

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
[/quote]
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.

#5

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 :slight_smile:

#6

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.

#7

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

What does “includes” mean here? It doesn’t seem to be “contains”.

#8

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

#9

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 :slight_smile:

#10

{snip rambling}

#11

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.
  2. Go to 1. for each new line
  3. Render the remaining triangles into your surface.

#12

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.

#13

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.

#14

My apologies, the question was directed more to cas’s current approach

#15

I didn’t exactly want to make you feel like you had to apologize :slight_smile:

#16

I’m just… so sensitive :’(

:wink: 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.

http://homepages.inf.ed.ac.uk/rmcnally/intersect/intersect2.png

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.

#17

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 :slight_smile:

#18

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.