Print

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

[Reelya]

If you add an outer clipping box, then you can create a polygon that's constrained. Then, check the function at each point like normal. If the maximum or minimum occur on the outer points (the ones bounded by the "fake" constraint) you can therefore prove that there's no max or no min. Because if there is a max or min it MUST occur at one of the valid intersections (since the objective function is linear this must be true).

[RoguelikeRazuka]

here:

Spoiler (click to show/hide)

One point in that picture is a min. The second one is kind of maximal, but it is not really true though the value of the objective funtiction at that point is greater than at the other since the area is unbounded (it's not a maximum for another reason, but no matter). How do I overcome this (sorry for my poor paint skills)?

[Reelya]

I explained that in my last post. if you put other edge constraints around the entire space then any maximum that's on the outer box means there's no maximum in the proper space. Basically because if you can find a higher value anywhere that's still within the inequality space but is not one of the existing points, you can prove there's no actual maximum. (this is always logically true, but only if the objective function is linear)

Adding an outer clipping box does that in a single step and helps with the rendering too.

[RoguelikeRazuka]

I'm so sorry I don't think I fully understand what you mean by the 'outer box'.

Here's my vision:

Spoiler (click to show/hide)

Did I get you right?

[Reelya]

Sorry you're not even following in the slightest. The additonal intersection you've just added is parallel to the gradient, therefore it has the same function value as the existing intersection on the same line, and will tell you exactly nothing.

This is the third time I'm trying to tell you something really simple. Put a box around the entire graph. A box is a square BTW, or a rectangle.

Clip everything outside that away. find the intersection points of your inequality space and the big box. If any of those points is a higher maximum than the normal points, you know there's no actual maximum.

[RoguelikeRazuka]

Uhm is it a bit closer to the point this time?

Spoiler (click to show/hide)

[Lightningfalcon]

So do I use function pointers in a struct?
For my project, I have an array of  Object structs, which has a union that can hold one of several different shapes, each of which has a different intersect function associated with it. What I plan on doing is setting a function pointer intersect to the required intersect funciton at initialization. However, for whatever reason, at compile time, I just get a solid wall of errors thrown at me. Current set up for pointer and how I set it at initialization is here-
 int (*intersect)(RAY_T, OBJ_T, VP_T, VP_T, double);
 obj[0].intersect = &sphereIntersect;
Note that intersect is set in OBJ_T, and has OBJ_T as one of the variables.

[Reelya]

@Lightningfalcon: You can do that or you can use polymorphism. They'd be almost identical in terms of function and performance, but polymorphism would be much cleaner, because you could do away with both the function pointers and the union, making adding new shapes easier and cleaner... It's not clear what is wrong with your code because you haven't provided enough information to tell us anything. Maybe do a pastebin dump of the relevant code?

@RoguelikeRazuka: you have the right idea now. When you work out where your inequality space intersects with that large box, you can check for values higher than your normal max or lower than your normal min values. if you find such values, then that means some points were more extreme than the normal, existing intersections, therefore none of the actual points is the maximum or minimum (clearly obvious since the values are linear: if they're getting bigger as you go along a line that goes to infinity, then they must keep increasing past that point)

[Reelya]

Return a struct. Problem solved. You need a struct with three values of low, high and sum.

Having the correct values of the structs shouldn't be a problem. You pass everything by value so that each level of recursion has it's own copies of the structs and it won't be an issue.

[Reelya]

I use structs for just clumping some values together when they're not really a complex object. That way, I reserve classes for things which are actually objects and not e.g. just some intermediate values that got passed back from a function or a bunch of settings. Also, say you have a world location in a game. You might have a lot of objects which deal with the concept of a "location" so you bundle them into a class. but is "my location" really an object? Usually I just make that a struct for that reason.

Anyway here's the algorithm you asked for written in C++ dialect. You'll notice that by creating an appropriate data structure, I was able to keep it nearly identical on a line-by-line basis:

Code: [Select]

struct Data // generic "Data" name because I don't actually know what it's for!
{
int low, high, sum;
Data(int _low, int _high, int _sum) : low(_low), high(_high), sum(_sum) {} // constructor so we can create the structs inline
}

Data FMS(int A[], int low, int high)
{
if (high == low)
return Data(low, high, A[low]);
else
{
int mid = (low + high) / 2;
Data left = FMS(A, low, mid);
Data right = FMS(A, mid + 1, high);
Data cross = FMCS(A, low, mid, high);

if (left.sum >= right.sum && left.sum >= cross.sum)
return Data(left.low, left.high, left.sum);
else if (right.sum >= left.sum && right.sum >= cross.sum)
return Data(right.low, right.high, right.sum);
else return Data(cross.low, cross.high, cross.sum);
}
}

[MagmaMcFry]

Minor nitpick: Replace

Code: [Select]

return Data(left.low, left.high, left.sum);with

Code: [Select]

return left;

[RoguelikeRazuka]

@RoguelikeRazuka: you have the right idea now. When you work out where your inequality space intersects with that large box, you can check for values higher than your normal max or lower than your normal min values. if you find such values, then that means some points were more extreme than the normal, existing intersections, therefore none of the actual points is the maximum or minimum (clearly obvious since the values are linear: if they're getting bigger as you go along a line that goes to infinity, then they must keep increasing past that point)

Yes I got it.

Great thanks to all for the help provided.

[Reelya]

Minor nitpick: Replace

Code: [Select]

return Data(left.low, left.high, left.sum);with

Code: [Select]

return left;

You're right there, I didn't notice that all sets of values were coming from the same triplets. If they're mixed you need to create a new object, but if they're all from the same object you just pass the pre-made name itself.

[Bumber]

Would an array have sufficed, or does that not work with recursion?
int data[3];
data[0] = thing1;
data[1] = thing2;
data[2] = thing3;
return data;

[Bumber]

Well, you can't return arrays in c++, but pointers to arrays. Meaning that you would have to create an object. Meaning memory leak.

Oh, right. Is it the same with vectors? (Never used them.)