Solved

need to scale a shape without losing information

Posted on 2006-11-06
11
212 Views
Last Modified: 2010-04-16
I have a list of points which define a shape
I need to shrink the shape
I know which direction to move the points
because if the angle is concave or convex
but sometimes if the points are too close to each other
they overlap and produce the wrong results

does anyone know of a good scaling algorithm that can avoid or compensate for this problem?
0
Comment
Question by:DangerMode
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 3
  • 2
  • +1
11 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 17886556
multiplying the coordinates of all the points by a constant will scale the shape
0
 

Author Comment

by:DangerMode
ID: 17886807
It must be done on a point by point basis
A uniform scale doesnt preserve the original shape but it does keep it proportional.
Therefore when computing the new point based on a cross vector at certain angles if the scale is to big
the points overlap themselves.

0
 
LVL 84

Expert Comment

by:ozo
ID: 17886826
Multiplying on a point by point basis is what I said.
A uniform scale preserves the original shape and keeps it proportional,
(which I thought were the same thing, unless you are using "shape" or "proportional" in a way I don't understand)
Points have 0 size, so the only way they can overlap is if they are the same point.
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 6

Expert Comment

by:_iskywalker_
ID: 17887747
How do you interpolate the points? with splines? Maybe you should make an image of the image in normal mode, and then
scale it down (undersample, take for subsampling 2 times, every second pixel).
0
 
LVL 3

Expert Comment

by:Kipski
ID: 17892281
I agree with ozo from what youv said...

Another way to do it would be to calculate or store the centre point of the shape and use this to determine the distance of each point in the shape boundary for which you have a reading from that point.  This way you could scale the shape by directly calculating the new size in proportion to its original position along the vector between it and the centre point.

It really depends on your original design and the complexity of the shapes you are drawing...

I created a shape drawing program, which deals with simple geometric forms such as squares, circles, triangles, diamonds and stars...  I treated each as a circle...

A square is a circle with only 4 points on its circumference recorded, a triangle has 3 points recorded... etc

The method I outlined for resizing worked well in this approach, proportionality was always maintained...  Rotating the shape was also simple...  
To draw the shape you just need the centre point, the radius or the circle and the angle of rotation, the draw method is identical regardless of the shape type, using these parameters, using oom

More complex shapes may require a different approach
0
 
LVL 3

Expert Comment

by:Kipski
ID: 17892300
To draw the shape you just need the centre point, the radius or the circle and the angle of rotation, the draw method is identical regardless of the shape type, using these parameters, using oom

And the number of points on the circumference....   Sorry...
0
 

Author Comment

by:DangerMode
ID: 17892907
I apologize for not being able to articulate what I need, it is hard to say in words so I have created a couple pictures to show you.
Basically, I dont want uniform proportional scaling as that doesnt maintain a uniform distance away from the line. (contraction or erosion scaling) not sure the proper term for this either?
http://i121.photobucket.com/albums/o209/DangerMode/bad-vector.gif
0
 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
ID: 17893713
given points (x0,y0) (x1,y1) (x2,y2) in clockwise order, and constant distance d
A01 = y1-y0;
B01 = x0-x1;
A12 = y2-y1;
B12 = x1-x2;
C01 = A01*x0+B01*y0+d*sqrt(A01*A01+B01*B01);
C12 = A12*x1+B12*y1+d*sqrt(A12*A12+B12*B12);
Det=A01*B12-A12*B01;
newX1= (B12*C01-B01*C12)/Det;
newY1= (A01*C12-A12*C01)/Det;
0
 

Author Comment

by:DangerMode
ID: 17894676
You are awesome finally someone who understands!
that is what I am doing

1) do you know the name of this algorithm, what would you call this?

So the problem arises when the distance is bigger then the point density and then points overlap
like in this case
http://i121.photobucket.com/albums/o209/DangerMode/vectorerr1.gif
(sorry the point numbers are upside down, but they show where the algorithm breaks down)

2) I thought of several approaches to fix it like removing those points and making a point at intersection etc
and all have other problems with them,
If you have any leads or ideas on how to fix this I would really really appreciated it.
0
 
LVL 84

Expert Comment

by:ozo
ID: 17894835
It looks like you want to take the boundary defined by the black line (adding points were lines intersect) and eliminate all points contained inside that boundary. (using a non-zero or poitive winding number definition of inside)
0
 
LVL 84

Expert Comment

by:ozo
ID: 17894866
Here's how postscript defines different kinds of line joins
http://www.capcode.de/help/setlinejoin
http://www.capcode.de/help/setmiterlimit
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Does the idea of dealing with bits scare or confuse you? Does it seem like a waste of time in an age where we all have terabytes of storage? If so, you're missing out on one of the core tools in every professional programmer's toolbox. Learn how to …
A short article about problems I had with the new location API and permissions in Marshmallow
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

730 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question