On Mon, 2011-05-16 at 22:59 +1000, Russell Shaw wrote:
> On 16/05/11 19:26, Peter Clifton wrote:
> > On Mon, 2011-05-16 at 15:54 +1000, Russell Shaw wrote:
> >
> >> From pcjc2/src/borast/borast-bentley-ottmann.c, i used some functions
> >> to make a small test program to see how bo_contour_to_traps() works.
> >
> > The code is mostly stolen from cairo, then stripped down to a bare
> > minumum (e.g. doesn't deal with intersections in contours, as PCB
> > polygons don't have them).
> >
> > I'd be interested to know what you're working on. Please let me know if
> > you spot anything stupid in the borast/ code, I've not completely
> > cleaned the interfaces up ready for merging yet. (The abstraction
> > between them and PCB is not particularly clean).
>
> Hi,
> In poly_PreContour(), the sign of the winding area is found by
> summing the area of each box formed by consecutive points. It is
> not clear if this method is valid. Is there a reference paper?
>
> double area = 0;
> ...
> do {
> area += (double) (p->point[0] - c->point[0]) * (p->point[1] +
> c->point[1]);
> }
Rearranging this:
(p->point[0] - c->point[0]) * (p->point[1] + c->point[1])
p->point[0] * (p->point[1] + c->point[1]) - c->point[0] * (p->point[1] + c->point[1])
p->point[0] * p->point[1] + p->point[0] * c->point[1]) - c->point[0] * p->point[1] - c->point[0] * c->point[1]
PX.PY + PX * CY - CX * PY - CX * CY
So we have an undesired (PX*PY - CX * CY) term added for each triangle
in addition to the correct PX * CY - CX * PY. As we circle the whole
contour, these terms do cancel out, "probably" giving the correct result
in the end.
> I think better if:
>
> int area = 0;
> ...
> do {
> area += p->point[0]*c->point[1] - c->point[0]*p->point[1];
>
> /* http://en.wikipedia.org/wiki/Polygon#Area_and_centroid */
> }
That is also correct, and looks a lot nicer than the PCB code.
I can't think why we do it the way we do, but it could just be a
mistake.
I can't think of any normalising benefit the extra terms would have in
preventing overflow or anything like that. Please feel to chime in if
you know otherwise.
Send a patch to fix it up?
--
Peter Clifton
Electrical Engineering Division,
Engineering Department,
University of Cambridge,
9, JJ Thomson Avenue,
Cambridge
CB3 0FA
Tel: +44 (0)7729 980173 - (No signal in the lab!)
Tel: +44 (0)1223 748328 - (Shared lab phone, ask for me)
Attachment:
signature.asc
Description: This is a digitally signed message part
_______________________________________________ geda-user mailing list geda-user@xxxxxxxxxxxxxx http://www.seul.org/cgi-bin/mailman/listinfo/geda-user