1. Casey Duncan
  2. planar

Commits

Casey Duncan  committed 959ca61

More wip LineSegment in C

  • Participants
  • Parent commits 9be14ba
  • Branches default

Comments (0)

Files changed (4)

File MANIFEST.in

View file
  • Ignore whitespace
 recursive-include doc *
 
 prune **/.hg
-prune doc/build/doctest/
-prune doc/build/doctrees/
+prune doc/build/doctest
+prune doc/build/doctrees
 global-exclude *.pyc 
 global-exclude *.pyo
 global-exclude *.o

File lib/planar/cline.c

View file
  • Ignore whitespace
             if (L > PLANAR_EPSILON2) break;
         }
         if (L < PLANAR_EPSILON2) goto tooShort;
-        while (++i < size) {
+        while (++i < Py_SIZE(points)) {
             d = (vec[i].x - x) * dy + (vec[i].y - y) * -dx;
             if (!almost_eq(d, 0.0)) {
                 goto notCollinear;
     }
     px -= self->anchor.x;
     py -= self->anchor.y;
-    if (px * -self->normal.y + py * self->normal.x > -PLANAR_EPSILON) {
+    if (px * -self->normal.y + py * self->normal.x >= 0.0) {
         /* point beside ray */
         return PyFloat_FromDouble(
             fabs(px * self->normal.x + py * self->normal.y));
     {NULL}
 };
 
+/* Methods */
+
+static PlanarLineObject *
+Segment_new_from_normal(PyTypeObject *type, PyObject *args)
+{
+    PlanarLineObject *line;
+    PyObject *normal_arg;
+    double offset, start_dist, end_dist;
+
+    assert(PyType_IsSubtype(type, &PlanarSegmentType));
+    if (!PyArg_ParseTuple(args, "Oddd:LineSegment.from_normal", 
+        &normal_arg, &offset, &start_dist, &end_dist)) {
+        return NULL;
+    }
+    line = (PlanarLineObject *)type->tp_alloc(type, 0);
+    if (line == NULL) {
+        return NULL;
+    }
+    if (Line_set_normal(line, normal_arg, NULL) == -1) {
+        Py_DECREF(line);
+        return NULL;
+    }
+    line->anchor.x = line->normal.x * offset + start_dist * -line->normal.y;
+    line->anchor.y = line->normal.y * offset + start_dist * line->normal.x;
+    line->length = end_dist - start_dist;
+    return line;
+}
+
+static PlanarLineObject *
+Segment_new_from_points(PyTypeObject *type, PyObject *points) 
+{
+    PlanarLineObject *line;
+    planar_vec2_t *vec, p1, p2;
+    Py_ssize_t size;
+    int i;
+    double furthest = 0.0;
+    double x, y, d, L;
+    double dx = 0.0;
+    double dy = 0.0;
+    double sx = 0.0;
+    double sy = 0.0;
+
+    assert(PyType_IsSubtype(type, &PlanarSegmentType));
+    line = (PlanarLineObject *)type->tp_alloc(type, 0);
+    if (line == NULL) {
+        return NULL;
+    }
+
+    if (PlanarSeq2_Check(points)) {
+        /* Optimized code path for Seq2 objects */
+        if (Py_SIZE(points) == 0) {
+            goto tooShort;
+        }
+        vec = ((PlanarSeq2Object *)points)->vec;
+        x = vec[0].x;
+        y = vec[0].y;
+        for (i = 1; i < Py_SIZE(points); ++i) {
+            dx = vec[i].x - x;
+            dy = vec[i].y - y;
+            if (!almost_eq(dx*sx + dy*sy, 0.0)) {
+                goto notCollinear;
+            }
+            L = dx*dx + dy*dy;
+            if (L > furthest) {
+                furthest = L;
+                sx = dy;
+                sy = -dx;
+            }
+        }
+    } else {
+        points = PySequence_Fast(points, "expected iterable of Vec2 objects");
+        if (points == NULL) {
+            return NULL;
+        }
+        size = PySequence_Fast_GET_SIZE(points);
+        if (Py_SIZE(points) == 0) {
+            Py_DECREF(points);
+            goto tooShort;
+        }
+        if (!PlanarVec2_Parse(PySequence_Fast_GET_ITEM(points, 0), &x, &y)) {
+            Py_DECREF(points);
+            goto wrongType;
+        }
+        for (i = 1; i < size; ++i) {
+            if (!PlanarVec2_Parse(
+                PySequence_Fast_GET_ITEM(points, i), &dx, &dy)) {
+                Py_DECREF(points);
+                goto wrongType;
+            }
+            dx -= x;
+            dy -= y;
+            if (!almost_eq(dx*sx + dy*sy, 0.0)) {
+                Py_DECREF(points);
+                goto notCollinear;
+            }
+            L = dx*dx + dy*dy;
+            if (L > furthest) {
+                furthest = L;
+                sx = dy;
+                sy = -dx;
+            }
+        }
+        Py_DECREF(points);
+    }
+    line->anchor.x = x;
+    line->anchor.y = y;
+    L = sqrt(furthest);
+    line->length = L;
+    if (L > 0.0) {
+        line->normal.x = sx / L;
+        line->normal.y = sy / L;
+    } else {
+        line->normal.x = 0.0;
+        line->normal.y = -1.0;
+    }
+    return line;
+
+wrongType:
+    PyErr_SetString(PyExc_TypeError, "expected iterable of Vec2 objects");
+    Py_DECREF(line);
+    return NULL;
+tooShort:
+    PyErr_SetString(PyExc_ValueError,
+        "Expected iterable of 1 or more points");
+    Py_DECREF(line);
+    return NULL;
+notCollinear:
+    PyErr_SetString(PyExc_ValueError, "All points provided must be collinear");
+    Py_DECREF(line);
+    return NULL;
+}
+
+static PyObject *
+Segment_distance_to(PlanarLineObject *self, PyObject *pt)
+{
+    double px, py, dx, dy, along, d;
+
+    assert(PlanarSegment_Check(self));
+    if (!PlanarVec2_Parse(pt, &px, &py)) {
+        return NULL;
+    }
+    dx = px - self->anchor.x;
+    dy = py - self->anchor.y;
+    along = dx * -self->normal.y + dy * self->normal.x;
+    if (along < 0.0) {
+        /* point behind */
+        return PyFloat_FromDouble(sqrt(dx*dx + dy*dy));
+    } else if (along > self->length) {
+        /* point ahead */
+        dx = px - (self->anchor.x + -self->normal.y * self->length); 
+        dy = py - (self->anchor.y + self->normal.x * self->length);
+        return PyFloat_FromDouble(sqrt(dx*dx + dy*dy));
+    } else {
+        /* point beside */
+        return PyFloat_FromDouble(
+            fabs(dx * self->normal.x + dy * self->normal.y));
+    }
+}
+
+static PyObject *
+Segment_point_ahead(PlanarLineObject *self, PyObject *pt)
+{
+    double px, py, d;
+
+    assert(PlanarSegment_Check(self));
+    if (!PlanarVec2_Parse(pt, &px, &py)) {
+        return NULL;
+    }
+    px -= self->anchor.x;
+    py -= self->anchor.y;
+    d = px * -self->normal.y + py * self->normal.x;
+    return Py_BOOL(d >= self->length + PLANAR_EPSILON);
+}
+
+static PyObject *
+Segment_point_behind(PlanarLineObject *self, PyObject *pt)
+{
+    double px, py, d;
+
+    assert(PlanarSegment_Check(self));
+    if (!PlanarVec2_Parse(pt, &px, &py)) {
+        return NULL;
+    }
+    px -= self->anchor.x;
+    py -= self->anchor.y;
+    d = px * -self->normal.y + py * self->normal.x;
+    return Py_BOOL(d <= -PLANAR_EPSILON);
+}
+
+static PyObject *
+Segment_point_left(PlanarLineObject *self, PyObject *pt)
+{
+    double px, py, b, d;
+
+    assert(PlanarSegment_Check(self));
+    if (!PlanarVec2_Parse(pt, &px, &py)) {
+        return NULL;
+    }
+    px -= self->anchor.x;
+    py -= self->anchor.y;
+    b = px * -self->normal.y + py * self->normal.x;
+    d = self->normal.x * px + self->normal.y * py;
+    return Py_BOOL((b > -PLANAR_EPSILON) & (b < self->length + PLANAR_EPSILON)
+        & (d <= -PLANAR_EPSILON));
+}
+
+static PyObject *
+Segment_point_right(PlanarLineObject *self, PyObject *pt)
+{
+    double px, py, b, d;
+
+    assert(PlanarSegment_Check(self));
+    if (!PlanarVec2_Parse(pt, &px, &py)) {
+        return NULL;
+    }
+    px -= self->anchor.x;
+    py -= self->anchor.y;
+    b = px * -self->normal.y + py * self->normal.x;
+    d = self->normal.x * px + self->normal.y * py;
+    return Py_BOOL((b > -PLANAR_EPSILON) & (b < self->length + PLANAR_EPSILON) 
+        & (d >= PLANAR_EPSILON));
+}
+
+static PyObject *
+Segment_contains_point(PlanarLineObject *self, PyObject *pt)
+{
+    double px, py, b, d;
+
+    assert(PlanarSegment_Check(self));
+    if (!PlanarVec2_Parse(pt, &px, &py)) {
+        return NULL;
+    }
+    px -= self->anchor.x;
+    py -= self->anchor.y;
+    if (px * -self->normal.y + py * self->normal.x >= 0.0) {
+        d = self->normal.x * px + self->normal.y * py;
+    } else {
+        d = sqrt(px*px + py*py);
+    }
+    return Py_BOOL((d < PLANAR_EPSILON) & (d > -PLANAR_EPSILON));
+
+}
+
+static PlanarVec2Object *
+Segment_project(PlanarLineObject *self, PyObject *pt)
+{
+    double px, py, along;
+
+    assert(PlanarSegment_Check(self));
+    if (!PlanarVec2_Parse(pt, &px, &py)) {
+        return NULL;
+    }
+    px -= self->anchor.x;
+    py -= self->anchor.y;
+    along = px * -self->normal.y + py * self->normal.x;
+    if (along < 0.0) {
+        /* point behind */
+        return PlanarVec2_FromStruct(&self->anchor);
+    } else if (along > self->length) {
+        /* point ahead */
+        return PlanarVec2_FromDoubles(
+            self->anchor.x + -self->normal.y * self->length,
+            self->anchor.y + self->normal.x * self->length);
+    } else {
+        /* point beside */
+        return PlanarVec2_FromDoubles(
+            self->anchor.x + -self->normal.y * along,
+            self->anchor.y + self->normal.x * along);
+    }
+}
+
+static PyMethodDef Segment_methods[] = {
+    {"from_normal", (PyCFunction)Segment_new_from_normal, 
+        METH_CLASS | METH_VARARGS, 
+        "Create a line segment from a normal vector perpendicular to the "
+        "line containing the segment, the offset distance from that line to "
+        "origin, and the signed distances along that line from the projection "
+        "of the origin to the start and end points of the segment "
+        "respectively."},
+    {"from_points", (PyCFunction)Segment_new_from_points, METH_CLASS | METH_O, 
+        "Create a line segment from one or more collinear points.  The first "
+        "point is assumed to be the anchor. The furthest point from the "
+        "anchor is the end point."},
+    {"distance_to", (PyCFunction)Segment_distance_to, METH_O,
+        "Return the distance from the line segment to the specified point."},
+    {"point_behind", (PyCFunction)Segment_point_behind, METH_O,
+        "Return True if the specified point is behind the anchor point with "
+        "respect to the direction of the line segment."},
+    {"point_ahead", (PyCFunction)Segment_point_ahead, METH_O,
+        "Return True if the specified point is ahead of the endpoint "
+        "of the line segment with respect to its direction."},
+    {"point_left", (PyCFunction)Segment_point_left, METH_O,
+        "Return True if the specified point is in the space "
+        "to the left of, but not behind the line segment."},
+    {"point_right", (PyCFunction)Segment_point_right, METH_O,
+        "Return True if the specified point is in the space "
+        "to the right of, but not behind the line segment."},
+    {"contains_point", (PyCFunction)Segment_contains_point, METH_O,
+        "Return True if the specified point is on the line segment."},
+    {"project", (PyCFunction)Segment_project, METH_O,
+        "Compute the projection of a point onto the line segment. This "
+        "is the closest point on the line segment to the specified point."},
+    /*
+    {"almost_equals", (PyCFunction)Ray_almost_equals, METH_O,
+        "Return True if this line segment is approximately equal to "
+        "another line segment, within precision limits."},
+    */
+    {NULL, NULL}
+};
+
 PyDoc_STRVAR(Segment_doc, 
     "Directed ray anchored by a single point.\n\n"
     "Ray(anchor, direction)"
     0,                    /* tp_weaklistoffset */
     0,                    /* tp_iter */
     0,                    /* tp_iternext */
-    0, //Segment_methods,      /* tp_methods */
+    Segment_methods,      /* tp_methods */
     Segment_members,      /* tp_members */
     Segment_getset,       /* tp_getset */
     0,                    /* tp_base */

File lib/planar/line.py

View file
  • Ignore whitespace
 
     @classmethod
     def from_points(cls, points):
-        """Create a line segment from two or more collinear points.  The first
+        """Create a line segment from one or more collinear points.  The first
         point is assumed to be the anchor.  The order of the remaining points
         is unimportant, however they must all be collinear.  The furthest
         point from the anchor determines the line segment's vector.
         return Line(self._anchor, self.direction)
 
     def distance_to(self, point):
-        """Return the distance between the given point and the ray."""
+        """Return the distance between the given point and the line segment."""
         point = planar.Vec2(*point)
         to_point = point - self._anchor
         along = self.direction.dot(to_point)

File test/test_line.py

View file
  • Ignore whitespace
         assert_equal(line.end, self.Vec2(1003, 3009))
         assert line.contains_point((0,0))
 
+    def test_from_points_many_collinear_from_seq2(self):
+        import planar
+        line = self.LineSegment.from_points(
+            planar.Seq2([(-7,-21), (-3,-9), (1, 3), (1003,3009), (5,15)]))
+        assert_equal(line.direction, self.Vec2(1,3).normalized())
+        assert_equal(line.normal, self.Vec2(3,-1).normalized())
+        assert_equal(line.anchor, self.Vec2(-7, -21))
+        assert_equal(line.end, self.Vec2(1003, 3009))
+        assert line.contains_point((0,0))
+
     def test_from_points_degenerate(self):
         line = self.LineSegment.from_points([(2,1), (2,1), (2,1)])
         assert_equal(line.direction, self.Vec2(1,0))
         assert line.contains_point(segment.end)
 
     def test_distance_to(self):
-        line = self.LineSegment((-1, 1), (1, 1))
+        line = self.LineSegment((-1, 1), (5, 5))
         assert_almost_equal(line.distance_to((0,0)), math.sqrt(2))
+        assert_almost_equal(line.distance_to((-1,-2)), 3)
         assert_almost_equal(line.distance_to((0,1)), math.sqrt(2) / 2)
         assert_almost_equal(line.distance_to(
-            self.Vec2(1,5)), (self.Vec2(1,5) - self.Vec2(0,2)).length)
+            self.Vec2(1,5)), (self.Vec2(1,5) - self.Vec2(2,4)).length)
         assert_almost_equal(line.distance_to((-0.5, 1.5)), 0)
         assert_almost_equal(line.distance_to((-3, -1)), 2 * math.sqrt(2))
+        assert_almost_equal(line.distance_to((4, 8)), 2)
 
     def test_contains_point(self):
         import planar