lib2geom-devel — development discussion

[Lib2geom-devel] Closing segment in Path

[Krzysztof K. <twe...@gm...>]

Hello

Right now, methods such as end_closed() and end_open() determine which
segments to include only by looking at the closed flag. However, this
makes little sense - if the path contains a closing segment which is
degenerate, i.e. has exactly zero length, because the last real
segment is a Bezier curve, the iteration will needlessly include it.

In order to be able to faithfully represent closed paths where the
last segment is not linear, the closing segment should be included in
the range returned by [begin(), end_default()] only when: 1. the path
is closed, 2. the closing segment is non-degenerate (initialPoint() !=
finalPoint(), tested with exact comparison).

By doing this and using an SVG path data writer that writes out the
last non-linear segment in absolute coordinates when it closes the
path, we can have perfect roundtrip between 2Geom paths and SVG.

What do you think of this change?

Regards, Krzysztof

[Lib2geom-devel] Path transform strangeness

[Krzysztof K. <twe...@gm...>]

Hello

There is some kind of problem when parsing the file monkey.svgd (in
the toys directory), e.g. with the load-svgd toy. It throws a
ContinutyError when transforming the path. I changed the classes
related to parsing recently, but this doesn't seem related - the error
is also present in revision 2200.

Any ideas what's going on? It should not be possible for two
applications of the same affine transform to the same point to yield
different results.

Regards, Krzysztof

[Lib2geom-devel] Path and Curve API cleanups

[Krzysztof K. <twe...@gm...>]

Hello

1. I renamed all the nearestPoint() methods to nearestTime(). These
functions return a time value, not points, so the former name was
misleading. Furthermore, this allows us to add functions such as
nearestPoint(), nearestCurve(), nearestPath(), and so on, to
PathVector.

2. I will also remove the last two parameters from
Curve::nearestTime() that specify the minimum and maximum considered
time values. Code that requires this should just use portion(), and it
seems this isn't used anywhere in Inkscape. The only place that uses
this functionality is the HVLineSegment toy.

3. The functions nearestPoint() and allNearestPoints() that act on
PathVector will be renamed to nearestPosition() and
allNearestPositions(), in keeping with point 1, and converted to
methods. The optional pointer for returning the squared distance will
be removed - instead call distance(x, pv.nearestPoint(x))

4. HLineSegment and VLineSegment will be removed, so that every curve
type can be transformed by an affine without duplicating it. We can
still write vline and hline segments to SVG by checking whether the
relevant coordinates of the line segment's initial and final point are
equal.

Regards, Krzysztof

Re: [Lib2geom-devel] Path storage idea

[Johan E. <jbc...@sw...>]

I have to think much longer about this. But first of, it seems that this 
would prevent the user to add his own curve types. When there are no 
virtual functions anymore, this means switch statements (or similar) on 
the type field? Basically hard-coded virtual functions, kind of.
I am afraid you'll end up mimicking C++'s polymorphic functionality, in 
a much harder to maintain or extend format, for only a little storage 
gain...

I think you'd be better of working on other things for now, and have 
this cook for a bit in your mind.

regards,
Johan


On 25-6-2014 21:05, Krzysztof Kosiński wrote:
> The current storage for path data is a bit wasteful and stores every
> segment endpoint in a path twice. Here is my proposal for an
> alternative implementation. I'm not yet convinced whether this would
> be a worthwhile improvement, so discussion is welcome.
>
> Path data would be stored in a series of structured like this:
>
> struct PathStorage {
>      int32_t type;
>      int32_t length;
>      double final_x;
>      double final_y;
> };
>
> "type" would contain the type of the segment - moveto, linear, bezier,
> arc, sbasis, and so on. "length" would contain the total size of the
> current segment. final_x and final_y would contain the coordinates of
> the final point. This way every type of segment would have the final
> point in the same place, simplifying access to this data from Curve
> classes.
>
> After PathStorage, the memory would contain additional parameters,
> such as the intermediate Bezier control points, arc parameters, sbasis
> coefficients, and so on. This could be accessed by static_cast to an
> appropriate derived type. The next PathStorage structure start at the
> address of the current structure + length.
>
> Each Curve class would have a constructor such as this:
>
> BezierCurve(PathStorage *data);
>
> The passed "data" would have to point one segment before the
> represented curve, so that the curve class could access its initial
> point (stored as the final point of the previous segment).
>
> Normal constructors that instantiate standalone curves would allocate
> storage for two PathStorage structures, a moveto and a segment
> matching the curve type. The curve class would also set a flag
> indicating that it is supposed to free this memory on destruction.
>
> In the above scenario, the amount of memory consumed by standalone
> curves on a 64-bit machine would increase by 32 bytes: 16 bytes for
> the four additional ints in the path data, and a pointer and a flag
> for each curve object (the flag would probably take 8 bytes due to
> alignment). However, a Path could only store the PathStorage data, and
> construct the curve objects on demand, saving 24 bytes per segment
> (-16 by not storing each endpoint twice, -8 by not storing a pointer
> to each curve object, -8 by not storing the curve object's vptr, +8
> for the two ints per segment).
>
> The disadvantage is that iterating over paths would require a memory
> allocation for every segment access, since the on-demand objects
> cannot be put on the stack and returned by value - we need to return
> the correct type. It would also mean that the iterators on Path would
> have to return a smartpointer to a dynamically allocated object,
> rather than a reference.
>
> Regards, Krzysztof
>
> ------------------------------------------------------------------------------
> Open source business process management suite built on Java and Eclipse
> Turn processes into business applications with Bonita BPM Community Edition
> Quickly connect people, data, and systems into organized workflows
> Winner of BOSSIE, CODIE, OW2 and Gartner awards
> http://p.sf.net/sfu/Bonitasoft
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>
>

[Lib2geom-devel] Path storage idea

[Krzysztof K. <twe...@gm...>]

The current storage for path data is a bit wasteful and stores every
segment endpoint in a path twice. Here is my proposal for an
alternative implementation. I'm not yet convinced whether this would
be a worthwhile improvement, so discussion is welcome.

Path data would be stored in a series of structured like this:

struct PathStorage {
    int32_t type;
    int32_t length;
    double final_x;
    double final_y;
};

"type" would contain the type of the segment - moveto, linear, bezier,
arc, sbasis, and so on. "length" would contain the total size of the
current segment. final_x and final_y would contain the coordinates of
the final point. This way every type of segment would have the final
point in the same place, simplifying access to this data from Curve
classes.

After PathStorage, the memory would contain additional parameters,
such as the intermediate Bezier control points, arc parameters, sbasis
coefficients, and so on. This could be accessed by static_cast to an
appropriate derived type. The next PathStorage structure start at the
address of the current structure + length.

Each Curve class would have a constructor such as this:

BezierCurve(PathStorage *data);

The passed "data" would have to point one segment before the
represented curve, so that the curve class could access its initial
point (stored as the final point of the previous segment).

Normal constructors that instantiate standalone curves would allocate
storage for two PathStorage structures, a moveto and a segment
matching the curve type. The curve class would also set a flag
indicating that it is supposed to free this memory on destruction.

In the above scenario, the amount of memory consumed by standalone
curves on a 64-bit machine would increase by 32 bytes: 16 bytes for
the four additional ints in the path data, and a pointer and a flag
for each curve object (the flag would probably take 8 bytes due to
alignment). However, a Path could only store the PathStorage data, and
construct the curve objects on demand, saving 24 bytes per segment
(-16 by not storing each endpoint twice, -8 by not storing a pointer
to each curve object, -8 by not storing the curve object's vptr, +8
for the two ints per segment).

The disadvantage is that iterating over paths would require a memory
allocation for every segment access, since the on-demand objects
cannot be put on the stack and returned by value - we need to return
the correct type. It would also mean that the iterators on Path would
have to return a smartpointer to a dynamically allocated object,
rather than a reference.

Regards, Krzysztof

Re: [Lib2geom-devel] Templates

[Stuart A. <st...@ya...>]

Just realised you are talking about C++ not python, sorry for the noise!
 
S++


On , Stuart Axon <st...@ya...> wrote:
 

>
>
>Hi,
>  I would have really liked to use 2geom in shoebot; the main reason we didn't is - that it is not installable off pypi + (last time I tried) doesn't work with virtualenv.
>
>
>For users of projects it's important that 3rd party libraries are easy to install, + work on the 3 main OSs.
>
>
>Numpy + Pillow have native parts but can install via pip, I'm sure lib2geom could too.
> 
>S++
>
>
>
>On Tuesday, June 24, 2014 9:57 PM, Krzysztof Kosiński <twe...@gm...> wrote:
> 
>
>>
>>
>>2014-06-24 11:44 GMT+02:00  <jbc...@sw...>:
>>> I asked myself the question: should 2geom be in the standard library? Surely, many applications would benefit from a standard geometry library. Then I thought, it is not nearly as general as it could be.
>>
>>I am somewhat skeptical of pursuing generality as a design goal in
>>itself, beyond the needs of Inkscape and other drawing-centric
>>programs.
 CGAL is a lot more general than 2Geom, but it's also a pain
>>to use.
>>
>>Regards, Krzysztof
>>
>>
>>------------------------------------------------------------------------------
>>Open source business process management suite built on Java and Eclipse
>>Turn processes into business applications with Bonita BPM Community Edition
>>Quickly connect people, data, and systems into organized workflows
>>Winner of BOSSIE, CODIE, OW2 and Gartner awards
>>http://p.sf.net/sfu/Bonitasoft
>>_______________________________________________
>>Lib2geom-devel mailing list
>>Lib...@li...
>>https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>>
>>
>>
>
>

Re: [Lib2geom-devel] Templates

[Stuart A. <st...@ya...>]

Hi,
  I would have really liked to use 2geom in shoebot; the main reason we didn't is - that it is not installable off pypi + (last time I tried) doesn't work with virtualenv.

For users of projects it's important that 3rd party libraries are easy to install, + work on the 3 main OSs.

Numpy + Pillow have native parts but can install via pip, I'm sure lib2geom could too.
 
S++


On Tuesday, June 24, 2014 9:57 PM, Krzysztof Kosiński <twe...@gm...> wrote:
 

>
>
>2014-06-24 11:44 GMT+02:00  <jbc...@sw...>:
>> I asked myself the question: should 2geom be in the standard library? Surely, many applications would benefit from a standard geometry library. Then I thought, it is not nearly as general as it could be.
>
>I am somewhat skeptical of pursuing generality as a design goal in
>itself, beyond the needs of Inkscape and other drawing-centric
>programs. CGAL is a lot more general than 2Geom, but it's also a pain
>to use.
>
>Regards, Krzysztof
>
>
>------------------------------------------------------------------------------
>Open source business process management suite built on Java and Eclipse
>Turn processes into business applications with Bonita BPM Community Edition
>Quickly connect people, data, and systems into organized workflows
>Winner of BOSSIE, CODIE, OW2 and Gartner awards
>http://p.sf.net/sfu/Bonitasoft
>_______________________________________________
>Lib2geom-devel mailing list
>Lib...@li...
>https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>
>
>

Re: [Lib2geom-devel] Templates

[Krzysztof K. <twe...@gm...>]

2014-06-24 11:44 GMT+02:00  <jbc...@sw...>:
> I asked myself the question: should 2geom be in the standard library? Surely, many applications would benefit from a standard geometry library. Then I thought, it is not nearly as general as it could be.

I am somewhat skeptical of pursuing generality as a design goal in
itself, beyond the needs of Inkscape and other drawing-centric
programs. CGAL is a lot more general than 2Geom, but it's also a pain
to use.

Regards, Krzysztof

Re: [Lib2geom-devel] Templates

[Jabiertxo A. C. <jab...@ma...>]

>> Another interesting area of improvement would be to put the
node-based
>> path representation from the node editor in 2Geom, though this would
>> need extra effort to decouple it from the display and event handling
>> code.

>Jaberto is thinking about this a little bit.  Perhaps he could say
>something to this.

Sorry but im starting a C++ book and dont look throught code for now,
Also don't understand very well :(

The goal in our mind is translate the hacked version of powerstroke used
to make fillet-chamfer LPE to a more robust class inside 2Geom. This
class is a idea of Nathan, done in his code review of fillet-chamfer,
and is something similar, using his words, a class to handle "sidecar
data" to nodes/points.

Hi, Jabier.

Re: [Lib2geom-devel] Templates

[<jbc...@sw...>]

---- "Krzysztof Kosiński" <twe...@gm...> wrote: 
> 2014-06-16 12:22 GMT+02:00 Nathan Hurst <nj...@nj...>:
> > Yes, I thought about this when we started, and mental and I discussed
> > this at length.  Here are the reasons against:
> >
> > * as Krzysztof says, templates mean everything must be on the compile
> >   path for everything.
> > * More complex methods for everything
> > * Ugly error messages
> > * Minor performance cost
> > * Slower compiles (a big issue for me - the slower the compile the
> >   slower the development)
> 
> Slower compilation can be alleviated somewhat by -O0 and using clang.
> Your points 2 and 3 are the main problems, and furthermore they
> complicate the use of the library. The main advantage of 2Geom over
> more complex libraries such as CGAL is its ease of use.

With default template parameters (or aliases like std::string), I don't think the use of the library would change really.
The compiler error messages is a good point, but we already have that 'problem' for the templated stuff that we have.
 
> > I couldn't think of any other compelling reasons for (especially when you
> > consider that D2<T> does what you want).
> 
> The biggest reason "for" is less code duplication, which is why I
> created GenericInterval and GenericRect - fixing every minor bug and
> adding every method in both places was getting really tedious. On the
> other hand for Point we wouldn't deduplicate a lot of code, and on top
> of that we would have to write lots of template boilerplate.
> 
> 2014-06-16 20:29 GMT+02:00 Johan Engelen <jbc...@sw...>:
> > Yep. But, our current design could be changed to alleviate this issue
> > somewhat, by splitting out some functionality in different header files.
> > Things like Path::toPwSb(), Path::allNearestPoints, ... should not be member
> > functions.
> 
> I don't see why allNearestPoints should be a free function. It makes
> sense that is is a method, in keeping with the "ease of use" design
> goal.

One can have long debates about making something a member function or not.
I don't see an ease-of-use problem between:
  path1.allNearestPoints(...)
and
  all_nearest_points(path1, ...)

I only meant to say that we have the option to split files. Some of our class definitions are huge, because of (imho) adding too many class methods instead of putting those methods outside the class. I am guilty of this myself, but have changed opinion a bit recently.
Come to think of it, allNearestPoints might be generalized to a 2geom algorithm that works for all objects passed with an interface similar to Path (argument in favor of out-of-class function).

> >> * Minor performance cost
> >
> > You made a typo: minor performance boost. ;-)
> > (serious question: I'm curious to see an example where using templates makes
> > the code slower)
> 
> Multiple, almost identical instantiations of a template increase code
> size, which in turn reduces code density and makes worse use of the
> CPU instruction cache. So templates may not always improve
> performance.

This is what everybody says, but I'm not buying it. I think this only results in less performance for some pathological test cases.
I'd like to see a real case where templated code reduced performance.
In our case, I don't see a problem here.

> > If that were true, we would not need Point at all.
> > But you are right, Point<float> would not be worth it. Point<int> would be
> > much better; but mind caveats noted by Krzysz.
> > So I'll give up on this one for now.
> > (how about IntPoint<int>, <unsigned>, <short>, etc, Krzysz?)
> 
> I don't see much use for IntPoint<unsigned>, because it will lead to
> annoying signedness caveats (e.g. you have to be careful when
> subtracting unsigned points).
> 
> Same for IntPoint<short>, because it has low resolution and shorts are
> not faster than ints on any modern CPUs. The only case where it would
> be useful is when you have to process a large amount of points stored
> in memory, because then it would increase the number of them that fits
> in the cache.
> 
> There may be some use for IntPoint<long>, IntPoint<long long> or
> IntPoint<Bignum>, but I don't see any clear use cases right now.

Yeah I don't see much use either, but it's a little beside the point :)

I asked myself the question: should 2geom be in the standard library? Surely, many applications would benefit from a standard geometry library. Then I thought, it is not nearly as general as it could be.
Hope you all could ponder of this question a bit (2geom -> stdlib?). When Inkscape's release is done, I hope we can switch to C++11, triggering some motivation for revisiting large parts of 2geom's code, making sure the interfaces are homogeneous, etc.

regards,
  Johan

Re: [Lib2geom-devel] Templates

[Krzysztof K. <twe...@gm...>]

2014-06-16 12:22 GMT+02:00 Nathan Hurst <nj...@nj...>:
> Yes, I thought about this when we started, and mental and I discussed
> this at length.  Here are the reasons against:
>
> * as Krzysztof says, templates mean everything must be on the compile
>   path for everything.
> * More complex methods for everything
> * Ugly error messages
> * Minor performance cost
> * Slower compiles (a big issue for me - the slower the compile the
>   slower the development)

Slower compilation can be alleviated somewhat by -O0 and using clang.
Your points 2 and 3 are the main problems, and furthermore they
complicate the use of the library. The main advantage of 2Geom over
more complex libraries such as CGAL is its ease of use.

> I couldn't think of any other compelling reasons for (especially when you
> consider that D2<T> does what you want).

The biggest reason "for" is less code duplication, which is why I
created GenericInterval and GenericRect - fixing every minor bug and
adding every method in both places was getting really tedious. On the
other hand for Point we wouldn't deduplicate a lot of code, and on top
of that we would have to write lots of template boilerplate.

2014-06-16 20:29 GMT+02:00 Johan Engelen <jbc...@sw...>:
> Yep. But, our current design could be changed to alleviate this issue
> somewhat, by splitting out some functionality in different header files.
> Things like Path::toPwSb(), Path::allNearestPoints, ... should not be member
> functions.

I don't see why allNearestPoints should be a free function. It makes
sense that is is a method, in keeping with the "ease of use" design
goal.

>> * Minor performance cost
>
> You made a typo: minor performance boost. ;-)
> (serious question: I'm curious to see an example where using templates makes
> the code slower)

Multiple, almost identical instantiations of a template increase code
size, which in turn reduces code density and makes worse use of the
CPU instruction cache. So templates may not always improve
performance.

> If that were true, we would not need Point at all.
> But you are right, Point<float> would not be worth it. Point<int> would be
> much better; but mind caveats noted by Krzysz.
> So I'll give up on this one for now.
> (how about IntPoint<int>, <unsigned>, <short>, etc, Krzysz?)

I don't see much use for IntPoint<unsigned>, because it will lead to
annoying signedness caveats (e.g. you have to be careful when
subtracting unsigned points).

Same for IntPoint<short>, because it has low resolution and shorts are
not faster than ints on any modern CPUs. The only case where it would
be useful is when you have to process a large amount of points stored
in memory, because then it would increase the number of them that fits
in the cache.

There may be some use for IntPoint<long>, IntPoint<long long> or
IntPoint<Bignum>, but I don't see any clear use cases right now.

Regards, Krzysztof

Re: [Lib2geom-devel] Templates

[Johan E. <jbc...@sw...>]

Attempt at rebuttal:
(please read as if replying to overall more templetization, not just 
Point<...>)

On 16-6-2014 12:22, Nathan Hurst wrote:
> On Mon, Jun 16, 2014 at 01:57:26AM +0200, Krzysztof Kosi??ski wrote:
>> 2014-06-16 0:01 GMT+02:00 Johan Engelen <jbc...@sw...>:
>>> Hi all,
>>>     I am reading Modern C++ Design by Andrei Alexandrescu and already
>>> after the first few pages, I want to start work on 2geom that I've been
>>> thinking about for a while. Would like to hear your thoughts,
>>> encouragement or otherwise :-)
> ...
>> Furthermore, this would require changing many functions that take
>> Point to template functions taking Point<Coord>. We would effectively
>> need to lift most of 2Geom code into headers.
> Yes, I thought about this when we started, and mental and I discussed
> this at length.  Here are the reasons against:
>
> * as Krzysztof says, templates mean everything must be on the compile
>    path for everything.

Yep. But, our current design could be changed to alleviate this issue 
somewhat, by splitting out some functionality in different header files. 
Things like Path::toPwSb(), Path::allNearestPoints, ... should not be 
member functions.

> * More complex methods for everything

True.
So? ;)

> * Ugly error messages

clang has *much* better error messages than gcc (up to the point where I 
am considering using clang on windows, even though the binaries do not 
work 100% yet). Plus, we could add checking code to improve error messages.

> * Minor performance cost

You made a typo: minor performance boost. ;-)
(serious question: I'm curious to see an example where using templates 
makes the code slower)

> * Slower compiles (a big issue for me - the slower the compile the
>    slower the development)

lib2geom compilation at the moment is pretty fast, you really notice 
this now?
(splitting things in more headers would shave off some compilation time)

>
> I couldn't think of any other compelling reasons for (especially when you
> consider that D2<T> does what you want).

If that were true, we would not need Point at all.
But you are right, Point<float> would not be worth it. Point<int> would 
be much better; but mind caveats noted by Krzysz.
So I'll give up on this one for now.
(how about IntPoint<int>, <unsigned>, <short>, etc, Krzysz?)

>>> Point<double> is just the start. My endgoal is to be able to choose
>>> Path<CubicBezier>: a path for which all functions know that it is just a
>>> vector with CubicBeziers, allowing SIMD optimization of many operations
>>> on it. Instead of the Path<Curve> that we have now, that does not allow
>>> for any of that.
>> This would be interesting. Path could also have a second parameter
>> specifying the underlying structure: vector, list or an
>> order-statistic tree.
> I suspect it would be hard to get useful optimisations this way.

On transform, I was able to get several times performance improvement 
without much effort if you remember. Our implementations for some basic 
operations are not all that fast and I feel improvement is possible. If 
only the code would compile-time decide on using a vector of shared 
pointers, or a shared vector of data; don't know how much it would 
improve performance, but it will I'm quite sure.

The target is being able to do powerstroke-like stuff *super-fast*. Most 
of this is using Pw D2 though, so that is already much faster than Path 
(not reallocating new memory on just about every operation). I'm not so 
familiar with S-basis, would a fixed number of coefficients make sense 
there? (like it would for beziers, where e.g. having all cubic beziers 
is fine).

Hmpf... well, reading on in the book. When release is out, we've 
switched to C++11, got proper testing in place, some profiling, and time 
is left, perhaps... :-)

>> Another interesting area of improvement would be to put the node-based
>> path representation from the node editor in 2Geom, though this would
>> need extra effort to decouple it from the display and event handling
>> code.
> Jaberto is thinking about this a little bit.  Perhaps he could say
> something to this.
>
> njh
>

Re: [Lib2geom-devel] Templates

[Nathan H. <nj...@nj...>]

On Mon, Jun 16, 2014 at 01:57:26AM +0200, Krzysztof Kosi??ski wrote:
> 2014-06-16 0:01 GMT+02:00 Johan Engelen <jbc...@sw...>:
> > Hi all,
> >    I am reading Modern C++ Design by Andrei Alexandrescu and already
> > after the first few pages, I want to start work on 2geom that I've been
> > thinking about for a while. Would like to hear your thoughts,
> > encouragement or otherwise :-)

...
> Furthermore, this would require changing many functions that take
> Point to template functions taking Point<Coord>. We would effectively
> need to lift most of 2Geom code into headers.

Yes, I thought about this when we started, and mental and I discussed
this at length.  Here are the reasons against:

* as Krzysztof says, templates mean everything must be on the compile
  path for everything.
* More complex methods for everything
* Ugly error messages
* Minor performance cost
* Slower compiles (a big issue for me - the slower the compile the
  slower the development)

I couldn't think of any other compelling reasons for (especially when you
consider that D2<T> does what you want).

> > Point<double> is just the start. My endgoal is to be able to choose
> > Path<CubicBezier>: a path for which all functions know that it is just a
> > vector with CubicBeziers, allowing SIMD optimization of many operations
> > on it. Instead of the Path<Curve> that we have now, that does not allow
> > for any of that.
> 
> This would be interesting. Path could also have a second parameter
> specifying the underlying structure: vector, list or an
> order-statistic tree.

I suspect it would be hard to get useful optimisations this way.

> Another interesting area of improvement would be to put the node-based
> path representation from the node editor in 2Geom, though this would
> need extra effort to decouple it from the display and event handling
> code.

Jaberto is thinking about this a little bit.  Perhaps he could say
something to this.

njh

Re: [Lib2geom-devel] Templates

[Krzysztof K. <twe...@gm...>]

2014-06-16 0:01 GMT+02:00 Johan Engelen <jbc...@sw...>:
> Hi all,
>    I am reading Modern C++ Design by Andrei Alexandrescu and already
> after the first few pages, I want to start work on 2geom that I've been
> thinking about for a while. Would like to hear your thoughts,
> encouragement or otherwise :-)
>
> The idea is to add template parameters to, e.g., Point.
> Right now, we hardcode the coordinate type Coord as double. But why not:
>      template<typename Coord = double>
>      class Point { ... };
> :) ?
> This will allow people to choose what precision they want. Perhaps this
> allows code sharing between Point and IntPoint. Note that with templated
> stuff, you can write methods that would not work with certain types
> without breaking compilation (unless you call such a method); this would
> allow exposing optional functionality depending on the template argument
> type.

I thought about this when I worked on the Point class and decided
against it, because expressing all the operations we need on point
classes in templates would require loads of arcane boilerplate. For
example, the conversion from IntPoint to Point should be implicit, but
the conversion from Point to IntPoint should be only possible through
functions such as round, ceil and floor. Also many operations, such as
normalization, don't make sense on IntPoint.

Furthermore, this would require changing many functions that take
Point to template functions taking Point<Coord>. We would effectively
need to lift most of 2Geom code into headers.

> Point<double> is just the start. My endgoal is to be able to choose
> Path<CubicBezier>: a path for which all functions know that it is just a
> vector with CubicBeziers, allowing SIMD optimization of many operations
> on it. Instead of the Path<Curve> that we have now, that does not allow
> for any of that.

This would be interesting. Path could also have a second parameter
specifying the underlying structure: vector, list or an
order-statistic tree.

Another interesting area of improvement would be to put the node-based
path representation from the node editor in 2Geom, though this would
need extra effort to decouple it from the display and event handling
code.

Regards, Krzysztof

Re: [Lib2geom-devel] Templates

[Vinícius d. S. O. <vin...@gm...>]

2014-06-15 20:12 GMT-03:00 Johan Engelen <jbc...@sw...>:

> Thanks for that idea. Do you know if there is a good reason for that
> design? Perhaps default template arguments are a bad idea / hinder future
> development?
>

The two are very alike.

The difference is when you type more. With the typedef solution, you'll
have to type more (the "basic_" prefix) when you want to write a generic
function. With the default type argument solution, you'll have to type more
when you want to write the common case and non-generic version (the "<>"
suffix).

https://gist.github.com/vinipsmaker/c277a3268c8a79ce8584

The idea was to allow you to refactor incrementally and still being able to
compile the code base. I haven't thought about the other implications.

I am a bit worried that it will hide functions that should be generalized
> to work with all kinds of Points, instead of just base_point<double>.
> Methods that are defined using Point will be template-specialized
> functions, and will not be available for base_point<float>; but I won't
> learn about them until some user complains that a certain obscure function
> is not available.
> Unfortunately, Inkscape is the only real (somewhat extensive) testcase
> that we have...
> I guess this is solved by a search for "Point" over the whole codebase,
> and changing it where necessary...
>

Yes, it'd "hide" functions that should be generalized, because they'd
continue to work. If you want to search these functions, you could also
remove the typedef and see the compiler errors. Then reintroduce the
typedef and refactor one more function and so on.


-- 
Vinícius dos Santos Oliveira
https://about.me/vinipsmaker

Re: [Lib2geom-devel] Templates

[Johan E. <jbc...@sw...>]

On 16-6-2014 0:06, Vinícius dos Santos Oliveira wrote:
> 2014-06-15 19:01 GMT-03:00 Johan Engelen <jbc...@sw... 
> <mailto:jbc...@sw...>>:
>
>     Would like to hear your thoughts,
>     encouragement or otherwise [...]
>
>
> Looks interesting.
>
> Why don't you create a new class, base_point and make point just a 
> typedef for base_point<double>? I think it'd break less code and speed 
> up refactoring. Also, it mirrors design found on the standard c++ 
> library itself (see basic_string and string, as an example).

Thanks for that idea. Do you know if there is a good reason for that 
design? Perhaps default template arguments are a bad idea / hinder 
future development?

I am a bit worried that it will hide functions that should be 
generalized to work with all kinds of Points, instead of just 
base_point<double>. Methods that are defined using Point will be 
template-specialized functions, and will not be available for 
base_point<float>; but I won't learn about them until some user 
complains that a certain obscure function is not available.
Unfortunately, Inkscape is the only real (somewhat extensive) testcase 
that we have...
I guess this is solved by a search for "Point" over the whole codebase, 
and changing it where necessary...

-Johan

Re: [Lib2geom-devel] Templates

[Vinícius d. S. O. <vin...@gm...>]

2014-06-15 19:01 GMT-03:00 Johan Engelen <jbc...@sw...>:

> Would like to hear your thoughts,
> encouragement or otherwise [...]
>

Looks interesting.

Why don't you create a new class, base_point and make point just a typedef
for base_point<double>? I think it'd break less code and speed up
refactoring. Also, it mirrors design found on the standard c++ library
itself (see basic_string and string, as an example).


-- 
Vinícius dos Santos Oliveira
https://about.me/vinipsmaker

[Lib2geom-devel] Templates

[Johan E. <jbc...@sw...>]

Hi all,
   I am reading Modern C++ Design by Andrei Alexandrescu and already 
after the first few pages, I want to start work on 2geom that I've been 
thinking about for a while. Would like to hear your thoughts, 
encouragement or otherwise :-)

The idea is to add template parameters to, e.g., Point.
Right now, we hardcode the coordinate type Coord as double. But why not:
     template<typename Coord = double>
     class Point { ... };
:) ?
This will allow people to choose what precision they want. Perhaps this 
allows code sharing between Point and IntPoint. Note that with templated 
stuff, you can write methods that would not work with certain types 
without breaking compilation (unless you call such a method); this would 
allow exposing optional functionality depending on the template argument 
type.

Point<double> is just the start. My endgoal is to be able to choose 
Path<CubicBezier>: a path for which all functions know that it is just a 
vector with CubicBeziers, allowing SIMD optimization of many operations 
on it. Instead of the Path<Curve> that we have now, that does not allow 
for any of that.

I am not sure this will improve performance, but I think it will be an 
interesting and challenging exercise to make lib2geom more general, and 
go beyond what it already can do.

regards,
   Johan

Re: [Lib2geom-devel] Intersection of parallel line segments

[Diederik v. L. <ma...@di...>]

Hi Nathan,

I haven't seen any difference in using a relative error over an absolute
error. Both fix the problem I was trying to tackle, likely because the
small errors we're talking about here are much smaller than what a user
would perceive as being zero (parallel) angles. Using the relative error
however should be more robust, and be safe over a much wider range of
length scales, provided that I implemented this correctly. You never know
what more this code will be used for.

I did notice though that the relative error as I calculate it now was
typically around 1e-13 to 1e-14, as opposed to the 1e-8 you estimated.
Still clueless about this though.

Diederik


On Sat, May 24, 2014 at 9:57 PM, Nathan Hurst <nj...@nj...> wrote:

> Did the relative error fix the problem?
>
> njh
>
> On Fri, May 23, 2014 at 11:31:22PM +0200, Diederik van Lierop wrote:
> > Hi Nathan and Johan,
> >
> > Thanks for your feedback! It has been incorporated in the patches I just
> > commited
> >
> > Kind regards,
> >
> > Diederik
> >
> >
> > On Thu, May 15, 2014 at 12:49 AM, Nathan Hurst <nj...@nj...> wrote:
> >
> > > I wonder whether it would work better if you used relative error
> > > rather than absolute?  Really what you're trying to do is put an error
> > > bound around the line and call lines parallel if their error windows
> > > overlap over the length of the segment.  The error bound for floating
> > > point is relative (typically 2^-23/-53 of the value).  This might be
> > > enough to make the problem go away.  Because the cross product is
> > > O(x^2) your relative error should be more like 2^-26 (1e-8) for double,
> > > I think.
> > >
> > > njh
> > >
> > >
> > > On Wed, May 14, 2014 at 11:06:10PM +0200, Johan Engelen wrote:
> > > > Hi Diederik,
> > > >   Great that you are working on this.
> > > > I can't judge the technical side too well. Some code style comments:
> > > > - remove / comment out the std::cout reporting
> > > > - can you add parenthesis in the final boolean expression (to not
> > > > rely on operator precedence)
> > > >
> > > > cheers,
> > > >   Johan
> > > >
> > > >
> > > > On 14-5-2014 21:03, Diederik van Lierop wrote:
> > > > >Hi everyone,
> > > > >
> > > > >When looking into this bug in Inkscape's measure tool:
> > > > >
> > > > >https://bugs.launchpad.net/inkscape/+bug/1022733
> > > > >
> > > > >I found out that intersecting two parallel line segments typically
> > > > >produces 50 - 100 crossings. This should either be zero or
> > > > >infinite (or maybe one if one line segment is just a point).
> > > > >
> > > > >The original code checked for a cross product being exactly zero
> > > > >as a measure for line segments being parallel, but that's
> > > > >obviously a bad idea. I've found the error to be < 1e-13, so I
> > > > >propose checking for a cross product of < 1e-12.
> > > > >
> > > > >This solves the bug I was trying to squash, but I'm not too
> > > > >familiar with the crossers code. If someone objects to this fix,
> > > > >then just speak up!
> > > > >
> > > > >Thanks,
> > > > >
> > > > >Diederik
> > > > >
> > > > >=== modified file 'src/2geom/path-intersection.cpp'
> > > > >--- src/2geom/path-intersection.cpp    2014-03-27 01:33:44 +0000
> > > > >+++ src/2geom/path-intersection.cpp    2014-05-14 18:47:54 +0000
> > > > >@@ -169,15 +169,21 @@
> > > > >           Bd = B1 - B0,
> > > > >            d = B0 - A0;
> > > > >     det = cross(Ad, Bd);
> > > > >-    if( 1.0 + det == 1.0 )
> > > > >-        return false;
> > > > >-    else
> > > > >-    {
> > > > >-        double detinv = 1.0 / det;
> > > > >-        tA = cross(d, Bd) * detinv;
> > > > >-        tB = cross(d, Ad) * detinv;
> > > > >-        return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> > > > >-    }
> > > > >+    if( fabs(det) < 1e-12 ) {// If the cross product is NEARLY
> zero,
> > > > >+        // Then one of the linesegments might have length zero
> > > > >+        if (!are_near(A0, A1) && !are_near(B0, B1)) {
> > > > >+            // If that's not the case, then we must have either:
> > > > >+            // - parallel lines, with no intersections, or
> > > > >+            // - coincident lines, with an infinite number of
> > > > >intersections
> > > > >+            // Either is quite useless, so we'll just bail out
> > > > >+            return false;
> > > > >+        } // Else, one of the linesegments is zero, and we might
> > > > >still find a single intersection point
> > > > >+    } // Else we haven't bailed out, and we'll try to calculate
> > > > >the intersections
> > > > >+    std::cout << "det = cross = " << det << std::endl;
> > > > >+    double detinv = 1.0 / det;
> > > > >+    tA = cross(d, Bd) * detinv;
> > > > >+    tB = cross(d, Ad) * detinv;
> > > > >+    return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> > > > > }
> > > > >
> > > > >
> > > > >
> > > > >
> > > >
> > >
> >------------------------------------------------------------------------------
> > > > >"Accelerate Dev Cycles with Automated Cross-Browser Testing - For
> FREE
> > > > >Instantly run your Selenium tests across 300+ browser/OS combos.
> > > > >Get unparalleled scalability from the best Selenium testing platform
> > > available
> > > > >Simple to use. Nothing to install. Get started now for free."
> > > > >http://p.sf.net/sfu/SauceLabs
> > > > >
> > > > >
> > > > >_______________________________________________
> > > > >Lib2geom-devel mailing list
> > > > >Lib...@li...
> > > > >https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> > > >
> > >
> > > >
> > >
> ------------------------------------------------------------------------------
> > > > "Accelerate Dev Cycles with Automated Cross-Browser Testing - For
> FREE
> > > > Instantly run your Selenium tests across 300+ browser/OS combos.
> > > > Get unparalleled scalability from the best Selenium testing platform
> > > available
> > > > Simple to use. Nothing to install. Get started now for free."
> > > > http://p.sf.net/sfu/SauceLabs
> > >
> > > > _______________________________________________
> > > > Lib2geom-devel mailing list
> > > > Lib...@li...
> > > > https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> > >
> > >
> > >
> > >
> ------------------------------------------------------------------------------
> > > "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> > > Instantly run your Selenium tests across 300+ browser/OS combos.
> > > Get unparalleled scalability from the best Selenium testing platform
> > > available
> > > Simple to use. Nothing to install. Get started now for free."
> > > http://p.sf.net/sfu/SauceLabs
> > > _______________________________________________
> > > Lib2geom-devel mailing list
> > > Lib...@li...
> > > https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> > >
>

Re: [Lib2geom-devel] Intersection of parallel line segments

[Nathan H. <nj...@nj...>]

Did the relative error fix the problem?

njh

On Fri, May 23, 2014 at 11:31:22PM +0200, Diederik van Lierop wrote:
> Hi Nathan and Johan,
> 
> Thanks for your feedback! It has been incorporated in the patches I just
> commited
> 
> Kind regards,
> 
> Diederik
> 
> 
> On Thu, May 15, 2014 at 12:49 AM, Nathan Hurst <nj...@nj...> wrote:
> 
> > I wonder whether it would work better if you used relative error
> > rather than absolute?  Really what you're trying to do is put an error
> > bound around the line and call lines parallel if their error windows
> > overlap over the length of the segment.  The error bound for floating
> > point is relative (typically 2^-23/-53 of the value).  This might be
> > enough to make the problem go away.  Because the cross product is
> > O(x^2) your relative error should be more like 2^-26 (1e-8) for double,
> > I think.
> >
> > njh
> >
> >
> > On Wed, May 14, 2014 at 11:06:10PM +0200, Johan Engelen wrote:
> > > Hi Diederik,
> > >   Great that you are working on this.
> > > I can't judge the technical side too well. Some code style comments:
> > > - remove / comment out the std::cout reporting
> > > - can you add parenthesis in the final boolean expression (to not
> > > rely on operator precedence)
> > >
> > > cheers,
> > >   Johan
> > >
> > >
> > > On 14-5-2014 21:03, Diederik van Lierop wrote:
> > > >Hi everyone,
> > > >
> > > >When looking into this bug in Inkscape's measure tool:
> > > >
> > > >https://bugs.launchpad.net/inkscape/+bug/1022733
> > > >
> > > >I found out that intersecting two parallel line segments typically
> > > >produces 50 - 100 crossings. This should either be zero or
> > > >infinite (or maybe one if one line segment is just a point).
> > > >
> > > >The original code checked for a cross product being exactly zero
> > > >as a measure for line segments being parallel, but that's
> > > >obviously a bad idea. I've found the error to be < 1e-13, so I
> > > >propose checking for a cross product of < 1e-12.
> > > >
> > > >This solves the bug I was trying to squash, but I'm not too
> > > >familiar with the crossers code. If someone objects to this fix,
> > > >then just speak up!
> > > >
> > > >Thanks,
> > > >
> > > >Diederik
> > > >
> > > >=== modified file 'src/2geom/path-intersection.cpp'
> > > >--- src/2geom/path-intersection.cpp    2014-03-27 01:33:44 +0000
> > > >+++ src/2geom/path-intersection.cpp    2014-05-14 18:47:54 +0000
> > > >@@ -169,15 +169,21 @@
> > > >           Bd = B1 - B0,
> > > >            d = B0 - A0;
> > > >     det = cross(Ad, Bd);
> > > >-    if( 1.0 + det == 1.0 )
> > > >-        return false;
> > > >-    else
> > > >-    {
> > > >-        double detinv = 1.0 / det;
> > > >-        tA = cross(d, Bd) * detinv;
> > > >-        tB = cross(d, Ad) * detinv;
> > > >-        return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> > > >-    }
> > > >+    if( fabs(det) < 1e-12 ) {// If the cross product is NEARLY zero,
> > > >+        // Then one of the linesegments might have length zero
> > > >+        if (!are_near(A0, A1) && !are_near(B0, B1)) {
> > > >+            // If that's not the case, then we must have either:
> > > >+            // - parallel lines, with no intersections, or
> > > >+            // - coincident lines, with an infinite number of
> > > >intersections
> > > >+            // Either is quite useless, so we'll just bail out
> > > >+            return false;
> > > >+        } // Else, one of the linesegments is zero, and we might
> > > >still find a single intersection point
> > > >+    } // Else we haven't bailed out, and we'll try to calculate
> > > >the intersections
> > > >+    std::cout << "det = cross = " << det << std::endl;
> > > >+    double detinv = 1.0 / det;
> > > >+    tA = cross(d, Bd) * detinv;
> > > >+    tB = cross(d, Ad) * detinv;
> > > >+    return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> > > > }
> > > >
> > > >
> > > >
> > > >
> > >
> > >------------------------------------------------------------------------------
> > > >"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> > > >Instantly run your Selenium tests across 300+ browser/OS combos.
> > > >Get unparalleled scalability from the best Selenium testing platform
> > available
> > > >Simple to use. Nothing to install. Get started now for free."
> > > >http://p.sf.net/sfu/SauceLabs
> > > >
> > > >
> > > >_______________________________________________
> > > >Lib2geom-devel mailing list
> > > >Lib...@li...
> > > >https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> > >
> >
> > >
> > ------------------------------------------------------------------------------
> > > "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> > > Instantly run your Selenium tests across 300+ browser/OS combos.
> > > Get unparalleled scalability from the best Selenium testing platform
> > available
> > > Simple to use. Nothing to install. Get started now for free."
> > > http://p.sf.net/sfu/SauceLabs
> >
> > > _______________________________________________
> > > Lib2geom-devel mailing list
> > > Lib...@li...
> > > https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> >
> >
> >
> > ------------------------------------------------------------------------------
> > "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> > Instantly run your Selenium tests across 300+ browser/OS combos.
> > Get unparalleled scalability from the best Selenium testing platform
> > available
> > Simple to use. Nothing to install. Get started now for free."
> > http://p.sf.net/sfu/SauceLabs
> > _______________________________________________
> > Lib2geom-devel mailing list
> > Lib...@li...
> > https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> >

Re: [Lib2geom-devel] Intersection of parallel line segments

[Diederik v. L. <ma...@di...>]

Hi Nathan and Johan,

Thanks for your feedback! It has been incorporated in the patches I just
commited

Kind regards,

Diederik


On Thu, May 15, 2014 at 12:49 AM, Nathan Hurst <nj...@nj...> wrote:

> I wonder whether it would work better if you used relative error
> rather than absolute?  Really what you're trying to do is put an error
> bound around the line and call lines parallel if their error windows
> overlap over the length of the segment.  The error bound for floating
> point is relative (typically 2^-23/-53 of the value).  This might be
> enough to make the problem go away.  Because the cross product is
> O(x^2) your relative error should be more like 2^-26 (1e-8) for double,
> I think.
>
> njh
>
>
> On Wed, May 14, 2014 at 11:06:10PM +0200, Johan Engelen wrote:
> > Hi Diederik,
> >   Great that you are working on this.
> > I can't judge the technical side too well. Some code style comments:
> > - remove / comment out the std::cout reporting
> > - can you add parenthesis in the final boolean expression (to not
> > rely on operator precedence)
> >
> > cheers,
> >   Johan
> >
> >
> > On 14-5-2014 21:03, Diederik van Lierop wrote:
> > >Hi everyone,
> > >
> > >When looking into this bug in Inkscape's measure tool:
> > >
> > >https://bugs.launchpad.net/inkscape/+bug/1022733
> > >
> > >I found out that intersecting two parallel line segments typically
> > >produces 50 - 100 crossings. This should either be zero or
> > >infinite (or maybe one if one line segment is just a point).
> > >
> > >The original code checked for a cross product being exactly zero
> > >as a measure for line segments being parallel, but that's
> > >obviously a bad idea. I've found the error to be < 1e-13, so I
> > >propose checking for a cross product of < 1e-12.
> > >
> > >This solves the bug I was trying to squash, but I'm not too
> > >familiar with the crossers code. If someone objects to this fix,
> > >then just speak up!
> > >
> > >Thanks,
> > >
> > >Diederik
> > >
> > >=== modified file 'src/2geom/path-intersection.cpp'
> > >--- src/2geom/path-intersection.cpp    2014-03-27 01:33:44 +0000
> > >+++ src/2geom/path-intersection.cpp    2014-05-14 18:47:54 +0000
> > >@@ -169,15 +169,21 @@
> > >           Bd = B1 - B0,
> > >            d = B0 - A0;
> > >     det = cross(Ad, Bd);
> > >-    if( 1.0 + det == 1.0 )
> > >-        return false;
> > >-    else
> > >-    {
> > >-        double detinv = 1.0 / det;
> > >-        tA = cross(d, Bd) * detinv;
> > >-        tB = cross(d, Ad) * detinv;
> > >-        return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> > >-    }
> > >+    if( fabs(det) < 1e-12 ) {// If the cross product is NEARLY zero,
> > >+        // Then one of the linesegments might have length zero
> > >+        if (!are_near(A0, A1) && !are_near(B0, B1)) {
> > >+            // If that's not the case, then we must have either:
> > >+            // - parallel lines, with no intersections, or
> > >+            // - coincident lines, with an infinite number of
> > >intersections
> > >+            // Either is quite useless, so we'll just bail out
> > >+            return false;
> > >+        } // Else, one of the linesegments is zero, and we might
> > >still find a single intersection point
> > >+    } // Else we haven't bailed out, and we'll try to calculate
> > >the intersections
> > >+    std::cout << "det = cross = " << det << std::endl;
> > >+    double detinv = 1.0 / det;
> > >+    tA = cross(d, Bd) * detinv;
> > >+    tB = cross(d, Ad) * detinv;
> > >+    return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> > > }
> > >
> > >
> > >
> > >
> >
> >------------------------------------------------------------------------------
> > >"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> > >Instantly run your Selenium tests across 300+ browser/OS combos.
> > >Get unparalleled scalability from the best Selenium testing platform
> available
> > >Simple to use. Nothing to install. Get started now for free."
> > >http://p.sf.net/sfu/SauceLabs
> > >
> > >
> > >_______________________________________________
> > >Lib2geom-devel mailing list
> > >Lib...@li...
> > >https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> >
>
> >
> ------------------------------------------------------------------------------
> > "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> > Instantly run your Selenium tests across 300+ browser/OS combos.
> > Get unparalleled scalability from the best Selenium testing platform
> available
> > Simple to use. Nothing to install. Get started now for free."
> > http://p.sf.net/sfu/SauceLabs
>
> > _______________________________________________
> > Lib2geom-devel mailing list
> > Lib...@li...
> > https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform
> available
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>

Re: [Lib2geom-devel] Intersection of parallel line segments

[Nathan H. <nj...@nj...>]

I wonder whether it would work better if you used relative error
rather than absolute?  Really what you're trying to do is put an error
bound around the line and call lines parallel if their error windows
overlap over the length of the segment.  The error bound for floating
point is relative (typically 2^-23/-53 of the value).  This might be
enough to make the problem go away.  Because the cross product is
O(x^2) your relative error should be more like 2^-26 (1e-8) for double,
I think.

njh


On Wed, May 14, 2014 at 11:06:10PM +0200, Johan Engelen wrote:
> Hi Diederik,
>   Great that you are working on this.
> I can't judge the technical side too well. Some code style comments:
> - remove / comment out the std::cout reporting
> - can you add parenthesis in the final boolean expression (to not
> rely on operator precedence)
> 
> cheers,
>   Johan
> 
> 
> On 14-5-2014 21:03, Diederik van Lierop wrote:
> >Hi everyone,
> >
> >When looking into this bug in Inkscape's measure tool:
> >
> >https://bugs.launchpad.net/inkscape/+bug/1022733
> >
> >I found out that intersecting two parallel line segments typically
> >produces 50 - 100 crossings. This should either be zero or
> >infinite (or maybe one if one line segment is just a point).
> >
> >The original code checked for a cross product being exactly zero
> >as a measure for line segments being parallel, but that's
> >obviously a bad idea. I've found the error to be < 1e-13, so I
> >propose checking for a cross product of < 1e-12.
> >
> >This solves the bug I was trying to squash, but I'm not too
> >familiar with the crossers code. If someone objects to this fix,
> >then just speak up!
> >
> >Thanks,
> >
> >Diederik
> >
> >=== modified file 'src/2geom/path-intersection.cpp'
> >--- src/2geom/path-intersection.cpp    2014-03-27 01:33:44 +0000
> >+++ src/2geom/path-intersection.cpp    2014-05-14 18:47:54 +0000
> >@@ -169,15 +169,21 @@
> >           Bd = B1 - B0,
> >            d = B0 - A0;
> >     det = cross(Ad, Bd);
> >-    if( 1.0 + det == 1.0 )
> >-        return false;
> >-    else
> >-    {
> >-        double detinv = 1.0 / det;
> >-        tA = cross(d, Bd) * detinv;
> >-        tB = cross(d, Ad) * detinv;
> >-        return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> >-    }
> >+    if( fabs(det) < 1e-12 ) {// If the cross product is NEARLY zero,
> >+        // Then one of the linesegments might have length zero
> >+        if (!are_near(A0, A1) && !are_near(B0, B1)) {
> >+            // If that's not the case, then we must have either:
> >+            // - parallel lines, with no intersections, or
> >+            // - coincident lines, with an infinite number of
> >intersections
> >+            // Either is quite useless, so we'll just bail out
> >+            return false;
> >+        } // Else, one of the linesegments is zero, and we might
> >still find a single intersection point
> >+    } // Else we haven't bailed out, and we'll try to calculate
> >the intersections
> >+    std::cout << "det = cross = " << det << std::endl;
> >+    double detinv = 1.0 / det;
> >+    tA = cross(d, Bd) * detinv;
> >+    tB = cross(d, Ad) * detinv;
> >+    return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> > }
> >
> >
> >
> >
> >------------------------------------------------------------------------------
> >"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> >Instantly run your Selenium tests across 300+ browser/OS combos.
> >Get unparalleled scalability from the best Selenium testing platform available
> >Simple to use. Nothing to install. Get started now for free."
> >http://p.sf.net/sfu/SauceLabs
> >
> >
> >_______________________________________________
> >Lib2geom-devel mailing list
> >Lib...@li...
> >https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> 

> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform available
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs

> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

Re: [Lib2geom-devel] Intersection of parallel line segments

[Johan E. <jbc...@sw...>]

Hi Diederik,
   Great that you are working on this.
I can't judge the technical side too well. Some code style comments:
- remove / comment out the std::cout reporting
- can you add parenthesis in the final boolean expression (to not rely 
on operator precedence)

cheers,
   Johan


On 14-5-2014 21:03, Diederik van Lierop wrote:
> Hi everyone,
>
> When looking into this bug in Inkscape's measure tool:
>
> https://bugs.launchpad.net/inkscape/+bug/1022733
>
> I found out that intersecting two parallel line segments typically 
> produces 50 - 100 crossings. This should either be zero or infinite 
> (or maybe one if one line segment is just a point).
>
> The original code checked for a cross product being exactly zero as a 
> measure for line segments being parallel, but that's obviously a bad 
> idea. I've found the error to be < 1e-13, so I propose checking for a 
> cross product of < 1e-12.
>
> This solves the bug I was trying to squash, but I'm not too familiar 
> with the crossers code. If someone objects to this fix, then just 
> speak up!
>
> Thanks,
>
> Diederik
>
> === modified file 'src/2geom/path-intersection.cpp'
> --- src/2geom/path-intersection.cpp    2014-03-27 01:33:44 +0000
> +++ src/2geom/path-intersection.cpp    2014-05-14 18:47:54 +0000
> @@ -169,15 +169,21 @@
>            Bd = B1 - B0,
>             d = B0 - A0;
>      det = cross(Ad, Bd);
> -    if( 1.0 + det == 1.0 )
> -        return false;
> -    else
> -    {
> -        double detinv = 1.0 / det;
> -        tA = cross(d, Bd) * detinv;
> -        tB = cross(d, Ad) * detinv;
> -        return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
> -    }
> +    if( fabs(det) < 1e-12 ) {// If the cross product is NEARLY zero,
> +        // Then one of the linesegments might have length zero
> +        if (!are_near(A0, A1) && !are_near(B0, B1)) {
> +            // If that's not the case, then we must have either:
> +            // - parallel lines, with no intersections, or
> +            // - coincident lines, with an infinite number of 
> intersections
> +            // Either is quite useless, so we'll just bail out
> +            return false;
> +        } // Else, one of the linesegments is zero, and we might 
> still find a single intersection point
> +    } // Else we haven't bailed out, and we'll try to calculate the 
> intersections
> +    std::cout << "det = cross = " << det << std::endl;
> +    double detinv = 1.0 / det;
> +    tA = cross(d, Bd) * detinv;
> +    tB = cross(d, Ad) * detinv;
> +    return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
>  }
>
>
>
>
> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform available
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs
>
>
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel

[Lib2geom-devel] Intersection of parallel line segments

[Diederik v. L. <ma...@di...>]

Hi everyone,

When looking into this bug in Inkscape's measure tool:

https://bugs.launchpad.net/inkscape/+bug/1022733

I found out that intersecting two parallel line segments typically produces
50 - 100 crossings. This should either be zero or infinite (or maybe one if
one line segment is just a point).

The original code checked for a cross product being exactly zero as a
measure for line segments being parallel, but that's obviously a bad idea.
I've found the error to be < 1e-13, so I propose checking for a cross
product of < 1e-12.

This solves the bug I was trying to squash, but I'm not too familiar with
the crossers code. If someone objects to this fix, then just speak up!

Thanks,

Diederik

=== modified file 'src/2geom/path-intersection.cpp'
--- src/2geom/path-intersection.cpp    2014-03-27 01:33:44 +0000
+++ src/2geom/path-intersection.cpp    2014-05-14 18:47:54 +0000
@@ -169,15 +169,21 @@
           Bd = B1 - B0,
            d = B0 - A0;
     det = cross(Ad, Bd);
-    if( 1.0 + det == 1.0 )
-        return false;
-    else
-    {
-        double detinv = 1.0 / det;
-        tA = cross(d, Bd) * detinv;
-        tB = cross(d, Ad) * detinv;
-        return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
-    }
+    if( fabs(det) < 1e-12 ) {// If the cross product is NEARLY zero,
+        // Then one of the linesegments might have length zero
+        if (!are_near(A0, A1) && !are_near(B0, B1)) {
+            // If that's not the case, then we must have either:
+            // - parallel lines, with no intersections, or
+            // - coincident lines, with an infinite number of intersections
+            // Either is quite useless, so we'll just bail out
+            return false;
+        } // Else, one of the linesegments is zero, and we might still
find a single intersection point
+    } // Else we haven't bailed out, and we'll try to calculate the
intersections
+    std::cout << "det = cross = " << det << std::endl;
+    double detinv = 1.0 / det;
+    tA = cross(d, Bd) * detinv;
+    tB = cross(d, Ad) * detinv;
+    return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
 }

Re: [Lib2geom-devel] [Inkscape-devel] Help with numpy.linalg.solve

[Nathan H. <nj...@nj...>]

On Fri, Apr 11, 2014 at 12:34:38PM +0100, Alex Valavanis wrote:
> Armadillo supports eigenvalue searches in sparse matrices (although you can
> only get selected eigenvalues) but doesn't support sparse matrix inversions
> yet.

I don't think anyone does sparse exact inversion - too much infill.
It's an interesting question what eps approximate sparse inverses
there are, the rank-k inverse made using the sparse svd algorithms
would be the L2 solution (USV -> V^T (1/S) U^T).  But there are
possibly better choices (e.g. L1).  I don't know if there are any
eps inverses which are not outer products.

(yes, for 3x3 a dense inverse is fine.)

njh