views:

105

answers:

3

Hi,

In one of mine applications I am dealing with graphics objects. I am using open source GPC library to clip/merge two shapes. To improve accuracy I am sampling (adding multiple points between two edges) existing shapes. But before displaying back the merged shape I need to remove all the points between two edges.

But I am not able to find an efficient algorithm that will remove all points between two edges which has same slope with minimum CPU utilization. Currently all points are of type

PointF 

I am calculating slope using following function

  private float Slope(PointF point1, PointF point2)
  {
     return (point2.Y - point1.Y) / (point2.X - point1.X);
  }

Any pointer on this will be a great help.

+1  A: 

What algorithm are you currently using? I can think only of going through all point and for each 3 to check wherher middle point is on vector (or close to) defined by 2 other points. Do you need math for that operation?

0xDEAD BEEF
Currently I am iterating through all points are removing the middle one if its slope is similar to the first and last point's slope. But this operation is taking much more time.I am looking for optimized math for this operation
Ram
How are you calculating slope of a (single) point?
Ravi Vyas
@ Ravi: I calculating slope using following function private float Slope(PointF point1, PointF point2) { return (point2.Y - point1.Y) / (point2.X - point1.X); }
Ram
How much points do you have? I dont think, that math is bottle neck here. How do you iterate through points? How are they sorted? Are they in array or list? Removing point from array could take some time! Better use list!
0xDEAD BEEF
A: 

Just to be clear, you have three points A = (a,b), C = (c,d), and E = (e,f), and are wondering if the segment AE goes through C and thus you can replace the pair of segments AC and CE with the single segment AE?

slope AC = (d-b)/(c-a) = slope CE = (f-d)/(e-c)

multiply through by the denominators, you get (d-b)(e-c) = (f-d)(c-a)

that's just four subtracts, two multiplies, and a compare. You'll need to do the comparison with some error tolerance due to the use of floating point.

Keith Randall
A: 

Well.. I found the solution for my question. Instead of using Sampling method provided by SDK, I created my own sampling method which insert a point between two points at a fixed distance. This reduces the number of point that I need to process and in turn reducing processor usage.

Ram