-10

I found this post while searching for the topic, and am very surprised to see it is locked and closed. What gives? How do you detect where two line segments intersect?

Checking the Help Center and its requirements:

Stack Overflow is for professional and enthusiast programmers, people who write code because they love it. We feel the best Stack Overflow questions have a bit of source code in them, but if your question generally covers…

  • a specific programming problem, or
  • a software algorithm, or
  • software tools commonly used by programmers; and is
  • a practical, answerable problem that is unique to software development

… then you’re in the right place to ask your question!

the question seems to very obviously satisfy both criteria #1 and #2. "How do I compute whether two lines intersect" is a specific programming problem that is solved by specific algorithms. Note that this is not a question about mathematical concepts or definitions (Q: When do two lines intersect? A: When they have at least one point in common), but about how to compute an intersection point. Note also that the two highest voted answers cite programming books and textbooks.

9
  • 2
    What programming problem is it and for which programming language do they want a practical solution?
    – rene
    Jun 2, 2019 at 21:33
  • 4
    You want to redo what happened on Mar, 17th?
    – rene
    Jun 2, 2019 at 21:35
  • 3
    @rene: "what programming problem is it?": given four points, compute if the line segments connecting the points intersect, and if so, what the coordinates are of the intersection point. "What programming language?" why can't questions about algorithms be language-agnostic?
    – user168715
    Jun 2, 2019 at 22:26
  • @rene I have no idea what happened on Mar 17th. Was there already a meta discussion about this question?
    – user168715
    Jun 2, 2019 at 22:26
  • 2
    I guess my main question is why the SO community is so hostile to this question (which strikes me as a standard computational geometry question, which comes up quite often when coding up graphics, UIs, etc) and offers no explanations for why this question does not fit the Help Center, either in the original close rationale or in this thread. There's not even a comment on the question saying "this kind of thing is better at math.se" (which in any case is arguable).
    – user168715
    Jun 2, 2019 at 22:34
  • We in SOCVR were already hostile to it in 2015
    – rene
    Jun 2, 2019 at 22:41
  • 4
    Pretty typical for the Q+A that was created in 2008 and 2009. Users back then still had no real idea what useful Q+A looked like. Dozens of answers (many deleted) of programmers that used their own favorite language, often with bugs that create more posts, is not useful. Such Q+A gets messed about later, like a user did in 2017 to try to make it on topic. And the typical never-ending flags and evermore barely useful answers such a question generates. Moderators have no real alternative but to slam a lock on it. That they didn't delete it makes you happy right now, as good as it can get Jun 2, 2019 at 22:48
  • 2
    @HansPassant: Yes, we should instead totally restrict ourselves to the most useful Q&A possible: debugging questions. There's only one answer, and it's easily determinable if the answer is right. Those are definitely the most useful questions. God knows I find those questions all the time via Google. /sarcasm I don't think this is a good question because it's not a programming question, not because it's not useful. Jun 2, 2019 at 22:52
  • I view SO as a place where programmers argue over best practices for solving a problem. And I find the most use when those discussions use different algorithms (and even different languages). As anyone dealing with graphics will have to deal with this particular question at some point there is a reason this is one of the most clicked on result in Google. If we only dealt in debugging questions, then the viewership would decline significantly.
    – Mark Walsh
    Apr 30, 2020 at 18:32

2 Answers 2

8

Note that this is not a question about mathematical concepts or definitions (Q: When do two lines intersect? A: When they have at least one point in common), but about how to compute an intersection point.

How to compute the intersection point is a mathematical concept. I know that because, if I were to solve this problem, my solution would be a couple of equations.

Now to be fair, technically the answer won't just be equations; there has to be the conditional tests to see if the intersection point is actually between the two segments. But overall, this is far more about pure mathematics and geometry than about algorithms and programming.

why can't questions about algorithms be language-agnostic?

They can be. But there's a distinction between "give me an algorithm" and "give me a math equation". I would argue that this question falls much stronger into the latter category than the former.

This question might be appropriate for ComputerGraphics.SE, or one of the math sites. But it's far too much of a pure math problem for us here.

Basically, as yourself this: if you needed an answer to the question, would you go to a random mathematician or a random programmer? Yes, some programmers do have that domain knowledge. But I rather suspect a lot more mathematicians do than programmers.

8
  • This is fair point. For what it's worth, I'm a researcher in an area that strongly intersects math and CS. I am perfect capable of working out the equations for line intersection. There are many ways to turn the math into code, not all equally robust and efficient, and I came to this site specifically to find the canonical, CS-idiomatic solution. It's a shame if it's not possible to look beyond the at-first-blush mathematical problem statement to the common and useful programming question beneath.
    – user168715
    Jun 2, 2019 at 22:45
  • 2
    @user168715: "I came to this specifically to find the canonical, CS-idiomatic solution." There's no such thing. Robustness and efficiency are highly dependent on things that vary from language to language, from hardware to hardware. You can't determine those things from first-principles; they only really apply to specific cases. We're not talking about sorting algorithms here (and even sorting algorithms are more or less efficient depending on a variety of implementation-dependent factors). Jun 2, 2019 at 22:48
  • 1
    Even if people cannot agree on the best algorithm, surely you will concede there are better and worse ways of solving this problem. I was looking for a solution that (1) is robust to parallel and overlapping segments (2) did not break down in the case of horizontal or vertical line segments etc and (3) used as few flops and branches as possible. The first answer did turn out to be quite useful to me (based on the GPU Gems article). If there are several possible answers, surely, that's why the site allows multiple answers per question?
    – user168715
    Jun 2, 2019 at 22:53
  • 3
    @user168715 nowhere in that question is there anything about your criteria. The question, as stated, is asking for the mathematical solution. It is the question that is the problem here.
    – Martijn Pieters Mod
    Jun 3, 2019 at 0:31
  • 1
    @MartijnPieters for better or worse, it's the second Google link anyone finds when searching for code to compute line-line intersections. Given the high number of upvotes on the answers, I doubt I'm the only one looking for this. I'm not sure what the fix is (edit this question to be more verbose? delete it and replace it with a rewritten question?) but you may want to do something
    – user168715
    Jun 3, 2019 at 2:11
  • 2
    @user168715: That's why we have historical locks. There's nothing more to "fix". We don't allow such questions anymore, so the question therefore should be closed. But it is a useful artifact nevertheless. It's locked right now due to a content dispute with someone who I presume was trying to make it look like more of a programming question, even though it clearly isn't. Jun 3, 2019 at 2:22
  • 1
    @NicolBolas I'm still at a total loss how computing intersection of two lines is not a "programming question" (especially coming from a fellow CG expert). People who ask a mathematician how to do this are going to get useless answers that assume exact arithmetic, don't work with IEEE floating point, and can't be turned into efficient code in a straightforward way. I don't know what evidence I can provide beyond the fact this question appears in two programming books, shows up on programming contests (open.kattis.com/problems/segmentintersection) (more)
    – user168715
    Jun 3, 2019 at 2:34
  • 1
    and is something that practitioners need to code up quite often when doing graphics, collision detection, etc (as you well know). But I'm done tilting at windmills here...
    – user168715
    Jun 3, 2019 at 2:35
7

The question body is:

How do I determine whether or not two lines intersect, and if they do, at what x,y point?

At face value, this is a question which is entirely about geometry. We perhaps might adopt a more lenient reading by assuming that, given this is Stack Overflow, there is an implicit "how to compute" in there, and then making that explicit with an edit (the March 17th edit war rene refers to was about that). The problem, however, is that, as a programming question, it is too broad because it is underspecified. More specifically:

  • There is no indication of which language and libraries an answer should use, if any. Even if we further assume it is a language-agnostic question about algorithms, there is no indication of what is the representation of the line segments: base point and end point? Polar coordinates? Should we make use of bounding boxes?

  • The issues mentioned above might conceivably be fixed if it was a new question. However, we are discussing a ten year old question with 27 answers, each one making its own assumptions about the problem. Rewriting the question and cleaning up the answers at this stage would be a mammoth undertaking that would be of little benefit to anyone. The historical lock it has seems like a reasonable compromise.

4
  • 2
    "there is no indication of what is the representation of the line segments: base point and end point? Polar coordinates?" To be fair, that's kind of irrelevant, since they're all mathematically interconvertible with one another. Jun 2, 2019 at 22:42
  • @NicolBolas Sure. If the answer is meant to be a concrete algorithm, though, the initial representation might, in principle, make a difference in what is the more convenient implementation. (To be honest, I'm not sure about how often polar representations of segments are used in practice -- I don't know all that much about computer graphics.)
    – duplode
    Jun 2, 2019 at 22:48
  • 1
    Maybe because I'm in an area that works with geometry a lot, but it's "obvious" to me that, unless specified otherwise, segments would be represented by the coordinates of their endpoints (whether as a pair of points, or point+vector, makes no different to the algorithm). If somebody really wanted to add an answer for how to do it with a polar representation, though, I don't see the problem?
    – user168715
    Jun 2, 2019 at 22:56
  • 4
    @user168715 The issue, mainly, is that SO deals better with narrower questions that don't lend themselves to long lists of disparate answers that readers then have to wade through to find something relevant to their use case. If this was a new question, it would make perfect sense to use comments to confirm the assumptions with the OP and edits to make them explicit in the question body. With a ten year old question that has dozens of answers, however, it is simply not worth the trouble.
    – duplode
    Jun 2, 2019 at 23:01

Not the answer you're looking for? Browse other questions tagged .