Lines

[sjkelly]

@skariel thank you for publishing this package. I am really excited about contributing some additional algorithms and features. I would like to work on adding support for Line primitives. Do you think adding orientation (http://www.cs.cmu.edu/~quake/robust.html) and line intersections would be good to have in this package? I am currently dealing with a lot of geometry code that has floating point error and this package might help.

[skariel]

Orientation is already implemented, exactly as in the J. R. Shewchuk page you linked to. For example, lets test where point c lies with respect to vector ab:

using GeometricalPredicates

a = Point(1.1, 1.1)
b = Point(1.5, 1.5)
c = Point(1.4, 1.6)

t = Primitive(a, b, c)
println(orientation(t)) # ---> 1, c lies to the left

setc(t, Point(1.4,1.05))
println(orientation(t)) # ---> -1, c lies to the right

setc(t, Point(1.4,1.4))
println(orientation(t)) # --> 0, c is exactly on the line

I think otherwise line intersections are not subject to robustness issues. I would like to add missing functionality, PRs (and bug reports) are welcome; I'll also help implementing :)

What specific features do you have in mind?

[sjkelly]

This is great, thanks! Somehow I missed this. I kind of imagined creating a line primitive as

a = Point(1.1, 1.1)
b = Point(1.5, 1.5)

t = Primitive(a, b)

I could then call orientation with any point, like orientation(t, Point(1.4, 1.6). This seems to be a little more intuitive to me.

You are correct that line intersections do not suffer from robustness issues, so I don't believe this should not be included here.

I have been working on implementing a planar geometry library (set theoretic operations on polygons, polyline clipping, reflex vertex detection, etc....). I am imagining the library being able to scale points down to use this library when necessary (e.g. during reflex vertex detection in polygons).

I plan on publishing it soon. Unfortunately it has been in a constant state of flux as it is tied to the needs of the application we are developing. I don't feel comfortable releasing until the API has stabilized. However I am the maintainer of Meshes.jl, and I think there are some interesting things we could use from this library.

[skariel]

Good point about the api, I'll implement that

[skariel]

Done, see how to use in the bottom of the predicates section in README.md here

The line is not currently a primitive, just a convenience api. The problem is that primitives are mutable and I would like the line to be immutable. So maybe we need mutablePrimitive and immutablePrimitive abstract types. I'll open a different issue for that