Writing a book on geometry, need some feedback

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

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

// 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; }

Комментарии (15)

Написать комментарий?

dalex

7 лет назад, # |

+29

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.

→ Ответить

vlecomte

7 лет назад, # ^ |

← Rev. 2 →

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. :)

yeputons

+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.

Tutis

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

Siriuslight

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. :)

bhishma

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

splucs

6 лет назад, # |

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

6 лет назад, # ^ |

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

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

Chilli

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.

+10

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).

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})
}

+13

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

Back with another one :)

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

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;
}

Should be fixed now, thanks a lot. :)

Блог пользователя vlecomte