vlecomte's blog

Writing a book on geometry, need some feedback
By vlecomte, 7 years ago, In English

Hello!

I'm writing a book on geometry with a competitive programming approach. I've just started, so I haven't written much at all yet but I'd like to have some early feedback.

My goal is to be easy to understand and practical (quite code-oriented), but also to explain important concepts in depth and try to build intuitions / interesting interpretations, because I think I can bring some things on that front. In what I've written I feel like the "in depth" part is okay but I'm afraid the "easy to understand" part is a bit lacking.

So far I've covered complex numbers, point representation, dot product, cross products and their applications, as the first part of a "Basics" chapter. There will eventually be other chapters, covering things like sweep algorithms, algorithms on convex polygons/hulls, and especially 3D geometry, which I like a lot.

I'd like to have feedback mostly on writing style and on ways in which I can make the explanations more accessible (e.g. adding examples, figures, rephrasing, etc.), but any comment or suggested improvement is welcome. I know I've not written much but there are some concepts in there which I found tricky to explain, so there should be plenty to criticize. :)

Here's the link (I'll update it as I fix things and add sections): https://vlecomte.github.io/cp-geo.pdf

  • Vote: I like it
  • +110
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Don't use complex. The book should not depend on some specific classes in standard library in one specific language. Write your own class Point and continue with it.

(conj(v)*w).Y; what the f*ck is it? Millions of people know the formula v.x * w.y - v.y * w.x and you introduce new unclear and not understandable from the first sight expression.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    That's a good point. At the moment I'm writing this like it's a blown-out ICPC cheatsheet and it's making things less clear. I think I'll take your advice and create a point class but keep mentioning C++ hacks as asides. :)

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    +1 for not using complex. It can also be much slower than a manually implemented structure because complex may be based on complex numbers from C which use some library calls for all operations, which prevents inlining. They also try to handle some cases like NaNs and stuff; that decreases speed as well.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem for use of complex numbers and cross product: https://icpc.kattis.com/problems/airport

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I am not eligible to give you any suggestion, but I must say, you are doing a great job. Keep going on. I would be waiting for the book. :)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be really great if we had problems to practice/test our code for each topic in the book.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On page 18, the solution to the quadratic equation is x = 1, not x = 0. Great material by the way. Reading all the way.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On page 16, I think you meant log_2(n) instead of log_2(k).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot, those errors will be fixed next time I recompile the whole book. :)

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a list of topics you're planning on covering eventually? So far, it's been extremely useful, but has been mostly limited to elementary operations.

I know that you created a contest and you're going to put the topics covered in the problems in the contest, but I was just curious if you have a full list.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I don't really have a full list. The plan is to eventually cover everything geometrical that can be useful in CP, but that's not going to happen any time soon at my current speed. ^^

    Right now I'm writing the chapter on 3D geometry and will also write a section on how to compute areas/volumes given a parametric representation of their boundaries (like in problem "Polar map"). After that my next goal is to have a chapter on all the techniques revolving around convex polygons (but I don't know when I'll have the time).

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

I'm going through and trying out the templates in the book, and I'm keeping a running list of typos. I think most of these are due to the fact that you probably wrote the rest of the book using complex numbers as your point and not the custom struct implementation, but I think it's best for most of the book to be switchable between the two.

I haven't looked at the 3d geometry section yet.

In 2.2.4, the line here, you have to construct the struct with braces, not parentheses. pt pq = q-p, num(cross(pq, fq-fp), dot(pq, fq-fp));

In 2.4.8, the double needs to be on the right hand side of the multiply in order to use the user defined multiply operator for pts. return {l2.v/abs(l2.v) + sign * l1.v/abs(l1.v),l2.c/abs(l2.v) + sign * l1.c/abs(l1.v)};

In 2.5.2, you put the points in a set. However, as you don't define a comparator for the points by default, this fails. I think you should either remark that you need to define a comparator here or use a vector.

In 2.7.5, you're missing a brace in the last for, as well as a semicolon. Also, you should probably remove your macro specific stuff (the V and the pb), since you don't use it anywhere else in the book.

for (int sign : {-1,1})
pt v = (d*dr + perp(d)*sqrt(h2)*sign)/d2;
out.pb({o1 + v*r1, o2 + v*r2})
}
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thank you, I will fix those issues ASAP! :)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Back with another one :)

      In 2.6.2, for the inPolygon function, you define things like so:

      // true if P at least as high as A (blue part)
bool half(pt a, pt p) {
return p.y >= a.y;
}
// check if [PQ] crosses ray from A
bool crossesRay(pt a, pt p, pt q) {
return (half(q) - half(p)) * orient(a,p,q) > 0;
}

      However, half (as defined here) actually takes 2 arguments. I missed it at first because you also defined a half elsewhere that only takes one argument (perhaps it's worth renaming them).

      I think it should actually be:

      // check if [PQ] crosses ray from A
bool crossesRay(pt a, pt p, pt q) {
return (half(q, a) - half(p, a)) * orient(a,p,q) > 0;
}
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Should be fixed now, thanks a lot. :)

        → Reply