See attached diff for proposed changes.
This patch implements support for directed graph rendering in AG_Graph
by modifying the AG_GraphEdge type with a "type" field which can be
either directed or undirected. Existing API compatibility is perfectly
preserved, as the default edge type is undirected.
Additionally, lines between graph nodes are now clipped so that they
intersect with the node's bounding box.
Documentation and changelog have been updated appropriately.
The attached diff is relative to r10220. A test program which can
demonstrate the new features is available here:
https://github.com/charlesdaniels/teaching-learning/tree/master/libraries/libagar/graph_editor
I am happy to revise this patch based on feedback should their be any
deficiencies.
Additionally, a screenshot is attached showing off the new widget
primitives.
Cheers,
~ Charles
diff --git ChangeLogs/Release-1.6.0.txt ChangeLogs/Release-1.6.0.txt
index bed0658a6..4ba337a5d 100644
--- ChangeLogs/Release-1.6.0.txt
+++ ChangeLogs/Release-1.6.0.txt
@@ -36,4 +36,13 @@ particular order.
- VG: Fix invalid access in VG_View(3).
- Add missing include for 32-bit MSYS build. Thanks varialus!
- Manual page improvements (clarity, wording, added more examples).
-
+- GUI: add AG_ClipLine for clipping lines to rectangular bounding boxes
+- GUI: add AG_ClipLineCircle for clipping lines to circular regions
+- GUI: add AG_DrawArrowhead for drawing arrowheads of arbitrary size and angle
+ aligned to arbitrary vectors
+- GUI: add AG_GetLineIntersection for computing the intersection of two line
+ segments
+- GUI: add new gui_math functions: AG_Square, AG_HaveQuadraticSolution,
+ AG_QuadraticPositive, AG_QuadraticNegative, AG_Distance
+- GUI: add AG_DrawArrowLine for drawing lines with arrowheads
+- GUI: AG_Graph now supports directed graphs
diff --git gui/AG_Graph.3 gui/AG_Graph.3
index 56851a006..9eeda0deb 100644
--- gui/AG_Graph.3
+++ gui/AG_Graph.3
@@ -165,6 +165,9 @@ on the vertex.
.Fn AG_GraphEdgeNew "AG_Graph *graph" "AG_GraphVertex *v1" "AG_GraphVertex *v2" "void *userPtr"
.Pp
.Ft "AG_GraphEdge *"
+.Fn AG_DirectedGraphEdgeNew "AG_Graph *graph" "AG_GraphVertex *v1" "AG_GraphVertex *v2" "void *userPtr"
+.Pp
+.Ft "AG_GraphEdge *"
.Fn AG_GraphEdgeFind "AG_Graph *graph" "void *userPtr"
.Pp
.Ft "void"
@@ -194,6 +197,14 @@ and returns NULL.
.Fa userPtr
is an optional user pointer to associated with the edge.
.Pp
+.Fn AG_DirectedGraphEdgeNew
+identical to AG_GraphEdgeNew, but the edge is marked as being directed.
+Directed graph edges are assumed to point "to"
+.Fa v2.
+Directed graph edges are displayed with an arrowhead pointing towards
+.Fa v2
+(only on systems with floating point support).
+.Pp
.Fn AG_GraphEdgeFind
returns the vertex matching the specified user pointer, or NULL if no
match exists.
@@ -272,6 +283,9 @@ structure:
Vertices connected by edge
.It Ft void *userPtr
User pointer
+.It Ft enum ag_graph_edge_type type
+Either AG_GRAPH_EDGE_UNDIRECTED or AG_GRAPH_EDGE_DIRECTED to indicate an
+undirected or directed edge respectively
.El
.Sh SEE ALSO
.Xr AG_Intro 3 ,
@@ -282,3 +296,4 @@ User pointer
The
.Nm
widget first appeared in Agar 1.3.
+Support for directed graphs first appeared in Agar 1.6.
diff --git gui/AG_WidgetPrimitives.3 gui/AG_WidgetPrimitives.3
index b1c37841a..5c4abc4ea 100644
--- gui/AG_WidgetPrimitives.3
+++ gui/AG_WidgetPrimitives.3
@@ -1,4 +1,5 @@
-.\" Copyright (c) 2009-2018 Julien Nadeau Carriere <[email protected]>
+.\" Copyright (c) 2009-2018 Julien Nadeau Carriere <[email protected]>,
+.\" 2019 Charles A. Daniels <[email protected]>
.\" All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
@@ -118,6 +119,9 @@ argument's local coordinate system.
.Ft void
.Fn AG_DrawRectBlended "AG_Widget *widget" "AG_Rect r" "AG_Color c" "AG_AlphaFn blendFn"
.Pp
+.Ft void
+.Fn AG_DrawArrowLine "void *_Nonnull obj" "int x1" "int y1" "int x2" "int y2" "AG_ArrowLineType t" "int length" "double theta" "const AG_Color *C"
+.Pp
.nr nS 0
.Fn AG_PutPixel
sets the pixel at
@@ -219,6 +223,17 @@ in that it accepts an explicit blending mode
(see
.Xr AG_AlphaFn 3
for details).
+.Fn Ag_DrawArrowLine
+is a rapper around AG_DrawLine and AG_DrawArrowhead which can draw a line along
+with, depending on the value of
+.Fa t
+, no arrowheads (AG_ARROWLINE_NONE), a forward arrow (AG_ARROWLINE_FORWARD), a
+reverse arrow (AG_ARROWLINE_REVERSE), or both a forward and reverse arrow
+(AG_ARROWLINE_BOTH). For the purposes of determining "forward" and "reverse",
+a forward arrow would be taken to point to (
+.Fa x2,
+.Fa y2
+). This function requires floating point support.
.Sh SIMPLE GRAPHICAL ELEMENTS
.nr nS 1
.Ft void
@@ -302,6 +317,9 @@ specify the colors of the tiles.
.Ft void
.Fn AG_DrawArrowRight "AG_Widget *widget" "int x" "int y" "int w" "AG_Color c1" "AG_Color c2"
.Pp
+.Ft void
+.Fn AG_DrawArrowhead "void *_Nonnull obj" "int x1" "int y1" "int x2" "int y2" "int length" "double theta" "const AG_Color *_Nonnull c"
+.Pp
.nr nS 0
The
.Fn AG_DrawPlus
@@ -330,6 +348,99 @@ draw an arrow at the specified coordinates.
and
.Fa w
specify the size of the arrow in pixels.
+.Pp
+.Fn AG_DrawArrowhead
+draws an arrowhead aligned to a line.
+.Fa x2
+and
+.Fa y2
+Define the tip of the arrowhead, and
+.Fa x1
+and
+.Fa y1
+define the originating point of the "line" (i.e. the arrowhead faces away from
+this point).
+.Fa length
+defines the length from tip to base of the arrowhead.
+.Fa theta
+defines the angle of the lines which converge at the tip of the arrowhead. The
+arrowhead is always drawn in a solid / fully filled style. This function
+requires floating point support.
+.Sh UTILITIES
+.nr nS 1
+.Ft int
+.Fn AG_GetLineIntersection "long x1" "long y1" "long x2" "long y2" "long x3" "long y3" "long x4" "long y4" "long *xi" "long *yi"
+.Pp
+.Ft void
+.Fn AG_ClipLine "int ax" "int ay" "int aw" "int ah" "int x1" "int y1" "int *x2" "int *y2"
+.Ft void
+.Fn AG_ClipLineCircle "int xc" "int yc" "int r" "int x1" "int y1" "int x2" "int y2" "int *xi" "int *yi"
+.Pp
+.Pp
+.Fn AG_GetLineIntersection
+considers two line segments (
+.Fa x1,
+.Fa y1
+), (
+.Fa x2,
+.Fa y2
+) and (
+.Fa x3,
+.Fa y3
+) and (
+.Fa x4,
+.Fa y4
+). If the lines do not intersect, then the function returns 0. If they do
+intersect, then the function returns 1 and
+.Fa xi
+and
+.Fa yi
+will be updated to the coordinates at which the intersection occurs. Requires
+floating point support.
+.Pp
+.Fn AG_ClipLine
+considers the bounding box defined by it's top left corner:
+.Fa ax,
+.Fa ay
+and its width and height:
+.Fa aw,
+.Fa ah
+and the line segment defined by (
+.Fa x1,
+.Fa y1,
+), (
+.Fa x2,
+.Fa y2,
+). If the line intersects with the provided bounding box, then
+.Fa x2
+and
+.Fa y2
+will be updated such that they are the closest point to (
+.Fa x1,
+.Fa y1
+) at which the line segment intersects with the given bounding box.
+.Pp
+.Fn AG_ClipLine
+If the circle centered at (
+.Fa xc,
+.Fa yc
+) with radius
+.Fa r
+intersects with the line segment (
+.Fa x1,
+.Fa y1
+), (
+.Fa x2,
+.Fa y2
+), then
+.Fa xi
+and
+.Fa yi
+are updated to reflect the intersection point which is closest to
+(
+.Fa x1,
+.Fa y1
+). This function requires floating point support.
.Sh SEE ALSO
.Xr AG_AlphaFn 3 ,
.Xr AG_Color 3 ,
@@ -341,3 +452,4 @@ specify the size of the arrow in pixels.
Simple widget primitives first appeared in Agar 1.0.
The basic rendering system was redesigned in Agar 1.4.
64-bit pixel access routines were added in Agar 1.6.
+AG_GetLineIntersection, AG_ClipLine, and AG_DrawArrowhead were added in Agar 1.6.
diff --git gui/graph.c gui/graph.c
index 463eb4a0c..5c465a06b 100644
--- gui/graph.c
+++ gui/graph.c
@@ -1,5 +1,6 @@
/*
- * Copyright (c) 2007-2019 Julien Nadeau Carriere <[email protected]>
+ * Copyright (c) 2007-2019 Julien Nadeau Carriere <[email protected]>,
+ * 2019 Charles A. Daniels, <[email protected]>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -10,7 +11,7 @@
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
- *
+ *
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
@@ -199,6 +200,7 @@ AG_GraphEdgeNew(AG_Graph *gf, AG_GraphVertex *v1, AG_GraphVertex *v2,
edge->userPtr = userPtr;
edge->graph = gf;
edge->popupMenu = NULL;
+ edge->type = AG_GRAPH_EDGE_UNDIRECTED;
TAILQ_INSERT_TAIL(&gf->edges, edge, edges);
gf->nedges++;
@@ -214,6 +216,14 @@ AG_GraphEdgeNew(AG_Graph *gf, AG_GraphVertex *v1, AG_GraphVertex *v2,
return (edge);
}
+AG_GraphEdge *
+AG_DirectedGraphEdgeNew(AG_Graph *gf, AG_GraphVertex *v1, AG_GraphVertex *v2,
+ void *usrPtr) {
+ AG_GraphEdge *edge = AG_GraphEdgeNew(gf, v1, v2, usrPtr);
+ edge->type = AG_GRAPH_EDGE_DIRECTED;
+ return edge;
+}
+
void
AG_GraphEdgeFree(AG_GraphEdge *edge)
{
@@ -241,7 +251,7 @@ void
AG_GraphEdgeLabel(AG_GraphEdge *ge, const char *fmt, ...)
{
va_list ap;
-
+
AG_ObjectLock(ge->graph);
va_start(ap, fmt);
Vsnprintf(ge->labelTxt, sizeof(ge->labelTxt), fmt, ap);
@@ -477,7 +487,7 @@ AG_GraphFreeVertices(AG_Graph *gf)
AG_GraphEdge *edge, *edgeNext;
AG_ObjectLock(gf);
-
+
for (vtx = TAILQ_FIRST(&gf->vertices);
vtx != TAILQ_END(&gf->vertices);
vtx = vtxNext) {
@@ -499,7 +509,7 @@ AG_GraphFreeVertices(AG_Graph *gf)
gf->yMin = 0;
gf->yMax = 0;
gf->flags &= ~(AG_GRAPH_DRAGGING);
-
+
AG_ObjectUnlock(gf);
AG_Redraw(gf);
}
@@ -573,12 +583,107 @@ Draw(void *obj)
if (edge->flags & AG_GRAPH_HIDDEN) {
continue;
}
- AG_DrawLine(gf,
- edge->v1->x - xOffs,
- edge->v1->y - yOffs,
- edge->v2->x - xOffs,
- edge->v2->y - yOffs,
- &edge->edgeColor);
+
+#ifdef HAVE_FLOAT
+ int xi1, yi1, xi2, yi2;
+ int x1, y1, x2, y2;
+ int h1, w1, h2, w2;
+
+ /* cache to avoid pointer chasing */
+ x1 = edge->v1->x - xOffs;
+ y1 = edge->v1->y - yOffs;
+ x2 = edge->v2->x - xOffs;
+ y2 = edge->v2->y - yOffs;
+ h1 = edge->v1->h;
+ w1 = edge->v1->w;
+ h2 = edge->v2->h;
+ w2 = edge->v2->w;
+
+ /* will be over-written with clipped positions */
+ xi1 = x1;
+ yi1 = y1;
+ xi2 = x2;
+ yi2 = y2;
+
+ /* perform the correct line clipping for the given vertex
+ * style */
+ if (edge->v2->style == AG_GRAPH_CIRCLE) {
+ AG_ClipLineCircle(
+ x2,
+ y2,
+ MAX(w2, h2) >> 1,
+ x1,
+ y1,
+ x2,
+ y2,
+ &xi2,
+ &yi2);
+
+ } else {
+ AG_ClipLine(
+ x2 - (w2 >> 1),
+ y2 - (h2 >> 1),
+ w2,
+ h2,
+ x1,
+ y1,
+ &xi2,
+ &yi2);
+ }
+
+ if (edge->v1->style == AG_GRAPH_CIRCLE) {
+ AG_ClipLineCircle(
+ x1,
+ y1,
+ MAX(w1, h1) >> 1,
+ x2,
+ y2,
+ x1,
+ y1,
+ &xi1,
+ &yi1);
+ } else {
+ AG_ClipLine(
+ x1 - (w1 >> 1),
+ y1 - (h1 >> 1),
+ w1,
+ h1,
+ x2,
+ y2,
+ &xi1,
+ &yi1);
+ }
+
+ /* Draw line appropriately depending on weather the edge type
+ * is directed or undirected. If floating point support is
+ * not available, then all edges are drawn undirected */
+ if (edge->type == AG_GRAPH_EDGE_DIRECTED) {
+ AG_DrawArrowLine(gf,
+ xi1,
+ yi1,
+ xi2,
+ yi2,
+ AG_ARROWLINE_FORWARD,
+ 20,
+ 0.5,
+ &edge->edgeColor);
+ } else {
+#endif /* HAVE_FLOAT */
+ AG_DrawLine(gf,
+#ifdef HAVE_FLOAT
+ xi1,
+ yi1,
+ xi2,
+ yi2,
+#else /* failover if we don't have float support */
+ edge->v1->x - xOffs, /* only have cache if
+ edge->v1->y - yOffs, * HAVE_FLOAT */
+ edge->v2->x - xOffs,
+ edge->v2->y - yOffs,
+#endif /* HAVE_FLOAT */
+ &edge->edgeColor);
+ }
+
if (edge->labelSu >= 0) {
AG_Surface *su = WSURFACE(gf,edge->labelSu);
@@ -686,7 +791,7 @@ AG_GraphVertex *
AG_GraphVertexNew(AG_Graph *gf, void *userPtr)
{
AG_GraphVertex *vtx;
-
+
vtx = Malloc(sizeof(AG_GraphVertex));
vtx->labelTxt[0] = '\0';
vtx->labelSu = -1;
@@ -746,7 +851,7 @@ AG_GraphVertexLabel(AG_GraphVertex *vtx, const char *fmt, ...)
{
char s[AG_GRAPH_LABEL_MAX];
va_list ap;
-
+
va_start(ap, fmt);
Vsnprintf(s, sizeof(s), fmt, ap);
va_end(ap);
@@ -772,7 +877,7 @@ void
AG_GraphVertexPosition(AG_GraphVertex *vtx, int x, int y)
{
AG_Graph *gf = vtx->graph;
-
+
AG_ObjectLock(gf);
vtx->x = x;
@@ -782,7 +887,7 @@ AG_GraphVertexPosition(AG_GraphVertex *vtx, int x, int y)
if (y < gf->yMin) { gf->yMin = y; }
if (x > gf->xMax) { gf->xMax = x; }
if (y > gf->yMax) { gf->yMax = y; }
-
+
AG_ObjectUnlock(gf);
AG_Redraw(gf);
}
@@ -814,7 +919,7 @@ AG_GraphVertexPopupMenu(AG_GraphVertex *vtx, struct ag_popup_menu *pm)
AG_ObjectUnlock(vtx->graph);
}
-static int
+static int
CompareVertices(const void *p1, const void *p2)
{
const AG_GraphVertex *v1 = *(const void **)p1;
@@ -892,7 +997,7 @@ AG_GraphAutoPlace(AG_Graph *gf, Uint w, Uint h)
AG_GraphVertex **vSorted, *vtx;
Uint i, nSorted=0;
int tx, ty;
-
+
AG_ObjectLock(gf);
if (gf->nvertices == 0 || gf->nedges == 0) {
diff --git gui/graph.h gui/graph.h
index ed0a99b2a..8eb120b8d 100644
--- gui/graph.h
+++ gui/graph.h
@@ -20,6 +20,11 @@ enum ag_graph_vertex_style { /* Vertex style */
AG_GRAPH_CIRCLE /* Circle */
};
+enum ag_graph_edge_type {
+ AG_GRAPH_EDGE_UNDIRECTED,
+ AG_GRAPH_EDGE_DIRECTED
+};
+
typedef struct ag_graph_vertex {
char labelTxt[AG_GRAPH_LABEL_MAX]; /* Label text */
int labelSu; /* Text surface handle */
@@ -61,6 +66,7 @@ typedef struct ag_graph_edge {
struct ag_graph *_Nonnull graph; /* Back pointer to graph */
AG_TAILQ_ENTRY(ag_graph_edge) edges;
struct ag_popup_menu *_Nullable popupMenu; /* Edge popup menu */
+ enum ag_graph_edge_type type;
} AG_GraphEdge;
typedef struct ag_graph {
@@ -119,6 +125,11 @@ AG_GraphEdge *_Nullable AG_GraphEdgeNew(AG_Graph *_Nonnull,
AG_GraphVertex *_Nonnull,
void *_Nullable);
+AG_GraphEdge *_Nullable AG_DirectedGraphEdgeNew(AG_Graph *_Nonnull,
+ AG_GraphVertex *_Nonnull,
+ AG_GraphVertex *_Nonnull,
+ void *_Nullable);
+
AG_GraphEdge *_Nullable AG_GraphEdgeFind(AG_Graph *_Nonnull, void *_Nullable)
_Pure_Attribute;
diff --git gui/gui_math.h gui/gui_math.h
index df83ef3c3..0b40b4d21 100644
--- gui/gui_math.h
+++ gui/gui_math.h
@@ -52,16 +52,13 @@
# define Truncf(x) AG_Truncf(x)
# define Fracf(x) AG_Fracf(x)
# define FracInvf(x) AG_FracInvf(x)
+# define Square(x) AG_Square(x)
+# define Distance(x1,y1,x2,y2) AG_Distance(x1, y1, x2, y2)
#endif /* _AGAR_INTERNAL or _USE_AGAR_GUI_MATH */
__BEGIN_DECLS
#ifdef AG_HAVE_FLOAT
-static __inline__ float
-AG_Hypot(float x, float y)
-{
- return AG_Sqrt(x*x+y*y);
-}
static __inline__ int
AG_Truncf(double d)
{
@@ -77,6 +74,31 @@ AG_FracInvf(double d)
{
return (1 - (d - floor(d)));
}
+static __inline__ double
+AG_Square(double d) {
+ return d*d;
+}
+static __inline__ double
+AG_Distance(double x1, double y1, double x2, double y2) {
+ return AG_Sqrt(AG_Square(x2-x1) + AG_Square(y2-y1));
+}
+static __inline__ float
+AG_Hypot(float x, float y)
+{
+ return AG_Sqrt(AG_Square(x)+AG_Square(y));
+}
+static __inline__ unsigned char
+AG_HaveQuadraticSolution(double a, double b, double c) {
+ return (((AG_Square(b) - 4 * a * c) >= 0) && a != 0);
+}
+static __inline__ double
+AG_QuadraticPositive(double a, double b, double c) {
+ return ((-1 * b) + AG_Sqrt(AG_Square(b) - 4 * a * c)) / ( 2 * a);
+}
+static __inline__ double
+AG_QuadraticNegative(double a, double b, double c) {
+ return ((-1 * b) - AG_Sqrt(AG_Square(b) - 4 * a * c)) / ( 2 * a);
+}
#endif /* AG_HAVE_FLOAT */
__END_DECLS
diff --git gui/inline_primitive.h gui/inline_primitive.h
index 83031e4b2..6e1d7b95c 100644
--- gui/inline_primitive.h
+++ gui/inline_primitive.h
@@ -50,7 +50,7 @@ ag_put_pixel_rgb_8(void *obj, int x, int y, Uint8 r, Uint8 g, Uint8 b)
#endif
{
AG_Widget *wid = (AG_Widget *)obj;
-
+
wid->drvOps->putPixelRGB8(wid->drv,
wid->rView.x1 + x,
wid->rView.y1 + y,
@@ -90,7 +90,7 @@ ag_blend_pixel_32(void *obj, int x, int y, Uint32 px, AG_AlphaFn fnSrc)
{
AG_Widget *wid = (AG_Widget *)obj;
AG_Color c;
-
+
AG_GetColor32(&c, px, agSurfaceFmt);
wid->drvOps->blendPixel(wid->drv,
wid->rView.x1 + x,
@@ -112,7 +112,7 @@ ag_blend_pixel_rgba(void *obj, int x, int y, Uint8 c[4], AG_AlphaFn fnSrc)
{
AG_Widget *wid = (AG_Widget *)obj;
AG_Color cd;
-
+
AG_ColorRGBA_8(&cd, c[0], c[1], c[2], c[3]);
wid->drvOps->blendPixel(wid->drv,
wid->rView.x1 + x,
@@ -169,7 +169,7 @@ ag_put_pixel_rgb_16(void *obj, int x, int y, Uint16 r, Uint16 g, Uint16 b)
# endif
{
AG_Widget *wid = (AG_Widget *)obj;
-
+
wid->drvOps->putPixelRGB16(wid->drv,
wid->rView.x1 + x,
wid->rView.y1 + y,
@@ -189,7 +189,7 @@ ag_blend_pixel_64(void *obj, int x, int y, Uint64 px, AG_AlphaFn fnSrc)
{
AG_Widget *wid = (AG_Widget *)obj;
AG_Color c;
-
+
AG_GetColor32(&c, px, agSurfaceFmt);
wid->drvOps->blendPixel(wid->drv,
wid->rView.x1 + x,
@@ -422,7 +422,7 @@ ag_draw_box_rounded(void *obj, const AG_Rect *r, int z, int rad,
rd.y = wid->rView.y1 + r->y;
rd.w = r->w;
rd.h = r->h;
-
+
AG_ColorAdd(&c[0], cBg, (z<0) ? &agSunkColor : &agRaisedColor);
AG_ColorAdd(&c[1], &c[0], (z<0) ? &agLowColor : &agHighColor);
AG_ColorAdd(&c[2], &c[0], (z<0) ? &agHighColor : &agLowColor);
@@ -472,7 +472,7 @@ ag_draw_circle(void *obj, int x, int y, int r, const AG_Color *c)
#endif
{
AG_Widget *wid = (AG_Widget *)obj;
-
+
wid->drvOps->drawCircle(wid->drv,
wid->rView.x1 + x,
wid->rView.y1 + y,
@@ -492,7 +492,7 @@ ag_draw_circle_filled(void *obj, int x, int y, int r, const AG_Color *c)
#endif
{
AG_Widget *wid = (AG_Widget *)obj;
-
+
wid->drvOps->drawCircleFilled(wid->drv,
wid->rView.x1 + x,
wid->rView.y1 + y,
@@ -564,7 +564,7 @@ ag_draw_rect_blended(void *obj, const AG_Rect *r, const AG_Color *c,
{
AG_Widget *wid = (AG_Widget *)obj;
AG_Rect rd;
-
+
rd.x = wid->rView.x1 + r->x;
rd.y = wid->rView.y1 + r->y;
rd.w = r->w;
@@ -588,7 +588,7 @@ ag_draw_rect_dithered(void *obj, const AG_Rect *r, const AG_Color *c)
{
AG_Rect rd;
AG_Widget *wid = (AG_Widget *)obj;
-
+
rd.x = wid->rView.x1 + r->x;
rd.y = wid->rView.y1 + r->y;
rd.w = r->w;
@@ -615,7 +615,7 @@ ag_draw_frame(void *obj, const AG_Rect *r, int z, const AG_Color *cBase)
AG_Color c[2];
AG_Rect rd;
int y2, x2;
-
+
rd.x = wid->rView.x1 + r->x;
rd.y = wid->rView.y1 + r->y;
rd.w = r->w;
@@ -840,3 +840,25 @@ ag_draw_line_2(void *obj, int x1, int y1, int x2, int y2,
AG_ColorAdd(&c, C, &agLowColor);
wid->drvOps->drawLine(wid->drv, x1+1,y1+1, x2+1,y2+1, &c);
}
+
+#ifdef AG_HAVE_FLOAT
+#ifdef AG_INLINE_HEADER
+static __inline__ void
+AG_DrawArrowLine(void *_Nonnull obj, int x1, int y1, int x2, int y2,
+ AG_ArrowLineType t, int length, double theta, const AG_Color *_Nonnull C)
+#else
+void
+ag_draw_arrow_line(void *obj, int x1, int y1, int x2, int y2,
+ AG_ArrowLineType t, int length, double theta, const AG_Color *C)
+#endif
+{
+ AG_DrawLine(obj, x1, y1, x2, y2, C);
+ if ((t == AG_ARROWLINE_FORWARD) || (t == AG_ARROWLINE_BOTH)) {
+ AG_DrawArrowhead(obj, x1, y1, x2, y2, length, theta, C);
+ }
+ if ((t == AG_ARROWLINE_REVERSE) || (t == AG_ARROWLINE_BOTH)) {
+ AG_DrawArrowhead(obj, x2, y2, x1, y1, length, theta, C);
+ }
+
+}
+#endif /* AG_HAVE_FLOAT */
diff --git gui/primitive.c gui/primitive.c
index 449a3c464..00458cd1a 100644
--- gui/primitive.c
+++ gui/primitive.c
@@ -1,5 +1,6 @@
/*
- * Copyright (c) 2019 Julien Nadeau Carriere <[email protected]>
+ * Copyright (c) 2019 Julien Nadeau Carriere <[email protected]>, 2019 Charles A.
+ * Daniels <[email protected]>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
@@ -10,7 +11,7 @@
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
- *
+ *
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
@@ -25,6 +26,7 @@
#include <agar/core/core.h>
#include <agar/gui/primitive.h>
+#include <agar/gui/gui_math.h>
/* Import inlinables */
#undef AG_INLINE_HEADER
@@ -66,3 +68,344 @@ AG_DrawTiling(void *obj, const AG_Rect *r, int tsz, int offs,
alt1 = alt2;
}
}
+
+/*
+ * Return 0 in the case that the lines ((x1,y1), (x2,y2)) and ((x3,y3),(x4,y4))
+ * do not intersect, and 1 in the case that they do. If they do intersect, xi
+ * and yi are set to the point of intersection, and otherwise unmodified.
+ *
+ * Originally written by by Mukesh Prasad in Graphics Gems II by James Arvo in
+ * gem I.2, "Intersection of Line Segments".
+ *
+ * The intuitive background behind what's going on is described well by "Tricks
+ * of the Windows Game Programming Gurus" by Andre Lamothe (1999), Chapter 8,
+ * pp 413, "Computing the Intersection of Two Lines Using the Point Slope Form"
+ *
+ * The original code may be retrieved from
+ * https://github.com/erich666/GraphicsGems/blob/master/gemsii/xlines.c
+ *
+ * This method uses integer math since it deals primarily with physical pixels
+ * on the screen. If you need a highly accurate version, you should
+ * re-implement with floating point. If you came here looking for a floating
+ * point line intersection calculator, this one works pretty well:
+ * https://stackoverflow.com/a/14795484
+ */
+
+/**************************************************************
+ * *
+ * NOTE: The following macro to determine if two numbers *
+ * have the same sign, is for 2's complement number *
+ * representation. It will need to be modified for other *
+ * number systems. *
+ * *
+ **************************************************************/
+
+#define SAME_SIGNS( a, b ) \
+ (((long) ((unsigned long) a ^ (unsigned long) b)) >= 0 )
+
+int AG_GetLineIntersection (
+ x1, y1, /* First line segment */
+ x2, y2,
+
+ x3, y3, /* Second line segment */
+ x4, y4,
+
+ xi,
+ yi /* Output value:
+ * point of intersection */
+ )
+long
+ x1, y1, x2, y2, x3, y3, x4, y4,
+ *xi, *yi;
+{
+ long a1, a2, b1, b2, c1, c2; /* Coefficients of line eqns. */
+ long r1, r2, r3, r4; /* 'Sign' values */
+ long denom, offset, num; /* Intermediate values */
+
+ /* Compute a1, b1, c1, where line joining points 1 and 2
+ * is "a1 x + b1 y + c1 = 0".
+ */
+
+ a1 = y2 - y1;
+ b1 = x1 - x2;
+ c1 = x2 * y1 - x1 * y2;
+
+ /* Compute r3 and r4.
+ */
+
+
+ r3 = a1 * x3 + b1 * y3 + c1;
+ r4 = a1 * x4 + b1 * y4 + c1;
+
+ /* Check signs of r3 and r4. If both point 3 and point 4 lie on
+ * same side of line 1, the line segments do not intersect.
+ */
+
+ if ( r3 != 0 &&
+ r4 != 0 &&
+ SAME_SIGNS( r3, r4 ))
+ return ( 0 );
+
+ /* Compute a2, b2, c2 */
+
+ a2 = y4 - y3;
+ b2 = x3 - x4;
+ c2 = x4 * y3 - x3 * y4;
+
+ /* Compute r1 and r2 */
+
+ r1 = a2 * x1 + b2 * y1 + c2;
+ r2 = a2 * x2 + b2 * y2 + c2;
+
+ /* Check signs of r1 and r2. If both point 1 and point 2 lie
+ * on same side of second line segment, the line segments do
+ * not intersect.
+ */
+
+ if ( r1 != 0 &&
+ r2 != 0 &&
+ SAME_SIGNS( r1, r2 ))
+ return ( 0 );
+
+ /* Line segments intersect: compute intersection point.
+ */
+
+ denom = a1 * b2 - a2 * b1;
+ if ( denom == 0 )
+ return ( 0 );
+ offset = denom < 0 ? - denom / 2 : denom / 2;
+
+ /* The denom/2 is to get rounding instead of truncating. It
+ * is added or subtracted to the numerator, depending upon the
+ * sign of the numerator.
+ */
+
+ num = b1 * c2 - b2 * c1;
+ *xi = ( num < 0 ? num - offset : num + offset ) / denom;
+
+ num = a2 * c1 - a1 * c2;
+ *yi = ( num < 0 ? num - offset : num + offset ) / denom;
+
+ return ( 1 );
+}
+
+#undef SAME_SIGNS
+
+/* If the circle with the center (xc, yc) and radius r intersects with the line
+ * (x1, y1), (x2, y2), then xi and yi are updated to reflect the point at which
+ * the intersection occurs. In the event of two intersections, xi and yi are
+ * set to the intersection point closest to the point (x1, y1).
+ *
+ * XXX: When using this to draw lines between circles in AG_Graph, some of the
+ * results this returns seem a little strange... it seems to have a hard time
+ * with horizontal approaches, and in sufficiently close vertical approaches
+ * the intersection is detected on the wrong side of the circle. This may
+ * be due to floating point precision errors as m becomes very small or very
+ * large.
+ */
+void AG_ClipLineCircle(int xc, int yc, int r, int x1, int y1,
+ int x2, int y2, int *xi, int *yi) {
+
+ /* In the case that x1 and x2 are the same, there is a bug that causes
+ * m to be zero, resulting in no intersect being detected. */
+ if (x1 == x2) {x1++;}
+
+ /* the derivation here is fairly straightforward -- just calculate
+ * the y = mx+b form of the line segment, and then plug the y found
+ * thus into (x - xê)² + (y - yê)² = r²
+ *
+ * You should get an order-2 polynomial, the solution for which is
+ * trivially found with the quadratic formula.
+ */
+ double m = ((double) y2 - (double) y1) / ((double) x2 - (double) x1);
+ double k = -m * (double) x1 + (double) y1 - (double) yc;
+ double a = 1 + AG_Square(m);
+ double b = -2 * (double) xc + 2 * m * k;
+ double c = -1 * (AG_Square((double) r) - AG_Square((double) xc) - AG_Square(k));
+
+ /* no intersection */
+ if (! AG_HaveQuadraticSolution(a, b, c)) {return;}
+
+ /* calculate both possible intersections */
+ double xs1, ys1, xs2, ys2;
+ xs1 = AG_QuadraticPositive(a, b, c);
+ xs2 = AG_QuadraticNegative(a, b, c);
+ ys1 = m * (xs1 - (double) x1) + (double) y1;
+ ys2 = m * (xs2 - (double) x1) + (double) y1;
+
+ /* Pick the one closer to (x1, y1) and return it. If they are equal,
+ * then this docent matter and the answer will still be correct. */
+ if (AG_Distance((double) x1, (double) y1, xs1, ys1) <
+ AG_Distance((double) x1, (double) y1, xs2, ys2)) {
+ *xi = (int) xs1;
+ *yi = (int) ys1;
+ } else {
+ *xi = (int) xs2;
+ *yi = (int) ys2;
+ }
+}
+
+/*
+ * Given a widget object and a line, clip the line such that it ends on the
+ * border of the object. In other words, set x2, y2 to the intersect of the
+ * line and the object. If the line does not intersect the object, then x2 and
+ * y2 are unchanged.
+ *
+ */
+void AG_ClipLine(int ax, int ay, int aw, int ah, int x1, int y1, int *x2, int *y2) {
+
+ /* We simply compute the intersection with every possible face, and
+ * pick the one which is smallest. It _might_ be faster to decide which
+ * face we are "approaching" from, but I think the edge case handling
+ * logic would add a lot of complexity */
+
+ /*
+ * a.x, a.y +------+ a.x + a.w, a.y
+ * | |
+ * | |
+ * | |
+ * | |
+ * a.x, a.y + a.h +------+ a.x + a.w, a.y + a.h
+ */
+
+ long x1_d, y1_d, x2_d, y2_d;
+
+ x1_d = (long) x1;
+ y1_d = (long) y1;
+ x2_d = (long) *x2;
+ y2_d = (long) *y2;
+
+ struct {
+ long x1;
+ long y1;
+ long x2;
+ long y2;
+ long x3;
+ long y3;
+ long x4;
+ long y4;
+ long xi;
+ long yi;
+ int intersect;
+ } faces[4] = {
+ {x1_d, y1_d, x2_d, y2_d, ax , ay , ax , ay+ah, 0, 0, 0},
+ {x1_d, y1_d, x2_d, y2_d, ax , ay+ah, ax+aw, ay+ah, 0, 0, 0},
+ {x1_d, y1_d, x2_d, y2_d, ax+aw, ay+ah, ax+aw, ay , 0, 0, 0},
+ {x1_d, y1_d, x2_d, y2_d, ax+aw, ay , ax , ay , 0, 0, 0},
+ };
+
+ unsigned short best = 0;
+ double shortest_dist = -1;
+ double dist;
+ for (unsigned short i = 0 ; i < 4 ; i++) {
+ faces[i].intersect = AG_GetLineIntersection(
+ faces[i].x1,
+ faces[i].y1,
+ faces[i].x2,
+ faces[i].y2,
+ faces[i].x3,
+ faces[i].y3,
+ faces[i].x4,
+ faces[i].y4,
+ &(faces[i].xi),
+ &(faces[i].yi));
+
+ /* don't care about candidates that don't intersect with us */
+ if (faces[i].intersect != 1) {continue;}
+
+ dist = sqrt(pow(faces[i].xi-x1, 2) + pow(faces[i].yi-y1, 2));
+ if ((shortest_dist == -1) || (dist < shortest_dist)) {
+ best = i;
+ shortest_dist = dist;
+ }
+ }
+
+ /* no intersection, so leave x2, y2 as they are */
+ if (shortest_dist < 0) { return; }
+
+ *x2 = (int) faces[best].xi;
+ *y2 = (int) faces[best].yi;
+}
+
+/*
+ * Render an arrowhead. The arrowhead will be parallel to the given line (x1,
+ * y1), (x2, y2), and will be drawing pointing to (x2, y2).
+ *
+ * length refers to the length in pixels of the two sides that intersect at
+ * the tip of the arrowhead.
+ *
+ * theta refers to the angle between the two sides that intersect at the tip of
+ * the arrowhead.
+ *
+ */
+void AG_DrawArrowhead(void *_Nonnull obj, int x1, int y1,
+ int x2, int y2, int length, double theta,
+ const AG_Color *_Nonnull c)
+{
+ AG_Widget *wid = (AG_Widget *)obj;
+
+ AG_Pt P_start, P_tip,P1, P2;
+
+ double V_dirx, V_diry, V_refx, V_refy, V_per1x, V_per1y, V_per2x, V_per2y;
+
+ double width, hyp;
+
+
+ /* AG_Sqrt( */
+ /* ((double) P_tip.x - (double) P_start.x) * ((double) P_tip.x - (double) P_start.x) + */
+ /* ((double) P_tip.y - (double) P_start.y) * ((double) P_tip.y - (double) P_start.y) */
+ /* ); */
+
+
+ /* start and end of the actual line */
+ P_start.x = x1;
+ P_start.y = y1;
+ P_tip.x = x2;
+ P_tip.y = y2;
+
+ /* length of overall line, necessary to generate direction reference
+ * unit vector */
+ double line_length = AG_Distance((double) P_tip.x, (double) P_tip.y,
+ (double) P_start.x, (double) P_start.y);
+
+ /* Avoid a divide by zero error later -- we can't draw an error for
+ * a zero-length line anyway.
+ *
+ * XXX: maybe this should trigger an error condition or something?
+ *
+ * XXX: might want to use an epsilon test?
+ * */
+ if (line_length == 0) {return;}
+
+ /* direction reference vector -- this intentionally points the
+ * "wrong" way since it makes it convenient to calculate P_ref and
+ * we don't need this for anything else */
+ V_dirx = ((double) P_start.x - (double) P_tip.x) / (line_length);
+ V_diry = ((double) P_start.y - (double) P_tip.y) / (line_length);
+
+ /* reference vector, this is a point a bit back from the tip that we
+ * use to compute some trig later to find the corner points */
+ V_refx = (double) length * V_dirx + (double) P_tip.x;
+ V_refy = (double) length * V_diry + (double) P_tip.y;
+
+ /* perpendicular to the direction unit vector */
+ V_per1x = V_diry;
+ V_per1y = -1 * V_dirx;
+ V_per2x = -1 * V_diry;
+ V_per2y = V_dirx;
+
+ /* distance between the two non-tip vertices */
+ width = (int) (2.0 * (Tan(((double) theta) / 4.0 ) * 2.0 * (double) length));
+
+ /* calculate the non-tip corners */
+ P1.x = (int) ((double) P_tip.x + (V_dirx * (double) length) + (width / 2.0) * V_per1x);
+ P1.y = (int) ((double) P_tip.y + (V_diry * (double) length) + (width / 2.0) * V_per1y);
+ P2.x = (int) ((double) P_tip.x + (V_dirx * (double) length) + (width / 2.0) * V_per2x);
+ P2.y = (int) ((double) P_tip.y + (V_diry * (double) length) + (width / 2.0) * V_per2y);
+
+ /* wid->drvOps->drawTriangle(wid->drv, &P_tip, &P1, &P2, c); */
+
+ AG_DrawTriangle(wid, &P_tip, &P1, &P2, c);
+}
+
+
diff --git gui/primitive.h gui/primitive.h
index 154b5b316..c17c387ae 100644
--- gui/primitive.h
+++ gui/primitive.h
@@ -6,6 +6,13 @@
#include <agar/gui/widget.h>
#include <agar/gui/begin.h>
+typedef enum ag_arrowline_type {
+ AG_ARROWLINE_NONE,
+ AG_ARROWLINE_FORWARD,
+ AG_ARROWLINE_REVERSE,
+ AG_ARROWLINE_BOTH
+} AG_ArrowLineType;
+
__BEGIN_DECLS
#ifdef AG_INLINE_WIDGET
# define AG_INLINE_HEADER
@@ -63,6 +70,8 @@ void ag_draw_plus(void *_Nonnull, const AG_Rect *_Nonnull,
void ag_draw_minus(void *_Nonnull, const AG_Rect *_Nonnull,
const AG_Color *_Nonnull, AG_AlphaFn);
void ag_draw_line_2(void *_Nonnull, int,int, int,int, const AG_Color *_Nonnull);
+void ag_draw_arrow_line(void *obj, int x1, int y1, int x2, int y2,
+ AG_ArrowLineType t, int length, double theta, const AG_Color *C);
# define AG_PutPixel(o,x,y,c) ag_put_pixel((o),(x),(y),(c))
# define AG_PutPixel32(o,x,y,c) ag_put_pixel_32((o),(x),(y),(c))
@@ -98,10 +107,23 @@ void ag_draw_line_2(void *_Nonnull, int,int, int,int, const AG_Color *_Nonnull);
# define AG_DrawPlus(o,r,c,fn) ag_draw_plus((o),(r),(c),(fn))
# define AG_DrawMinus(o,r,c,fn) ag_draw_minus((o),(r),(c),(fn))
# define AG_DrawLine2(o,x1,y1,x2,y2,c) ag_draw_line_2((o),(x1),(y1),(x2),(y2),(c))
+#ifdef AG_HAVE_FLOAT
+#define AG_DrawArrowLine(o,x1,y1,x2,y2,t,l,th,c) ag_draw_arrow_line((o),(x1),(y1),(x2),(y2),(t),(l),(th),(c))
+#endif /* AG_HAVE_FLOAT */
#endif /* !AG_INLINE_WIDGET */
-void AG_DrawTiling(void *_Nonnull, const AG_Rect *_Nonnull, int, int,
+void AG_DrawTiling(void * , const AG_Rect *_Nonnull, int, int,
const AG_Color *_Nonnull, const AG_Color *_Nonnull);
+int AG_GetLineIntersection(long x1, long y1, long x2, long y2, long x3,
+ long y3, long x4, long y4, long *xi, long *yi);
+#ifdef AG_HAVE_FLOAT
+void AG_ClipLine(int ax, int ay, int aw, int ah, int x1, int y1, int *x2, int *y2);
+void AG_ClipLineCircle(int xc, int yc, int r, int x1, int y1,
+ int x2, int y2, int *xi, int *yi);
+void AG_DrawArrowhead(void *_Nonnull obj, int x1, int y1,
+ int x2, int y2, int length, double theta,
+ const AG_Color *_Nonnull c);
+#endif /* AG_HAVE_FLOAT */
__END_DECLS
#include <agar/gui/close.h>
_______________________________________________
Agar mailing list
[email protected]
http://libagar.org/lists.html
