Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Reelya]

If you're doing any sort of complex scenework in 3D however, it's extremely unlikely your homebrew OpenGL 3D engine is going to be as efficient as existing engines however.

[Gatleos]

Hmmm... I got my own implementation of quadtrees working, and it successfully reduced the number of collision comparisons to 0.166 what it was before, using about 3.50% of my (quad-core) CPU while moving around and drawing 1000 AABBs at 60fps. But one of the code examples I looked at looks like this:

Code: [Select]

public List retrieve(List returnObjects, Rectangle pRect) {
   int index = getIndex(pRect);
   if (index != -1 && nodes[0] != null) {
     nodes[index].retrieve(returnObjects, pRect);
   }
 
   returnObjects.addAll(objects);
 
   return returnObjects;
 }
This function returns a list of objects that the given rect could potentially be intersecting. When getIndex returns -1, it means the given rect doesn't fit within one of the child nodes, so must be placed within the current one. The problem I found with this function is that it's not symmetrical. Say two collision rectangles are added to the quadtree, and one is placed into one of the child nodes as it fits entirely within one quadrant. But the other is halfway between two of the quadrants, so it gets placed in the parent node. Using the function above, the former will register as colliding with the latter, but not vice versa.

I can't even tell if that's intended behavior here.

[MagmaMcFry]

Hmmm... I got my own implementation of quadtrees working, and it successfully reduced the number of collision comparisons to 0.166 what it was before, using about 3.50% of my (quad-core) CPU while moving around and drawing 1000 AABBs at 60fps. But one of the code examples I looked at looks like this:

Code: [Select]

public List retrieve(List returnObjects, Rectangle pRect) {
   int index = getIndex(pRect);
   if (index != -1 && nodes[0] != null) {
     nodes[index].retrieve(returnObjects, pRect);
   }
 
   returnObjects.addAll(objects);
 
   return returnObjects;
 }
This function returns a list of objects that the given rect could potentially be intersecting. When getIndex returns -1, it means the given rect doesn't fit within one of the child nodes, so must be placed within the current one. The problem I found with this function is that it's not symmetrical. Say two collision rectangles are added to the quadtree, and one is placed into one of the child nodes as it fits entirely within one quadrant. But the other is halfway between two of the quadrants, so it gets placed in the parent node. Using the function above, the former will register as colliding with the latter, but not vice versa.

I can't even tell if that's intended behavior here.

When searching a space partitioning tree for things that collide with an object, you need to look not only at the object node's parent nodes, but also at its child nodes.

[Gatleos]

Yeah, I think the implementation I used as an example is just flawed. I'm going to look at a few more examples of quadtree classes and change that retrieval function up a bit.

[RoguelikeRazuka]

Hey I need to write a program for solving a linear programming (optimization) problem using the graphical method. This boils down to solving a system of linear inequations of two variables by graphing -- that is the area of the points which coordinates satisfy each of the inequations is to be determined.

Supose I have found the points of intersection of the lines that confine the area. How do I identify which one of those points is the point where the objective function reaches its maximum or minimum? It also can be that there is either no maximum or no minimum, or both no maximum and no minimum.

[TheBiggerFish]

Hey I need to write a program for solving a linear programming (optimization) problem using the graphical method. This boils down to solving a system of linear inequations of two variables by graphing -- that is the area of the points which coordinates satisfy each of the inequations is to be determined.

Supose I have found the points of intersection of the lines that confine the area. How do I identify which one of those points is the point where the objective function reaches its maximum or minimum? It also can be that there is either no maximum or no minimum, or both no maximum and no minimum.

That's a Math Help Thread problem, methinks.

[RoguelikeRazuka]

Hey I need to write a program for solving a linear programming (optimization) problem using the graphical method. This boils down to solving a system of linear inequations of two variables by graphing -- that is the area of the points which coordinates satisfy each of the inequations is to be determined.

Supose I have found the points of intersection of the lines that confine the area. How do I identify which one of those points is the point where the objective function reaches its maximum or minimum? It also can be that there is either no maximum or no minimum, or both no maximum and no minimum.

That's a Math Help Thread problem, methinks.

No-no-no, I do know how to do it using a sheet of paper and a pencil. But how to program it?

[TheBiggerFish]

Hey I need to write a program for solving a linear programming (optimization) problem using the graphical method. This boils down to solving a system of linear inequations of two variables by graphing -- that is the area of the points which coordinates satisfy each of the inequations is to be determined.

Supose I have found the points of intersection of the lines that confine the area. How do I identify which one of those points is the point where the objective function reaches its maximum or minimum? It also can be that there is either no maximum or no minimum, or both no maximum and no minimum.

That's a Math Help Thread problem, methinks.

No-no-no, I do know how to do it using a sheet of paper and a pencil. But how to program it?

Plug in the values, see if they are defined on the function.
At least, I thought of doing it that way.
But where's your problem in transitioning from paper and pencil to computerized?

[RoguelikeRazuka]

Hey I need to write a program for solving a linear programming (optimization) problem using the graphical method. This boils down to solving a system of linear inequations of two variables by graphing -- that is the area of the points which coordinates satisfy each of the inequations is to be determined.

Supose I have found the points of intersection of the lines that confine the area. How do I identify which one of those points is the point where the objective function reaches its maximum or minimum? It also can be that there is either no maximum or no minimum, or both no maximum and no minimum.

That's a Math Help Thread problem, methinks.

No-no-no, I do know how to do it using a sheet of paper and a pencil. But how to program it?

Plug in the values, see if they are defined on the function.
At least, I thought of doing it that way.
But where's your problem in transitioning from paper and pencil to computerized?

Suppose we have n constraints (n lines) and less-than-n points of their intersection with one another. That means the area is unbounded in the direction of the gradient of the objective function. How do I find it out not knowing how the polygon (which is shaped by the area) looks like?

[Reelya]

To graph the region you need what's called a clipping algorithm to make the polygon. Possible steps would be :-

- calculate the set of all intersection points. (trivial)
- work out the smallest rectangle that holds all of the points, keep it aligned to the axes (trivial)
- feed this rectangle and your lines into a clipping algorithm of your choice. (not very hard).
- use your chosen  graphics library to render the polygon created in the last step with a fill color (trivial)

For calculating the optimal points, it's actually hard to answer that because we don't know what sorts of functions you're trying to solve. If you have differentiable functions however (partial derivatives for two or more variables), you can use Newton's Method or Gradient Descent to iteratively generate approximate solutions for your function.
https://en.wikipedia.org/wiki/Newton's_method
https://en.wikipedia.org/wiki/Gradient_descent
They're similar but a little different in the formula used to generate the next approximation.

[RoguelikeRazuka]

To graph the region you need what's called a clipping algorithm to make the polygon. Possible steps would be :-

- calculate the set of all intersection points. (trivial)
- work out the smallest rectangle that holds all of the points, keep it aligned to the axes (trivial)
- feed this rectangle and your lines into a clipping algorithm of your choice. (not very hard).
- use your chosen  graphics library to render the polygon created in the last step with a fill color (trivial)

For calculating the optimal points, it's actually hard to answer that because we don't know what sorts of functions you're trying to solve. If you have differentiable functions however (partial derivatives for two or more variables), you can use Newton's Method or Gradient Descent to iteratively generate approximate solutions for your function.
https://en.wikipedia.org/wiki/Newton's_method
https://en.wikipedia.org/wiki/Gradient_descent
They're similar but a little different in the formula used to generate the next approximation.

The objective funtion is linear, each of the constraints is linear too.

[TheBiggerFish]

To graph the region you need what's called a clipping algorithm to make the polygon. Possible steps would be :-

- calculate the set of all intersection points. (trivial)
- work out the smallest rectangle that holds all of the points, keep it aligned to the axes (trivial)
- feed this rectangle and your lines into a clipping algorithm of your choice. (not very hard).
- use your chosen  graphics library to render the polygon created in the last step with a fill color (trivial)

For calculating the optimal points, it's actually hard to answer that because we don't know what sorts of functions you're trying to solve. If you have differentiable functions however (partial derivatives for two or more variables), you can use Newton's Method or Gradient Descent to iteratively generate approximate solutions for your function.
https://en.wikipedia.org/wiki/Newton's_method
https://en.wikipedia.org/wiki/Gradient_descent
They're similar but a little different in the formula used to generate the next approximation.

Interesting. And what if there's no 'smallest rectangle that holds all of the points'?

There always is?

[Reelya]

To graph the region you need what's called a clipping algorithm to make the polygon. Possible steps would be :-

- calculate the set of all intersection points. (trivial)
- work out the smallest rectangle that holds all of the points, keep it aligned to the axes (trivial)
- feed this rectangle and your lines into a clipping algorithm of your choice. (not very hard).
- use your chosen  graphics library to render the polygon created in the last step with a fill color (trivial)

For calculating the optimal points, it's actually hard to answer that because we don't know what sorts of functions you're trying to solve. If you have differentiable functions however (partial derivatives for two or more variables), you can use Newton's Method or Gradient Descent to iteratively generate approximate solutions for your function.
https://en.wikipedia.org/wiki/Newton's_method
https://en.wikipedia.org/wiki/Gradient_descent
They're similar but a little different in the formula used to generate the next approximation.

The objective funtion is linear, each of the constraints is linear too.

If the objective function is linear, then just compute that function at each intersection point. It'll be higher or lower at one of them, and you can forget the points in the middle. If there is actually an unbounded edge, well you need to make a bound for your drawing, because finite size of graph.

[MagmaMcFry]

Supose I have found the points of intersection of the lines that confine the area. How do I identify which one of those points is the point where the objective function reaches its maximum or minimum? It also can be that there is either no maximum or no minimum, or both no maximum and no minimum.

Suppose we have n constraints (n lines) and less-than-n points of their intersection with one another. That means the area is unbounded in the direction of the gradient of the objective function. How do I find it out not knowing how the polygon (which is shaped by the area) looks like?

To find a potential maximum, just evaluate the objective function f at all intersections of two lines and take the intersection P with the highest objective value f(P) such that P still fulfills all inequalities. To determine whether that point is actually maximal, take the line {Q : f(Q) = f(P) + 1} and intersect it with all the given boundary lines. If none of the resulting points is valid, then P is indeed maximal, otherwise P is not maximal.

[RoguelikeRazuka]

To graph the region you need what's called a clipping algorithm to make the polygon. Possible steps would be :-

- calculate the set of all intersection points. (trivial)
- work out the smallest rectangle that holds all of the points, keep it aligned to the axes (trivial)
- feed this rectangle and your lines into a clipping algorithm of your choice. (not very hard).
- use your chosen  graphics library to render the polygon created in the last step with a fill color (trivial)

For calculating the optimal points, it's actually hard to answer that because we don't know what sorts of functions you're trying to solve. If you have differentiable functions however (partial derivatives for two or more variables), you can use Newton's Method or Gradient Descent to iteratively generate approximate solutions for your function.
https://en.wikipedia.org/wiki/Newton's_method
https://en.wikipedia.org/wiki/Gradient_descent
They're similar but a little different in the formula used to generate the next approximation.

Interesting. And what if there's no 'smallest rectangle that holds all of the points'?

There always is?

Nevermind.

Actually I don't necessarily need to graph the region and fill it with colour; I think just showing all the lines would be enough. But to get the answer to whether there is an optimum and if there is one which it is (an objective function may reach it at one point or at all of the points of a line) is necessary.