Got an optimizing algorithm problem here. Maybe you can help out with some idea or pseudo-code?
I have a bunch of lines, but as you see on the picture they are not optimized. What seems one line consists of many points on the same line. I want to remove those points so that I have only the necessary points building the lines.
My approach would be.
for p in points do
con_p[] = get_connected_points(p)
if length con_p[] == 1
then
break
else
if (con_p[0].x-p.x)/(con_p[0].y-p.y) ==
(con_p[1].x-p.x)/(con_p[1].y-p.y)
then
remove_point(p)
end for
Just my first though. Would need the two other functions to work accordingly. Hope it makes sense.
Smiles
Sam
Sorry
if (con_p[0].x-p.x)/(con_p[0].y-p.y) ==
(con_p[1].x-p.x)/(con_p[1].y-p.y)
should be
if (con_p[0].x-p.x)/(con_p[0].y-p.y) ==
(p.x-con_p[1].x)/(p.y-con_p[1].y)
Smiles
Form a simple mathematical POV:
Take three points. Check if they are in one line (linear function). Remove middle point.
No idea how to do this in programing.
It’s “from” not “form”, sorry.
calculate direction vectors for the connected lines, if they’re (about) the same you can whether remove the mid point or calculate a new, average line
mh, didn’t read what gedazz wrote.
the implementation is simple: P1P2 = p2 – p1; p1/2 being the absolute coordiantes
I didn’t add that I don’t store the lines that easily.
They are just stored as a list of pairs (2 points), not as big connected lines. So its a bit harder.
The first option is to change the way the lines are stored to a pair of indices into a list. If you load in the points from somewhere you should add an algorithm to see if any two points are very close (Length(p1 – p2) 0.999) where p2 is the point that is shared.
The second option is to leave it as a list of two points and do the test between every pair of lines first checking if they share a point.
The first method would be better if you sent the lines to a 3D API (like OpenGL/DirectX) because it may improve performance sending a list of points and a list of indices.
I have an easy (probably not best) approach :
Get the slope between two points of the list (since they are all on the same “line”) M = (y2-y1)/(x2-x1)
if(M != 0)
{
/*Algorithm to sort the x value of each point
the biggest and smallest value are the points that should be preserved scrap the rest.
}
else if(x2 – x1 == 0) //x1,x2 = values of two points from list
{
/*Algorithm to sort the y value of each point
the biggest and smallest value are the points that should be preserved scrap the rest.
}
The list of points to draw the lines to create the Map should be sent to the graphic card by VBO’s (vertex buffer objects) or VA (Vertex array) VBO aren’t supported on most hardware since there recent but there the most effective.
Now I remember why I chose networking and not coding as my profession.
Remember when you are checking the slope of the line or the angle between two connected segments or however you are doing it…always add in a tolerance or fudge factor to make up for floating point precision inaccuracy. That’s a bug that will drive you nutty.
You could optimize it by Hand
Why don’t use Polygons? Aren’t they faster to draw and easier to handle?
Vector projection. Slopes and angles are inaccurate over larger distances. Project each point onto each line vector and check if the distance between the point and it’s intersection point is less than the tolerance.
Is this game going to use Psyhx?
1. Convert the list to a graph.
2. For every vertex with 2 edges connected, if the dot product of these 2 edges is > 0.999 then remove the vertex and combine the edges.
3. Convert the graph back to a list.
Simple and fast (linear time).
Hope that helps
@nadult: That’s what i did too.
http://spamtheweb.com/ul/upload/210509/3088_lineOptimisation.php
The dot product method will work the best. It (could) tell you the angle between 3 points, and if that angle is close to +-180 then they are in a straight line. It will work for 3d points as well. Don’t use “gradient” method, because it will be very inconsistent – what if delta y is very small or zero?.
@Monx, your app looks neat, but there is one bug. If you place points A, then point B, then point C so that A lies in the middle, then optimize, then your app will erase point B.
“I didn’t add that I don’t store the lines that easily.
They are just stored as a list of pairs (2 points), not as big connected lines. So its a bit harder.”
hmmm…
This is similar to line tools within some graphic and photo-editing software. The beginning and end of a drawn line are detected, then based on curves, dots are plotted out at certain angles to keep the path on top of the line. These tools usually have an optimization option allowing you to decrease or increase the points on the line. If you can find some info and code for that feature – I bet, it would definitely help you out. You might even be able to put in an adjustable optimization in your engine, depending on what lines are for what.
this might work?
for a in lines
as = a.slope
for b in lines
if as==b.slope
if a.1==b.2
a.1 = b.1
delete b
else if a.2==b.1
a.2 = b.2
delete b
I love this gay
Michal .. at last you’ve started writing some fucking code for a change.
What you want is to cluster points in sets of collinear points.
Here’s a link treating a similar problem and some algorithms are discussed in there.
http://discuss.joelonsoftware.com/default.asp?interview.11.576927.12
Also ,
This is what you should’ve done from the start instead of talking about inspirational crap ( which you do over a beer and not on a blog ).
If you rush design you produce a piece of crap. That’s general knowledge.
Amazing that there is one now and then that is actually angry that they’re not getting something for free fast enough lol.
Thanks guys. It gave me some ideas, although most of your propositions would be too slow for what I’m planning (thousands of these lines?). I think I need to do some spatial hashing first and then apply some easy trick.
This is what you should’ve done from the start instead of talking about inspirational crap ( which you do over a beer and not on a blog ).
I code over a beer and blog about inspiration ;p.
What about angle checking: if the angle of a node is 0, remove that node?