Implicit line explained?

Implicit line explained?

Post by James William » Fri, 04 Jul 2003 07:18:01



Could someone please explain how the implict line.  I have a book that
explains how to determine the center point  of a circle with radius r and
tangent to two intersecting lines. However it's pseudocode code explains in
the form of lines being implict form.  I.E.  they use
ax + by +c =0 as the line definition.  Now, if I have the points p1(x,y) and
p2(x,y)
which define the line L0  in affine space and points p2(x,y) and p3(x,y)
which forms line L1 and intersects line L0, where are they getting the a, b
and c values for each of the lines.

Now, in the book "Geometric Tools for Computer graphics" it explains the
elements as being:

The alorithm they use is as follows:

struct Line2D
{
  double x,y,a,b,c;

Quote:}

void CircleTangentToLinesGivenR(Line2D L1,Line2D L2, double radius, Point &
center[4])
{
  double discrm0 = sqrt(L1.a*L1.a + L1.b*L1.b) * r;
  double discrm1 = sqrt(L2.a*L2.a + L2.b*L2.b) * r;
  double invDenom = 1.0/(-L2.a*L1.b + L1.a*L2.b);

  center[0].x = -(L2.b*(L1.c+discrm0)-)...

Quote:}

 
 
 

Implicit line explained?

Post by Dave Eberl » Fri, 04 Jul 2003 08:03:19



Quote:> Could someone please explain how the implict line.  I have a book that
> explains how to determine the center point  of a circle with radius r and
> tangent to two intersecting lines. However it's pseudocode code explains
in
> the form of lines being implict form.  I.E.  they use
> ax + by +c =0 as the line definition.  Now, if I have the points p1(x,y)
and
> p2(x,y)
> which define the line L0  in affine space and points p2(x,y) and p3(x,y)
> which forms line L1 and intersects line L0, where are they getting the a,
b
> and c values for each of the lines.

Let p1 = (x1,y1) and p2 = (x2,y2).  The direction of the line is
D = (x2-x1,y2-y1).  A (not-necessarily-unit-length) normal vector
to the line is N = (y2-y1,-(x2-x1)).  The implicit equation is
  0 = Dot(N,(x,y)-(x1,y1))
     = (y2-y1)*(x-x1) - (x2-x1)*(y-y1)
     = (y2-y1)*x + (x1-x2)*y + ((x2-x1)*y1-(y2-y1)*x1)
     = a*x + b*y + c
where a = y2-y1, b = x1-x2, c = (x2-x1)*y1-(y2-y1)*x1

Quote:> Now, in the book "Geometric Tools for Computer graphics" it explains the
> elements as being:

> The alorithm they use is as follows:

> struct Line2D
> {
>   double x,y,a,b,c;
> }

<snip>

You must have a different printing of the book than I do.
My copy does not have a definition for "struct Line2D".
This struct should contain only a, b, and c.  The x and y
members do not belong there.

Quote:> void CircleTangentToLinesGivenR(Line2D L1,Line2D L2, double radius, Point
&
> center[4])
> {
>   double discrm0 = sqrt(L1.a*L1.a + L1.b*L1.b) * r;
>   double discrm1 = sqrt(L2.a*L2.a + L2.b*L2.b) * r;
>   double invDenom = 1.0/(-L2.a*L1.b + L1.a*L2.b);

>   center[0].x = -(L2.b*(L1.c+discrm0)-)...
> }

Not quite what appears in my copy.  Looks like you renamed
some variables.  (I would have done the same since I do not
use lower case "ell" in the manner used in the pseudocode.)
The output centers are returned through "Point2D center[4]".
However, the "r" in the body of the function is a typographical
error in the book.  It should be "radius".

--
Dave Eberly

http://www.magic-software.com
http://www.wild-magic.com

 
 
 

Implicit line explained?

Post by Just d' FAQ » Fri, 04 Jul 2003 11:30:35


On Wed, 02 Jul 2003 22:18:01 GMT, "James Williams"


>Could someone please explain how the implict line.  I have a book that
>explains how to determine the center point  of a circle with radius r and
>tangent to two intersecting lines. However it's pseudocode code explains in
>the form of lines being implict form.  I.E.  they use
>ax + by +c =0 as the line definition.  Now, if I have the points p1(x,y) and
>p2(x,y)
>which define the line L0  in affine space and points p2(x,y) and p3(x,y)
>which forms line L1 and intersects line L0, where are they getting the a, b
>and c values for each of the lines.

Be aware that a single equation will define a line in 2D, but a plane
in 3D. Here's one easy way to derive an equation. If point P is on the
same line as P1 and P2, then the three are not "linearly independent".
Thus the determinant of the matrix with those (homogeneous) columns

  [x1 x2 x]
  [y1 y2 y]
  [1  1  1]

must be zero. We expand the determinant by cofactors of the last
column to get equation

  (y1-y2)*x - (x1-x2)*y + (x1*y2-x2*y1) = 0

From this we read off coefficients for ax+by+c=0 as

  a = y1-y2
  b = x2-x1
  c = x1*y2-x2*y1

Example.
Points P1=(3,4) and P2=(5,0). Line equation coefficients are

  a = 4-0 = 4
  b = 5-3 = 2
  c = 3*0-5*4 = -20

 
 
 

1. Cel-Rendering, Implicit Line Drawing

Hi,

Just wanted to know if there is any information available (net? books?)
dealing with the issue of control over implicitly created lines, resulting
from cel-rendering of 3D geometry.

With traditional 2D animation/drawing, lines are drawn explicitly, and are
similarly under the direct control of the artist.

With cel-rendered 3D, however, lines are implicitly or indirectly created
from the cel-rendering algorithm.

I just wanted to know if there are any methods which are known, or under
investigation, to set up ways to control the look/shape of cel-rendered 3D
lines -- particularly to emulate the look of 2D lines/curves in traditional
hand-drawings.

2. help with metafiles!!!

3. Lines,Lines,Lines

4. 3DS FORMAT?

5. Implicit Surfaces '96

6. Long Filename Support PS 4.0.1

7. CFP: Implicit Surfaces '96

8. LightWave 3D 4.0 vs 3D Studio 4.0

9. raytracing implicit surfaces

10. Raytracing for Implicit Surfaces

11. Newbie Q: Ray tracing implicit surfaces in Povray 3.1

12. POV-Ray: Implicit & Parametric surfaces